Продолжаем проводить конкурс SQL в рамках международной олимпиады «IT-Планета 2026». Как обычно, на втором этапе участникам было предложено решить 5 задач на чистом SQL. Давайте перейдём к рассмотрению задач. В этот раз я решил разобрать задачи на примере реальных вариантов, присланных конкурсантами. Может быть, где-то они покажутся избыточными, где-то — неоптимальными, но зато они рабочие и на их примере можно объяснить подход к решению. На момент проверки мы видим только обезличенные данные: я не знаю авторов решений, только их идентификаторы, поэтому оставим всё как есть, только идентификаторы участников.
Перейдём к задачам.
Сломанная клавиатура
Шлагбаум парковки
Свободное место на парковке
Турнирная таблица НХЛ
Мобильная сеть
Общие мысли
Задача 1: Сломанная клавиатура
Условие
Программист Василий любил пить кофе, когда работал за ноутбуком. Он нечаянно пролил напиток, и теперь у него на клавиатуре не работают клавиши b,c,k,l,q,v,x,z,|,*,<,&,$,%.
В информационной системе хранятся данные о работе агентов компании. Каждый месяц в таблицу M сохраняются начисления за месяц. Таблицы созданы следующими командами:
-- таблица «агенты»
create table a (id_a int primary key, -- идентификатор агента
n text not null, -- имя агента
p numeric(3,1) default 0 not null -- комиссионные проценты
);
-- таблица «начисления за месяц»
create table m(id_m int primary key, -- идентификатор начисления
id_a int not null references a (id_a), -- идентификатор агента
s numeric(8,2) not null -- начисления за месяц
);Руководителю Василия Сергею Петровичу срочно понадобился отчёт по работе агентов за месяц с вычисленными итоговыми суммами с учётом комиссионных процентов за месяц. Отчет нужен очень срочно, другой клавиатуры у Василия нет. Помогите Василию написать запрос для получения данных, не используя клавиши, которые не работают.
В итоговый ответ должны попасть следующие поля:
Id_a — идентификатор агента;
Id_m — идентификатор начисления;
N — имя агента;
S — начисление за месяц;
P — комиссионные проценты;
T — итог начисления с учётом комиссионных процентов.
Расчёт итога:
T = S*(1+P/100)
В результат должны попасть все агенты, даже если им в этом месяце ничего не начислено.
Пример
Для следующих входных данных:
insert into a values (1,'Иванов',-5.5);
insert into a values (2,'Петрова',5);
insert into a values (3,'Кузнецов',0);
insert into a values (4,'Волкова',2);
insert into a values (5,'Зайцев',0);
insert into a values (6,'Воронова',3);
insert into a values (7,'Козлов',5);
insert into m values (1,1,10000);
insert into m values (2,2,10000);
insert into m values (3,3,6000);
insert into m values (4,5,5000);
insert into m values (5,6,2000);Результат:
id_a | id_m | n | s | p | t
------+------+----------+----------+------+----------
1 | 1 | Иванов | 10000.00 | -5.5 | 9450.00
2 | 2 | Петрова | 10000.00 | 5.0 | 10500.00
3 | 3 | Кузнецов | 6000.00 | 0.0 | 6000.00
5 | 4 | Зайцев | 5000.00 | 0.0 | 5000.00
6 | 5 | Воронова | 2000.00 | 3.0 | 2060.00
7 | | Козлов | | 5.0 |
4 | | Волкова | | 2.0 |
(7 rows)Разбор решения
Формализуем правила:
В запросе запрещено использовать часть символов.
Запрещённые символы ограничены только списком из условия.
Они не могут использоваться вне зависимости от регистра.
Решение
Эта задача задумывалась как простое задание для разминки, но половина участников с ней не справилась. Причина проста: раз запрос — значит оператор SELECT. Однако если посмотреть на список запрещённых символов, видно, что в нём присутствуют c и l. Значит, написать SELECT не получится, мы просто не сможем набрать это слово. Поэтому все решения с SELECT формально неправильны по критерию использования запрещённых символов.
Тут мы вспоминаем, что DML-операторы могут возвращать отношение через конструкцию RETURNING. Будем использовать UPDATE, обновляя данные на те же самые значения.
Ещё одна сложность была связана с вычисляемым полем: знак умножения * тоже запрещён. Пришлось вспомнить математику и придумать, чем заменить умножение, причём с учётом того, что проценты могут быть отрицательными.
Рассмотрим решение участника с идентификатором 16747. Поскольку оно невелико, приведём его сразу полностью:
UPDATE a SET p = a.p
FROM m RIGHT JOIN a AS a1 ON m.id_a = a1.id_a
WHERE a.id_a = a1.id_a
RETURNING
a.id_a, m.id_m, a.n, m.s, a.p,
ROUND((power(m.s + (1 + a.p/100.0), 2) - power(m.s, 2) - power(1 + a.p/100.0, 2)) / 2, 2) AS t;Используется оператор UPDATE, в нём обновляется таблица a с агентами. Поскольку нужны данные по всем агентам, даже без начислений в таблице m, приходится применять внешнее соединение. Выбрано правое внешнее соединение, потому что левое (LEFT) и полное (FULL) запрещены из-за символа l. При этом таблицу a для соединения приходится использовать ещё раз.
Вычисление итогового результата возможно несколькими способами: заменой умножения делением или через разность квадратов. В данном примере применена разность квадратов, хотя большинство участников использовали замену умножения на деление. Однако это решение встречалось настолько часто, что возникало подозрение на использование ИИ.
Больше сказать по этой задаче нечего.
Задача 2: Шлагбаум парковки
Условие
В организации имеется парковка с ограниченным количеством мест. Для въезда и выезда используется один общий шлагбаум. Рядом с ним установлена камера с системой распознавания автомобильных номеров. Камера фиксирует как въезд, так и выезд автомобиля, сохраняя только распознанный номер и отметку времени. В журнале могут присутствовать повторяющиеся записи.
ИИ в установленной камере иногда ошибается, и тогда в номере, сохранённом в журнале, может присутствовать одна неправильная буква или цифра. Также в сохранённом номере может присутствовать одна нераспознанная цифра или буква, которая заменяется на символ «?».
Формат автомобильного номера: 000xxx, где:
000 — последовательность из трёх цифр;
xxx — последовательность из трёх букв латинского алфавита.
Определения
Расстояние между двумя номерами — количество позиций, в которых они различаются. Корректный номер — номер, не содержащий символа «?». Ошибочный номер — номер, содержащий ровно один символ «?». Подозрительный номер — номер, который:
не содержит «?»;
встречается в журнале только один раз;
отличается от некоторого корректного номера не более чем в одной позиции.
Не каждый номер, встречающийся один раз, является подозрительным.
Необходимо:
Обработать журнал и заменить ошибочные и подозрительные номера на корректные в соответствии с приведёнными ниже правилами.
Порядок записей и их количество должны быть сохранены.
Правила замены
Обработка выполняется в порядке следования записей в соответствии с временнóй меткой.
Ошибочные номера
Пусть рассматривается запись с ошибочным номером.
Рассматриваются корректные номера из предшествующих записей по временнóй метке.
Из них выбираются номера, совпадающие с данным во всех позициях, кроме позиции с «?».
Если такие номера существуют, выбирается номер:
встречавшийся ранее наибольшее количество раз;
если таких номеров несколько, то выбирается тот, который встречается раньше остальных.
Если среди предыдущих записей подходящего номера нет, поиск выполняется по тем же критериям по всему журналу.
Подозрительные номера
Пусть рассматривается запись с подозрительным номером.
Рассматриваются корректные номера из предшествующих записей по временнóй метке.
Выбираются номера, расстояние до которых не превышает 1.
Если такие номера существуют, выбирается номер:
встречавшийся ранее наибольшее количество раз;
если таких номеров несколько, то выбирается тот, который встречается раньше остальных.
Если подходящего номера нет, запись остаётся без изменений.
В результате необходимо получить журнал, в котором все ошибочные и подозрительные номера заменены на соответствующие корректные номера. Повторяющиеся строки журнала должны сохраниться.
Для регистрации въездов и выездов в системе создана таблица:
create table gate (
id bigserial primary key, -- Идентификатор записи журнала
carnumber varchar(6) not null, -- автомобильный номер
ts timestamp not null -- временная метка
);Пример
Для следующих входных данных:
insert into gate(carnumber,ts) values ('123abc','2026-03-01 08:00:00');
insert into gate(carnumber,ts) values ('123abc','2026-03-01 18:13:00');
insert into gate(carnumber,ts) values ('123abc','2026-03-02 08:05:00');
insert into gate(carnumber,ts) values ('123abb','2026-03-02 18:15:00');
insert into gate(carnumber,ts) values ('564kpa','2026-03-01 07:50:00');
insert into gate(carnumber,ts) values ('56?kpa','2026-03-01 13:05:00');
insert into gate(carnumber,ts) values ('565kpa','2026-03-01 13:50:00');
insert into gate(carnumber,ts) values ('565kpa','2026-03-01 17:50:00');
insert into gate(carnumber,ts) values ('845cko','2026-03-01 10:01:00');
insert into gate(carnumber,ts) values ('845cko','2026-03-01 17:16:00');
insert into gate(carnumber,ts) values ('745cko','2026-03-02 13:01:00');
insert into gate(carnumber,ts) values ('845c?o','2026-03-02 17:55:00');Результат:
id | carnumber | ts
----+-----------+---------------------
1 | 123abc | 2026-03-01 08:00:00
2 | 123abc | 2026-03-01 18:13:00
3 | 123abc | 2026-03-02 08:05:00
4 | 123abc | 2026-03-02 18:15:00
5 | 564kpa | 2026-03-01 07:50:00
6 | 564kpa | 2026-03-01 13:05:00
7 | 565kpa | 2026-03-01 13:50:00
8 | 565kpa | 2026-03-01 17:50:00
9 | 845cko | 2026-03-01 10:01:00
10 | 845cko | 2026-03-01 17:16:00
11 | 845cko | 2026-03-02 13:01:00
12 | 845cko | 2026-03-02 17:55:00
(12 rows)Разбор решения
Рассмотрим некоторые замечания к формулировке, которые появились после обсуждений.
Все поиски — только по исходному журналу
Самое коварное место — фраза «из предшествующих записей». Возникает естественное желание вести накопленный журнал: обработали запись, заменили номер и для следующей записи ищем кандидатов уже среди исправленных. Но тестовый пример показывает, что это не так.
Кандидаты для замены всегда ищутся в исходной таблице, а не в промежуточном результате. Замены не влияют друг на друга. Статусы «ошибочный» и «подозрительный» тоже определяются один раз по исходным данным до начала обработки и не пересчитываются динамически.
Подозрительный номер определяется только по предыдущим записям
Ошибочный номер при отсутствии кандидатов среди предыдущих записей может быть исправлен по всему журналу, в правилах это сказано явно. Для подозрительного номера такой возможности нет: если среди предыдущих записей подходящего корректного номера не нашлось, запись остаётся без изменений, даже если позже в журнале такой номер присутствует.
Пример из тестовых данных: 564kpa (id=5) формально подозрительный: встречается один раз, расстояние до 565kpa равно единице. Но это самая первая запись по времени, предыдущих у неё нет. Поэтому замены не происходит, и номер остаётся 564kpa.
Корректный номер может быть одновременно и подозрительным
Определение корректного номера требует ровно одного — отсутствия в номере символа «?». Оно ничего не говорит о частоте встречаемости или расстоянии до других номеров. Поэтому номер может быть одновременно и корректным, и подозрительным — эти статусы не исключают друг друга.
В чём это проявляется? Кандидата для замены ошибочного номера следует искать среди корректных, а не среди «не подозрительных». Поэтому 564kpa (id=5), будучи корректным по формальному признаку, выступает кандидатом для ошибочного 56?kpa (id=6), и этот кандидат выигрывает, так как он единственный подходит под шаблон. То, что 564kpa сам является подозрительным, никак не ограничивает его право быть кандидатом.
Частота и порядок появления считаются по предшествующим записям
Фраза «встречавшийся ранее наибольшее количество раз» означает «среди записей, предшествующих текущей по временнóй метке». Считается не общее количество вхождений номера в журнал, а только те, что расположены до обрабатываемой строки. Аналогично и с критерием «встречается раньше остальных»: сравниваются первые появления среди предшествующих записей, а не по всему журналу.
Дубликаты сохраняются
В условии явно сказано: «в журнале могут присутствовать повторяющиеся записи» и «порядок записей и их количество должны быть сохранены». Если запись не подлежит замене, она переносится в результат как есть. Никакого удаления дубликатов или группировки.
Перейдём к рассмотрению решения, предложенного конкурсантом с идентификатором 24838.
Запрос orig_unique — убираем дубли в журнале.
SELECT carnumber, ts FROM gate GROUP BY carnumber, tsРезультат выполнения
carnumber | ts -----------+--------------------- 565kpa | 2026-03-01 17:50:00 745cko | 2026-03-02 13:01:00 56?kpa | 2026-03-01 13:05:00 123abb | 2026-03-02 18:15:00 845cko | 2026-03-01 17:16:00 123abc | 2026-03-01 08:00:00 565kpa | 2026-03-01 13:50:00 123abc | 2026-03-02 08:05:00 845cko | 2026-03-01 10:01:00 123abc | 2026-03-01 18:13:00 564kpa | 2026-03-01 07:50:00 845c?o | 2026-03-02 17:55:00 (12 rows)Оставляем в orig_correct только корректные номера: как отмечалось ранее, это номера где нет символа «?».
SELECT carnumber, ts FROM orig_unique WHERE POSITION('?' IN carnumber) = 0Результат выполнения
carnumber | ts -----------+--------------------- 123abb | 2026-03-02 18:15:00 123abc | 2026-03-01 08:00:00 123abc | 2026-03-01 18:13:00 123abc | 2026-03-02 08:05:00 564kpa | 2026-03-01 07:50:00 565kpa | 2026-03-01 13:50:00 565kpa | 2026-03-01 17:50:00 745cko | 2026-03-02 13:01:00 845cko | 2026-03-01 10:01:00 845cko | 2026-03-01 17:16:00 (10 rows)Запрос orig_stats статистика по исходному журналу. Вычислим частоту встречаемости номера и минимальное значение отметки времени.
SELECT carnumber, COUNT(*) AS freq, MIN(ts) AS first_ts FROM orig_correct GROUP BY carnumberРезультат выполнения
carnumber | freq | first_ts -----------+------+--------------------- 123abb | 1 | 2026-03-02 18:15:00 123abc | 3 | 2026-03-01 08:00:00 564kpa | 1 | 2026-03-01 07:50:00 565kpa | 2 | 2026-03-01 13:50:00 745cko | 1 | 2026-03-02 13:01:00 845cko | 2 | 2026-03-01 10:01:00 (6 rows)Запрос suspicious — список подозрительных номеров. Оставляем только те номера, которые удовлетворяют двум условиям: встречаются в исходном журнале ровно один раз, и существует хотя бы один корректный номер на расстоянии не более 1.
SELECT o1.carnumber FROM orig_stats o1 WHERE o1.freq = 1 AND EXISTS ( SELECT 1 FROM orig_stats o2 WHERE o2.carnumber != o1.carnumber AND ( (CASE WHEN SUBSTR(o1.carnumber,1,1) = SUBSTR(o2.carnumber,1,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(o1.carnumber,2,1) = SUBSTR(o2.carnumber,2,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(o1.carnumber,3,1) = SUBSTR(o2.carnumber,3,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(o1.carnumber,4,1) = SUBSTR(o2.carnumber,4,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(o1.carnumber,5,1) = SUBSTR(o2.carnumber,5,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(o1.carnumber,6,1) = SUBSTR(o2.carnumber,6,1) THEN 0 ELSE 1 END) ) <= 1 )Результат выполнения
carnumber ----------- 123abb 564kpa 745cko (3 rows)В ordered_gate получаем записи журнала, пронумерованные в нужном порядке, причём берём их из исходной таблицы, чтобы присутствовали дубли строк
SELECT id, carnumber, ts, POSITION('?' IN carnumber) > 0 AS is_erroneous, EXISTS(SELECT 1 FROM suspicious s WHERE s.carnumber = gate.carnumber) AS is_suspicious, ROW_NUMBER() OVER (ORDER BY ts, id) AS rn FROM gateРезультат выполнения
id | carnumber | ts | is_erroneous | is_suspicious | rn ----+-----------+---------------------+--------------+---------------+---- 5 | 564kpa | 2026-03-01 07:50:00 | f | t | 1 1 | 123abc | 2026-03-01 08:00:00 | f | f | 2 9 | 845cko | 2026-03-01 10:01:00 | f | f | 3 6 | 56?kpa | 2026-03-01 13:05:00 | t | f | 4 7 | 565kpa | 2026-03-01 13:50:00 | f | f | 5 10 | 845cko | 2026-03-01 17:16:00 | f | f | 6 8 | 565kpa | 2026-03-01 17:50:00 | f | f | 7 2 | 123abc | 2026-03-01 18:13:00 | f | f | 8 3 | 123abc | 2026-03-02 08:05:00 | f | f | 9 11 | 745cko | 2026-03-02 13:01:00 | f | t | 10 12 | 845c?o | 2026-03-02 17:55:00 | t | f | 11 4 | 123abb | 2026-03-02 18:15:00 | f | t | 12 (12 rows)Основная логика замены — запрос rec. Рекурсивно проходим по журналу и заменяем подозрительные и ошибочные номера.
rec AS ( SELECT 0::BIGINT AS id, 0::BIGINT AS rn, ''::TEXT AS carnumber, '1970-01-01'::TIMESTAMP AS ts, ARRAY[]::TEXT[] AS hist_cars, ARRAY[]::TIMESTAMP[] AS hist_ts UNION ALL SELECT g.id, g.rn, calc.new_carnumber, g.ts, prev.hist_cars || calc.new_carnumber, prev.hist_ts || g.ts FROM rec prev JOIN ordered_gate g ON g.rn = prev.rn + 1 CROSS JOIN LATERAL ( SELECT COALESCE( CASE WHEN g.is_erroneous THEN COALESCE( (SELECT h_car FROM ( SELECT u.h_car, COUNT(*) as f, MIN(u.h_ts) as t FROM UNNEST(prev.hist_cars, prev.hist_ts) AS u(h_car, h_ts) WHERE u.h_car LIKE REPLACE(g.carnumber, '?', '_') GROUP BY u.h_car ) sub ORDER BY f DESC, t ASC LIMIT 1), (SELECT os.carnumber FROM orig_stats os WHERE os.carnumber LIKE REPLACE(g.carnumber, '?', '_') ORDER BY os.freq DESC, os.first_ts ASC LIMIT 1) ) WHEN g.is_suspicious THEN (SELECT h_car FROM ( SELECT u.h_car, COUNT(*) as f, MIN(u.h_ts) as t FROM UNNEST(prev.hist_cars, prev.hist_ts) AS u(h_car, h_ts) WHERE ( (CASE WHEN SUBSTR(g.carnumber,1,1) = SUBSTR(u.h_car,1,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(g.carnumber,2,1) = SUBSTR(u.h_car,2,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(g.carnumber,3,1) = SUBSTR(u.h_car,3,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(g.carnumber,4,1) = SUBSTR(u.h_car,4,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(g.carnumber,5,1) = SUBSTR(u.h_car,5,1) THEN 0 ELSE 1 END) + (CASE WHEN SUBSTR(g.carnumber,6,1) = SUBSTR(u.h_car,6,1) THEN 0 ELSE 1 END) ) <= 1 GROUP BY u.h_car ) sub ORDER BY f DESC, t ASC LIMIT 1) ELSE g.carnumber END, g.carnumber ) AS new_carnumber ) calc )Результат выполнения
id | rn | carnumber | ts | hist_cars | hist_ts ----+----+-----------+---------------------+---------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0 | 0 | | 1970-01-01 00:00:00 | {} | {} 5 | 1 | 564kpa | 2026-03-01 07:50:00 | {564kpa} | {"2026-03-01 07:50:00"} 1 | 2 | 123abc | 2026-03-01 08:00:00 | {564kpa,123abc} | {"2026-03-01 07:50:00","2026-03-01 08:00:00"} 9 | 3 | 845cko | 2026-03-01 10:01:00 | {564kpa,123abc,845cko} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00"} 6 | 4 | 564kpa | 2026-03-01 13:05:00 | {564kpa,123abc,845cko,564kpa} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00"} 7 | 5 | 565kpa | 2026-03-01 13:50:00 | {564kpa,123abc,845cko,564kpa,565kpa} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00"} 10 | 6 | 845cko | 2026-03-01 17:16:00 | {564kpa,123abc,845cko,564kpa,565kpa,845cko} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00","2026-03-01 17:16:00"} 8 | 7 | 565kpa | 2026-03-01 17:50:00 | {564kpa,123abc,845cko,564kpa,565kpa,845cko,565kpa} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00","2026-03-01 17:16:00","2026-03-01 17:50:00"} 2 | 8 | 123abc | 2026-03-01 18:13:00 | {564kpa,123abc,845cko,564kpa,565kpa,845cko,565kpa,123abc} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00","2026-03-01 17:16:00","2026-03-01 17:50:00","2026-03-01 18:13:00"} 3 | 9 | 123abc | 2026-03-02 08:05:00 | {564kpa,123abc,845cko,564kpa,565kpa,845cko,565kpa,123abc,123abc} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00","2026-03-01 17:16:00","2026-03-01 17:50:00","2026-03-01 18:13:00","2026-03-02 08:05:00"} 11 | 10 | 845cko | 2026-03-02 13:01:00 | {564kpa,123abc,845cko,564kpa,565kpa,845cko,565kpa,123abc,123abc,845cko} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00","2026-03-01 17:16:00","2026-03-01 17:50:00","2026-03-01 18:13:00","2026-03-02 08:05:00","2026-03-02 13:01:00"} 12 | 11 | 845cko | 2026-03-02 17:55:00 | {564kpa,123abc,845cko,564kpa,565kpa,845cko,565kpa,123abc,123abc,845cko,845cko} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00","2026-03-01 17:16:00","2026-03-01 17:50:00","2026-03-01 18:13:00","2026-03-02 08:05:00","2026-03-02 13:01:00","2026-03-02 17:55:00"} 4 | 12 | 123abc | 2026-03-02 18:15:00 | {564kpa,123abc,845cko,564kpa,565kpa,845cko,565kpa,123abc,123abc,845cko,845cko,123abc} | {"2026-03-01 07:50:00","2026-03-01 08:00:00","2026-03-01 10:01:00","2026-03-01 13:05:00","2026-03-01 13:50:00","2026-03-01 17:16:00","2026-03-01 17:50:00","2026-03-01 18:13:00","2026-03-02 08:05:00","2026-03-02 13:01:00","2026-03-02 17:55:00","2026-03-02 18:15:00"} (13 rows)Осталось получить итог. Уберём фиктивную строку с rn=0 и оставим только значимые строки журнала.
SELECT id, carnumber, ts FROM rec WHERE rn > 0 ORDER BY id
Решение полностью
WITH RECURSIVE
orig_unique AS (
SELECT carnumber, ts
FROM gate
GROUP BY carnumber, ts
),
orig_correct AS (
SELECT carnumber, ts
FROM orig_unique
WHERE POSITION('?' IN carnumber) = 0
)
,
orig_stats AS (
SELECT carnumber, COUNT(*) AS freq, MIN(ts) AS first_ts
FROM orig_correct
GROUP BY carnumber
)
,
suspicious AS (
SELECT o1.carnumber
FROM orig_stats o1
WHERE o1.freq = 1
AND EXISTS (
SELECT 1 FROM orig_stats o2
WHERE o2.carnumber != o1.carnumber
AND (
(CASE WHEN SUBSTR(o1.carnumber,1,1) = SUBSTR(o2.carnumber,1,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(o1.carnumber,2,1) = SUBSTR(o2.carnumber,2,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(o1.carnumber,3,1) = SUBSTR(o2.carnumber,3,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(o1.carnumber,4,1) = SUBSTR(o2.carnumber,4,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(o1.carnumber,5,1) = SUBSTR(o2.carnumber,5,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(o1.carnumber,6,1) = SUBSTR(o2.carnumber,6,1) THEN 0 ELSE 1 END)
) <= 1
)
)
,
ordered_gate AS (
SELECT id, carnumber, ts,
POSITION('?' IN carnumber) > 0 AS is_erroneous,
EXISTS(SELECT 1 FROM suspicious s WHERE s.carnumber = gate.carnumber) AS is_suspicious,
ROW_NUMBER() OVER (ORDER BY ts, id) AS rn
FROM gate
)
,
rec AS (
SELECT
0::BIGINT AS id,
0::BIGINT AS rn,
''::TEXT AS carnumber,
'1970-01-01'::TIMESTAMP AS ts,
ARRAY[]::TEXT[] AS hist_cars,
ARRAY[]::TIMESTAMP[] AS hist_ts
UNION ALL
SELECT
g.id, g.rn, calc.new_carnumber, g.ts,
prev.hist_cars || calc.new_carnumber,
prev.hist_ts || g.ts
FROM rec prev
JOIN ordered_gate g ON g.rn = prev.rn + 1
CROSS JOIN LATERAL (
SELECT COALESCE(
CASE
WHEN g.is_erroneous THEN
COALESCE(
(SELECT h_car FROM (
SELECT u.h_car, COUNT(*) as f, MIN(u.h_ts) as t
FROM UNNEST(prev.hist_cars, prev.hist_ts) AS u(h_car, h_ts)
WHERE u.h_car LIKE REPLACE(g.carnumber, '?', '_')
GROUP BY u.h_car
) sub ORDER BY f DESC, t ASC LIMIT 1),
(SELECT os.carnumber FROM orig_stats os
WHERE os.carnumber LIKE REPLACE(g.carnumber, '?', '_')
ORDER BY os.freq DESC, os.first_ts ASC LIMIT 1)
)
WHEN g.is_suspicious THEN
(SELECT h_car FROM (
SELECT u.h_car, COUNT(*) as f, MIN(u.h_ts) as t
FROM UNNEST(prev.hist_cars, prev.hist_ts) AS u(h_car, h_ts)
WHERE (
(CASE WHEN SUBSTR(g.carnumber,1,1) = SUBSTR(u.h_car,1,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(g.carnumber,2,1) = SUBSTR(u.h_car,2,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(g.carnumber,3,1) = SUBSTR(u.h_car,3,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(g.carnumber,4,1) = SUBSTR(u.h_car,4,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(g.carnumber,5,1) = SUBSTR(u.h_car,5,1) THEN 0 ELSE 1 END) +
(CASE WHEN SUBSTR(g.carnumber,6,1) = SUBSTR(u.h_car,6,1) THEN 0 ELSE 1 END)
) <= 1
GROUP BY u.h_car
) sub ORDER BY f DESC, t ASC LIMIT 1)
ELSE g.carnumber
END,
g.carnumber
) AS new_carnumber
) calc
)
SELECT id, carnumber, ts
FROM rec
WHERE rn > 0
ORDER BY id;Результат вывода запроса:
id | carnumber | ts
----+-----------+---------------------
1 | 123abc | 2026-03-01 08:00:00
2 | 123abc | 2026-03-01 18:13:00
3 | 123abc | 2026-03-02 08:05:00
4 | 123abc | 2026-03-02 18:15:00
5 | 564kpa | 2026-03-01 07:50:00
6 | 564kpa | 2026-03-01 13:05:00
7 | 565kpa | 2026-03-01 13:50:00
8 | 565kpa | 2026-03-01 17:50:00
9 | 845cko | 2026-03-01 10:01:00
10 | 845cko | 2026-03-01 17:16:00
11 | 845cko | 2026-03-02 13:01:00
12 | 845cko | 2026-03-02 17:55:00
(12 rows)Задача 3: Свободное место на парковке
Условие
У организации имеется парковка с ограниченным количеством мест. Для въезда и выезда используется один общий шлагбаум. Рядом с ним установлена камера с системой распознавания автомобильных номеров. Камера фиксирует как въезд, так и выезд автомобиля, сохраняя только распознанный номер и отметку времени. В журнале могут присутствовать повторяющиеся записи.
В предыдущей задаче вы очистили журнал шлагбаума парковки. То же самое проделал и программист Василий. Теперь у него тоже есть запрос, получающий исправленный журнал.
Программист Василий едет на в офис на своём автомобиле и, подъезжая к парковке, хочет узнать, есть ли на ней свободные места. Количество мест на парковке, а также дата и время, когда Василий едет на работу, задаются параметрами.
Вам необходимо помочь Василию и сделать запрос, который бы выводил количество автомобилей на парковке в момент запроса, а также количество свободных мест или строку «нет». Если количество машин на парковке превышает количество парковочных мест, запрос должен вывести «ошибка» в поле «Свободно мест».
Для регистрации въездов и выездов в системе создана таблица:
create table gate (
id bigserial primary key, -- идентификатор записи журнала
carnumber varchar(6) not null, -- автомобильный номер
ts timestamp not null -- временная метка
);Для задания количества мест на парковке, а также даты и времени запроса используются параметры:
gate.number – количество мест на парковке
gate.ts – дата и время запросаПример
Для следующих входных данных:
insert into gate(carnumber,ts) values ('123abc','2026-03-01 08:00:00');
insert into gate(carnumber,ts) values ('123abc','2026-03-01 18:13:00');
insert into gate(carnumber,ts) values ('123abc','2026-03-02 08:05:00');
insert into gate(carnumber,ts) values ('123abb','2026-03-02 18:15:00');
insert into gate(carnumber,ts) values ('564kpa','2026-03-01 07:50:00');
insert into gate(carnumber,ts) values ('56?kpa','2026-03-01 13:05:00');
insert into gate(carnumber,ts) values ('565kpa','2026-03-01 13:50:00');
insert into gate(carnumber,ts) values ('565kpa','2026-03-01 17:50:00');
insert into gate(carnumber,ts) values ('845cko','2026-03-01 10:01:00');
insert into gate(carnumber,ts) values ('845cko','2026-03-01 17:16:00');
insert into gate(carnumber,ts) values ('745cko','2026-03-02 13:01:00');
insert into gate(carnumber,ts) values ('845c?o','2026-03-02 17:55:00');и параметров:
set gate.number=3;
set gate.ts='2026-03-02 12:05:00';Результат:
На стоянке авто | Свободно мест
-----------------+---------------
1 | 2
(1 row)Разбор решения
Задача — прямое продолжение предыдущей. По сути, это была одна задача, которую разделили на две логические части. Поэтому в первой части требовалось сохранить дубликаты строк в журнале, заменив только подозрительные и ошибочные номера. Теперь же, имея исправленный журнал, нужно ответить на вопрос: сколько машин находится на парковке в конкретный момент времени?
От журнала к интервалам
В исходном журнале камера не фиксирует тип события, въезд это или выезд. Есть только номер и временнáя метка. Логика определения статуса машины держится на простом правиле:
первое появление номера — машина заехала на парковку;
второе — выехала.
Весь временной интервал между этими двумя событиями машина находится на парковке.
Однако в журнале могут присутствовать дубликаты — строки с одинаковым номером и одинаковой временной меткой. Если их оставить, правило ломается. Представьте: машина заехала, а камера записала это дважды подряд. Формально получаются две строки с одним временем — «въезд и сразу выезд», что физически невозможно.
Поэтому перед подсчётом дубликаты необходимо убрать. В отличие от предыдущей задачи, где мы сохраняли их как часть исходных данных, здесь они мешают корректно определить состояние парковки. Убираем строки, у которых (carnumber, ts) совпадает с предыдущей записью для того же номера.
Построение интервалов
Логику «нечётная запись — въезд, чётная — выезд» удобно оформить путём построения интервалов пребывания каждой машины на парковке. Это нагляднее, чем манипуляции с чётностью, и лучше соответствует семантике задачи. Хотя, надо заметить, многие участники определяли, находится машина на парковке или нет, как раз через чётность/нечётность порядкового номера временнóй метки. И такой подход тоже рабочий.
После удаления дубликатов записи каждого номера идут в хронологическом порядке и гарантированно чередуются: въезд, выезд, въезд, выезд… Нумеруем их по порядку и формируем пары:
нечётная запись (1, 3, 5…) — начало интервала;
следующая за ней чётная (2, 4, 6…) — конец интервала.
Если у номера нечётное количество записей, последний интервал остаётся открытым: машина заехала, но ещё не выехала.
Дальше всё просто: остаётся только найти все интервалы, пересекающиеся с заданной временной меткой, и посчитать, для скольких машин такое пересечение есть. Это и будет количество автомобилей на парковке.
Крайние случаи
Нужно не забыть про граничные ситуации. Если временнáя метка находится раньше всех записей в журнале или позже всех, парковка пуста, машин нет.
Также количество автомобилей на парковке может превышать количество мест, в условии задачи это оговорено явно. Такое возможно, если из-за ошибок распознавания разные машины с похожими номерами были исправлены на один и тот же корректный номер, и теперь их интервалы накладываются друг на друга. В этом случае в поле «Свободно мест» нужно вывести «Ошибка».
Разбор решения участника
Перейдём к рассмотрению решения, представленного конкурсантом с идентификатором 45533. Первую часть запроса, отвечающую за очистку журнала от ошибочных и подозрительных номеров, рассматривать не будем, она разобрана в решении предыдущей задачи. Начнём с части, где выполняется дедупликация и дальнейшее построение интервалов.
Получим исходные данные из переменных для использования в запросах. Именно в этом месте было много ошибок у конкурсантов, почему-то с такой простой задачей они не справились. При получении сразу делаем проверку на корректность входных данных.
select case when current_setting('gate.number', true) ~ '^\d+$' then current_setting('gate.number')::int end max_slot, case when current_setting('gate.ts', true) ~ '^\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}$' then current_setting('gate.ts', true)::timestamp end target_tsРезультат
max_slot | target_ts ----------+--------------------- 3 | 2026-03-02 12:05:00 (1 row)Запрос flagged_data маркирование въездов и выездов для данных без дубликатов
select carnumber, ts, case row_number() over (partition by carnumber order by ts) % 2 when 1 then 1 else -1 end io_flag from result_2ndРезультат
carnumber | ts | io_flag -----------+---------------------+--------- 123abc | 2026-03-01 08:00:00 | 1 123abc | 2026-03-01 18:13:00 | -1 123abc | 2026-03-02 08:05:00 | 1 123abc | 2026-03-02 18:15:00 | -1 564kpa | 2026-03-01 07:50:00 | 1 564kpa | 2026-03-01 13:05:00 | -1 565kpa | 2026-03-01 13:50:00 | 1 565kpa | 2026-03-01 17:50:00 | -1 845cko | 2026-03-01 10:01:00 | 1 845cko | 2026-03-01 17:16:00 | -1 845cko | 2026-03-02 13:01:00 | 1 845cko | 2026-03-02 17:55:00 | -1 (12 rows)В parking_timeline формируем интервалы занятости мест парковки и определяем количество оставшихся мест.
select carnumber, tsrange(ts, lead(ts) over ts_order, '[)') tsrange, max_slot - sum(io_flag) over ts_order remain from flagged_data join prepare_input on true window ts_order as (order by ts)Результат
carnumber | tsrange | remain -----------+-----------------------------------------------+-------- 564kpa | ["2026-03-01 07:50:00","2026-03-01 08:00:00") | 2 123abc | ["2026-03-01 08:00:00","2026-03-01 10:01:00") | 1 845cko | ["2026-03-01 10:01:00","2026-03-01 13:05:00") | 0 564kpa | ["2026-03-01 13:05:00","2026-03-01 13:50:00") | 1 565kpa | ["2026-03-01 13:50:00","2026-03-01 17:16:00") | 0 845cko | ["2026-03-01 17:16:00","2026-03-01 17:50:00") | 1 565kpa | ["2026-03-01 17:50:00","2026-03-01 18:13:00") | 2 123abc | ["2026-03-01 18:13:00","2026-03-02 08:05:00") | 3 123abc | ["2026-03-02 08:05:00","2026-03-02 13:01:00") | 2 845cko | ["2026-03-02 13:01:00","2026-03-02 17:55:00") | 1 845cko | ["2026-03-02 17:55:00","2026-03-02 18:15:00") | 2 123abc | ["2026-03-02 18:15:00",) | 3 (12 rows)Формируем окончательный результат с обработкой крайних случаев и ошибочных ситуаций. Проверяем пересечение временнóй метки из параметров с построенными интервалами.
select max_slot - coalesce(remain, max_slot) "На стоянке авто", case when coalesce(remain, max_slot) < 0 then 'ошибка' when coalesce(remain, max_slot) = 0 then 'нет' else coalesce(remain, max_slot)::text end "Свободно мест" from prepare_input left join parking_timeline on tsrange @> target_ts
Решение полностью
with remove_duplicate as (
select distinct carnumber, ts
from gate
)
,input_data as (
select t1.carnumber, t1.ts,
case when strpos(t1.carnumber, '?') > 0
then 1
when count(t1.carnumber) over (partition by t1.carnumber) = 1
and exists(select 1
from remove_duplicate t2
where
strpos(t2.carnumber, '?') <= 0
and (select sum((substring(t1.carnumber, i, 1) != substring(t2.carnumber, i, 1))::int)
from generate_series(1, 6) as g(i)) = 1
and t1.ts > t2.ts
)
then 2
else 0 end datatype
from remove_duplicate t1
)
,processed_data as (
select t1.carnumber, t1.ts, t1.datatype, t2.carnumber candidate,
t2.ts - t1.ts delta,
count(t2.carnumber)
filter (where t2.ts - t1.ts < interval '0')
over (
partition by t1.carnumber, t1.ts, t2.carnumber
) prev_cnt,
count(t2.carnumber)
filter (where t2.ts - t1.ts > interval '0')
over (
partition by t1.carnumber, t1.ts, t2.carnumber
) next_cnt
from input_data t1
left join input_data t2
on t1.carnumber != t2.carnumber
and case when t1.datatype = 1 then t2.carnumber LIKE replace(t1.carnumber, '?', '_')
when t1.datatype = 2 then (select sum((substring(t1.carnumber, i, 1) <> substring(t2.carnumber, i, 1))::int)
from generate_series(1, 6) as g(i)) = 1 end
where t1.datatype != 0 and t2.datatype = 0
)
,result_2nd as (
select distinct
coalesce (first_value(candidate) over (
partition by carnumber, ts
order by
prev_cnt desc,
case when delta < interval '0' then delta else null end,
next_cnt desc,
case when delta > interval '0' then delta else null end), carnumber) carnumber,
ts
from processed_data
right join remove_duplicate using(carnumber, ts)
)
,prepare_input as (
select case
when current_setting('gate.number', true) ~ '^\d+$'
then current_setting('gate.number')::int
end max_slot,
case
when current_setting('gate.ts', true) ~
'^\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}$'
then current_setting('gate.ts', true)::timestamp end target_ts
)
,flagged_data as (
select carnumber, ts,
case row_number() over (partition by carnumber order by ts) % 2
when 1 then 1 else -1 end io_flag
from result_2nd
)
,parking_timeline as(
select carnumber,
tsrange(ts, lead(ts) over ts_order, '[)') tsrange,
max_slot - sum(io_flag) over ts_order remain
from flagged_data
join prepare_input on true
window ts_order as (order by ts)
)
select
max_slot - coalesce(remain, max_slot) "На стоянке авто",
case
when coalesce(remain, max_slot) < 0 then 'ошибка'
when coalesce(remain, max_slot) = 0 then 'нет'
else coalesce(remain, max_slot)::text end "Свободно мест"
from prepare_input
left join parking_timeline on tsrange @> target_ts;Результат запроса:
На стоянке авто | Свободно мест
-----------------+---------------
1 | 2
(1 row)Задача 4: Турнирная таблица НХЛ
Условие
Незнайка и Гунька основали Настольную Хоккейную Лигу (НХЛ). Для детального учёта результатов Знайка создал таблицу scores, в которую заносится счёт отдельно за каждый этап матча: основное время, овертайм и серию послематчевых бросков (буллитов).
Таблица создана следующей командой:
create table scores
( idscore serial primary key,-- идентификатор матча
team1 text not null, -- название первой команды
team2 text not null, -- название второй команды
g1 int not null, -- количество голов, забитых первой командой в основное время
g2 int not null, -- количество голов, забитых второй командой в основное время
ot1 int, -- количество голов, забитых первой командой в овертайме
ot2 int, -- количество голов, забитых второй командой в овертайме
so1 int, -- количество буллитов, забитых первой командой
so2 int -- количество буллитов, забитых второй командой
);Коротышки аккуратно вели таблицу и заносили в неё результаты всех матчей. В таблицу заносились данные о количестве голов на каждом этапе игры.
Структура матча и фиксация результата
Матч состоит из трёх периодов (основное время).
Если по итогам основного времени зафиксирована ничья, то назначается овертайм, ограниченный по времени, который продолжается до первого гола («золотой гол») или окончания времени.
Если овертайм не выявил победителя, проводится серия послематчевых бросков (буллитов). Серия длится до первого гола при равном количестве бросков.
Финальный счёт матча формируется так:
Голы, забитые в основное время и овертайме, суммируются.
Победа в серии буллитов добавляет 1 гол к общему счёту победившей команды. Этот гол учитывается только в финальном результате и не относится к этапам игры.
Система начисления очков
На основании результата матча каждой команде начисляются очки, сумма которых будет основным критерием при построении рейтинга команд.
Очки за матч определяются по следующим правилам:
Победитель получает 2 очка.
Проигравший в основное время получает 0 очков.
Проигравший в овертайме или по серии послематчевых буллитов получает 1 очко.
Определение места в итоговом рейтинге
Главный критерий — сумма набранных за все матчи очков.
В случае равенства очков места между командами определяются последовательно по следующим правилам:
Личные встречи: большее количество очков в матчах между командами с равным количеством очков.
Разность голов: наибольшая разница забитых и пропущенных голов (по финальному счёту матчей) в матчах между командами с равным количеством очков.
Общая результативность: большее суммарное количество забитых голов во всех матчах чемпионата (по финальному счёту).
Количество побед: большее число побед (любого типа) во всех матчах.
Алфавитный порядок: команда, чьё название идет первым по алфавиту (от А к Я), получает более высокое место.
Помогите коротышкам написать запрос для получения итоговой таблицы с результатами и местами команд.
В итоговой таблице должны быть следующие поля:
Team — название команды;
Games — общее количество игр;
Points — набранные очки во всех играх;
Wins — игры, где команда победила;
Losses — игры, где команда проиграла;
Overtime losses — игры, где команда проиграла в добавленное время или в серии послематчевых бросков;
Goals for — количество забитых голов во всех встречах;
Goals against — количество пропущенных голов во всех встречах;
goal differential — разность между забитыми и пропущенными голами во всех встречах;
rn — итоговое место команды.
Пример
Для следующих входных данных:
insert into scores(team1,team2,g1,g2) values ('Незнайка','Гунька',3,5);
insert into scores(team1,team2,g1,g2) values ('Гунька','Незнайка',1,4);
insert into scores(team1,team2,g1,g2) values ('Незнайка','Знайка',3,2);
insert into scores(team1,team2,g1,g2,ot1,ot2) values ('Знайка','Незнайка',1,1,0,1);
insert into scores(team1,team2,g1,g2) values ('Незнайка','Сиропчик',5,1);
insert into scores(team1,team2,g1,g2) values ('Сиропчик','Незнайка',3,4);
insert into scores(team1,team2,g1,g2,ot1,ot2,so1,so2) values ('Гунька','Знайка',4,4,0,0,2,4);
insert into scores(team1,team2,g1,g2,ot1,ot2) values ('Знайка','Гунька',2,2,1,0);
insert into scores(team1,team2,g1,g2,ot1,ot2) values ('Гунька','Сиропчик',3,3,0,1);
insert into scores(team1,team2,g1,g2) values ('Сиропчик','Гунька',3,4);
insert into scores(team1,team2,g1,g2,ot1,ot2,so1,so2) values ('Знайка','Сиропчик',2,2,0,0,3,1);
insert into scores(team1,team2,g1,g2) values ('Сиропчик','Знайка',3,2);Результат:
team | games | points | wins | losses | overtime losses | goals for | goals against | goal differential | rn
----------+-------+--------+------+--------+-----------------+-----------+---------------+-------------------+----
Незнайка | 6 | 10 | 5 | 1 | 0 | 21 | 13 | 8 | 1
Знайка | 6 | 7 | 3 | 2 | 1 | 16 | 16 | 0 | 2
Гунька | 6 | 7 | 2 | 1 | 3 | 19 | 22 | -3 | 3
Сиропчик | 6 | 5 | 2 | 3 | 1 | 16 | 21 | -5 | 4
(4 rows)Разбор решения
Формализуем правила:
Это задача на использование аналитических функций и ранжирования с разными критериями.
Следует обратить внимание, что каждая игра в итоговой таблице записана одной строкой. Команды всегда в полях team1 и team2. Чтобы получить статистику для каждой команды независимо от того, где она записана, нужно «развернуть» каждую строку в две: одну — для team1, другую — для team2.
Счёт матча
Главный подводный камень задачи — нельзя просто сложить g1 + ot1 + so1 и получить финальный счёт. По условию:
Голы основного времени (g1, g2) и овертайма (ot1, ot2) суммируются.
Буллиты (so1, so2) не суммируются в голы. Победа в серии буллитов добавляет ровно 1 гол к финальному счёту победившей команды.
Это означает, что при вычислении забитых и пропущенных голов (Goals for, Goals against) нужно считать голы этапов отдельно, а буллитный гол добавлять как +1 победителю серии. Например, если so1 = 3 и so2 = 1, команда 1 получает +1 гол, а команда 2 — 0 голов к финальному счёту, несмотря на то что реализовала 1 бросок.
Определение исхода матча
Для начисления очков нужно понять, как именно завершилась игра:
Победа в основное время: g1 != g2. Победитель получает 2 очка, проигравший — 0.
Победа в овертайме: g1 = g2 и ot1 != ot2. Победитель — 2 очка, проигравший — 1 очко (Overtime loss).
Победа по буллитам: g1 = g2 и ot1 = ot2 и so1 != so2. Победитель — 2 очка, проигравший — 1 очко (тоже Overtime loss).
Ничьей быть не может: регламент гарантирует выявление победителя.
Поля ot1, ot2, so1, so2 могут быть NULL — это означает, что до соответствующего этапа матч не дошёл. В таких случаях NULL нужно трактовать как 0 при сравнении, но не подменять им реальное отсутствие этапа.
Два типа поражений
В выводе нужны два разных поля:
Losses — поражения в основное время (0 очков);
Overtime losses — поражения в овертайме или по буллитам (1 очко).
Их нужно считать раздельно.
Многоступенчатое ранжирование
Критерии ранжирования применяются последовательно. Только если команды равны по первому критерию, переходят ко второму и так далее. Полный список:
Сумма набранных очков.
Личные встречи: больше очков в матчах между собой.
Разность голов в личных встречах.
Общая результативность: больше забитых голов во всех матчах.
Количество побед (любого типа).
Алфавитный порядок названий.
Самые сложные для реализации — критерии личных встреч (второй и третий в списке). Они требуют пересчёта очков и разности голов только в матчах между командами, имеющими равные общие очки. Это значит, что сначала нужно посчитать общие очки, выявить группы с равенством, а затем внутри каждой группы пересчитать очки и разность по личным встречам.
Разбор решения участника
Перейдём к рассмотрению оригинального решения конкурсанта с идентификатором 45533. В нём запрос работает над данными, которые предварительно собираются в json. Это используется для ранжирования команд с одинаковым количеством очков, когда необходимо смотреть личные встречи.
Запрос match_meta рассчитывает исходные данные по очкам и голам:
select team1, team2, case when g1 > g2 then 2 when g1 < g2 then 0 when coalesce(ot1, 0) > coalesce(ot2, 0) then 2 when coalesce(ot1, 0) < coalesce(ot2, 0) then 1 when coalesce(so1, 0) > coalesce(so2, 0) then 2 when coalesce(so1, 0) < coalesce(so2, 0) then 1 end as point1, g1 + coalesce(ot1, 0) + case when coalesce(so1, 0) > coalesce(so2, 0) then 1 else 0 end as goal1, case when g2 > g1 then 2 when g2 < g1 then 0 when coalesce(ot2, 0) > coalesce(ot1, 0) then 2 when coalesce(ot2, 0) < coalesce(ot1, 0) then 1 when coalesce(so2, 0) > coalesce(so1, 0) then 2 when coalesce(so2, 0) < coalesce(so1, 0) then 1 end as point2, g2 + coalesce(ot2, 0) + case when coalesce(so2, 0) > coalesce(so1, 0) then 1 else 0 end as goal2 from scoresРезультат
team1 | team2 | point1 | goal1 | point2 | goal2 ----------+----------+--------+-------+--------+------- Незнайка | Гунька | 0 | 3 | 2 | 5 Гунька | Незнайка | 0 | 1 | 2 | 4 Незнайка | Знайка | 2 | 3 | 0 | 2 Знайка | Незнайка | 1 | 1 | 2 | 2 Незнайка | Сиропчик | 2 | 5 | 0 | 1 Сиропчик | Незнайка | 0 | 3 | 2 | 4 Гунька | Знайка | 1 | 4 | 2 | 5 Знайка | Гунька | 2 | 3 | 1 | 2 Гунька | Сиропчик | 1 | 3 | 2 | 4 Сиропчик | Гунька | 0 | 3 | 2 | 4 Знайка | Сиропчик | 2 | 3 | 1 | 2 Сиропчик | Знайка | 2 | 3 | 0 | 2 (12 rows)В запросе metadata упаковываем данные каждой команды в jsonb-массив:
select jsonb_build_array( jsonb_build_object( 'team', team1, 'point', point1, 'goal', goal1, 'goal_diff', goal1 - goal2 ), jsonb_build_object( 'team', team2, 'point', point2, 'goal', goal2, 'goal_diff', goal2 - goal1 ) ) as meta_json from match_metaРезультат
meta_json ----------------------------------------------------------------------------------------------------------------------------- [{"goal": 3, "team": "Незнайка", "point": 0, "goal_diff": -2}, {"goal": 5, "team": "Гунька", "point": 2, "goal_diff": 2}] [{"goal": 1, "team": "Гунька", "point": 0, "goal_diff": -3}, {"goal": 4, "team": "Незнайка", "point": 2, "goal_diff": 3}] [{"goal": 3, "team": "Незнайка", "point": 2, "goal_diff": 1}, {"goal": 2, "team": "Знайка", "point": 0, "goal_diff": -1}] [{"goal": 1, "team": "Знайка", "point": 1, "goal_diff": -1}, {"goal": 2, "team": "Незнайка", "point": 2, "goal_diff": 1}] [{"goal": 5, "team": "Незнайка", "point": 2, "goal_diff": 4}, {"goal": 1, "team": "Сиропчик", "point": 0, "goal_diff": -4}] [{"goal": 3, "team": "Сиропчик", "point": 0, "goal_diff": -1}, {"goal": 4, "team": "Незнайка", "point": 2, "goal_diff": 1}] [{"goal": 4, "team": "Гунька", "point": 1, "goal_diff": -1}, {"goal": 5, "team": "Знайка", "point": 2, "goal_diff": 1}] [{"goal": 3, "team": "Знайка", "point": 2, "goal_diff": 1}, {"goal": 2, "team": "Гунька", "point": 1, "goal_diff": -1}] [{"goal": 3, "team": "Гунька", "point": 1, "goal_diff": -1}, {"goal": 4, "team": "Сиропчик", "point": 2, "goal_diff": 1}] [{"goal": 3, "team": "Сиропчик", "point": 0, "goal_diff": -1}, {"goal": 4, "team": "Гунька", "point": 2, "goal_diff": 1}] [{"goal": 3, "team": "Знайка", "point": 2, "goal_diff": 1}, {"goal": 2, "team": "Сиропчик", "point": 1, "goal_diff": -1}] [{"goal": 3, "team": "Сиропчик", "point": 2, "goal_diff": 1}, {"goal": 2, "team": "Знайка", "point": 0, "goal_diff": -1}] (12 rows)В запросе earned_scores считаем очки для каждой команды:
select distinct sum((value ->> 'point')::int) total_point, array_agg(value ->> 'team') over (partition by sum((value ->> 'point')::int)) teams from metadata m cross join lateral jsonb_array_elements(m.meta_json) group by value ->> 'team'Результат
total_point | teams -------------+----------------- 5 | {Сиропчик} 7 | {Знайка,Гунька} 10 | {Незнайка} (3 rows)Запрос duel_info получает данные по командам в группе с одинаковым количеством очков:
select distinct total_point, coalesce(value ->> 'team', teams[1]) team, sum((value ->>'point')::int) over byteam point_between, sum((value ->> 'goal_diff')::int) over byteam maxdiff_betwen from earned_scores left join metadata m1 on array[(meta_json -> 0) ->> 'team', (meta_json -> 1) ->> 'team'] <@ teams left join lateral jsonb_array_elements(meta_json) as e(value) on true window byteam as (partition by value ->> 'team')Результат
total_point | team | point_between | maxdiff_betwen -------------+----------+---------------+---------------- 5 | Сиропчик | | 10 | Незнайка | | 7 | Гунька | 2 | -2 7 | Знайка | 4 | 2 (4 rows)Итоговый запрос — получение всех данных с ранжированием команд:
select Team, count(*) Games, total_point Points, count(*) filter (where (value ->>'point')::int = 2) Wins, count(*) filter (where (value ->>'point')::int = 0) Losses, count(*) filter (where (value ->>'point')::int = 1) "overtime losses", sum((value ->> 'goal')::int) "goals for", sum((value ->> 'goal')::int - (value -> 'goal_diff')::int) "goals against", sum((value ->> 'goal_diff')::int) "goal differential", dense_rank() over (order by total_point desc, point_between desc, maxdiff_betwen desc, sum((value ->> 'goal')::int) desc, count(*) filter (where (value ->> 'point')::int = 2) desc, team asc) rn from duel_info left join metadata m1 on array[(meta_json -> 0) ->> 'team', (meta_json -> 1) ->> 'team'] @> array[team] left join lateral jsonb_array_elements(meta_json) as e(value) on true where value ->> 'team' = team group by total_point, team, point_between, maxdiff_betwen
Решение полностью:
with match_meta as (
select
team1,
team2,
case
when g1 > g2 then 2
when g1 < g2 then 0
when coalesce(ot1, 0) > coalesce(ot2, 0) then 2
when coalesce(ot1, 0) < coalesce(ot2, 0) then 1
when coalesce(so1, 0) > coalesce(so2, 0) then 2
when coalesce(so1, 0) < coalesce(so2, 0) then 1
end as point1,
g1
+ coalesce(ot1, 0)
+ case
when coalesce(so1, 0) > coalesce(so2, 0) then 1
else 0
end as goal1,
case
when g2 > g1 then 2
when g2 < g1 then 0
when coalesce(ot2, 0) > coalesce(ot1, 0) then 2
when coalesce(ot2, 0) < coalesce(ot1, 0) then 1
when coalesce(so2, 0) > coalesce(so1, 0) then 2
when coalesce(so2, 0) < coalesce(so1, 0) then 1
end as point2,
g2
+ coalesce(ot2, 0)
+ case
when coalesce(so2, 0) > coalesce(so1, 0) then 1
else 0
end as goal2
from scores
)
,
metadata as (
select
jsonb_build_array(
jsonb_build_object(
'team', team1,
'point', point1,
'goal', goal1,
'goal_diff', goal1 - goal2
),
jsonb_build_object(
'team', team2,
'point', point2,
'goal', goal2,
'goal_diff', goal2 - goal1
)
) as meta_json
from match_meta
)
,earned_scores as
(
select distinct
sum((value ->> 'point')::int) total_point,
array_agg(value ->> 'team') over (partition by sum((value ->> 'point')::int)) teams
from metadata m
cross join lateral jsonb_array_elements(m.meta_json)
group by value ->> 'team'
)
,duel_info as (
select distinct total_point,
coalesce(value ->> 'team', teams[1]) team,
sum((value ->>'point')::int) over byteam point_between,
sum((value ->> 'goal_diff')::int) over byteam maxdiff_betwen
from earned_scores
left join metadata m1 on array[(meta_json -> 0) ->> 'team', (meta_json -> 1) ->> 'team'] <@ teams
left join lateral jsonb_array_elements(meta_json) as e(value) on true
window byteam as (partition by value ->> 'team')
)
select
Team, count(*) Games,
total_point Points,
count(*) filter (where (value ->>'point')::int = 2) Wins,
count(*) filter (where (value ->>'point')::int = 0) Losses,
count(*) filter (where (value ->>'point')::int = 1) "overtime losses",
sum((value ->> 'goal')::int) "goals for",
sum((value ->> 'goal')::int - (value -> 'goal_diff')::int) "goals against",
sum((value ->> 'goal_diff')::int) "goal differential",
dense_rank() over
(order by total_point desc,
point_between desc,
maxdiff_betwen desc,
sum((value ->> 'goal')::int) desc,
count(*) filter (where (value ->> 'point')::int = 2) desc,
team asc) rn
from duel_info
left join metadata m1 on array[(meta_json -> 0) ->> 'team', (meta_json -> 1) ->> 'team'] @> array[team]
left join lateral jsonb_array_elements(meta_json) as e(value) on true
where value ->> 'team' = team
group by total_point, team, point_between, maxdiff_betwen;Результат
team | games | points | wins | losses | overtime losses | goals for | goals against | goal differential | rn
----------+-------+--------+------+--------+-----------------+-----------+---------------+-------------------+----
Незнайка | 6 | 10 | 5 | 1 | 0 | 21 | 13 | 8 | 1
Знайка | 6 | 7 | 3 | 2 | 1 | 16 | 16 | 0 | 2
Гунька | 6 | 7 | 2 | 1 | 3 | 19 | 22 | -3 | 3
Сиропчик | 6 | 5 | 2 | 3 | 1 | 16 | 21 | -5 | 4
(4 rows)Задача 5: Мобильная сеть
Условие
Знайка с друзьями строят сотовую связь. Вышки сотовой связи уже установлены. Необходимо подключить их к электроэнергии. У коротышек есть карта, которая представляет собой прямоугольную сетку, на которую нанесены вышки сотовой связи и болота. Вам необходимо найти все возможные расположения трансформаторов рядом с вышками сотовой связи.
Правила расположения трансформаторов:
Рядом (по горизонтали, вертикали или диагонали) с каждой вышкой сотовой связи должен быть ровно один трансформатор.
Трансформатор не может находится рядом (по горизонтали, вертикали или диагонали) с другим трансформатором.
Трансформатор не может располагаться в болоте.
Так как установка трансформаторов может помешать сезонному перемещению кузнечиков, имеется ограничение на количество трансформаторов для каждой строки и столбца исходной карты.
Данные хранятся в следующих таблицах:
Таблица objects:
create table objects(
objecttype text not null
check (objecttype in ('T','#')), -- тип объекта T - вышка, # - болото
r int, -- строка
c int, -- столбец
primary key (r,c)
);В таблице хранится координаты объектов: T — вышка, # — болото.
Таблица rows_limit:
create table rows_limit(
r int primary key, -- строка
lim int not null -- количество трансформаторов
);В таблице хранятся ограничения по количеству трансформаторов на каждой строке карты.
Таблица cols_limit:
create table cols_limit(
c int primary key, -- столбец
lim int not null -- количество трансформаторов
);В таблице хранятся ограничения по количеству трансформаторов в каждом столбце карты.
Вам необходимо получить все возможные размещения трансформаторов и сформировать прямоугольную карту с нанесёнными на неё трансформаторами (обозначив их буквой X), вышками (T) и болотами (#). Пустые клетки обозначьте буквой «o».
Размер карты определяется на основании исходных данных.
Каждую возможную карту следует вывести в текстовом виде, пронумеровав её строки и сконкатенировав их через запятую. Смотри пример вывода ниже.
Пример
Для следующих входных данных:
insert into objects(objecttype,r,c) values ('T',2,2),('T',2,6),('T',5,3),('T',6,7),('T',8,4),('T',1,4);
insert into objects(objecttype,r,c) values ('#',1,7),('#',2,8),('#',4,3),('#',5,2),('#',6,8),('#',7,6);
insert into rows_limit(r,lim) values (1,1),(2,2),(3,0),(4,1),(5,1),(6,0),(7,1),(8,0);
insert into cols_limit(c,lim) values (1,1),(2,1),(3,0),(4,2),(5,0),(6,0),(7,1),(8,1);Результат:
solution
-----------------------------------------------------------------------------------------
1:XooToo#o,2:oToXoTX#,3:oooooooo,4:oX#ooooo,5:o#TooooX,6:ooooooT#,7:oooXo#oo,8:oooToooo
(1 row)Разбор решения
Формализуем правила
В основе задачи — известная головоломка Tents and Trees («Палатки и деревья») на размещение объектов с ограничениями, переложенная на вышки и трансформаторы: нужно не найти спрятанные объекты, а расставить новые, соблюдая правила соседства и ограничения.
Исходные данные
Прямоугольная сетка, на которой уже размещены два типа объектов:
T — вышка сотовой связи;
# — болото.
Размер сетки явно не задан и определяется по координатам объектов в таблицах как максимальные значения r и c среди всех переданных данных.
Дополнительно заданы ограничения:
для каждой строки — сколько трансформаторов может в ней находиться (rows_limit);
для каждого столбца — сколько трансформаторов может в нём находиться (cols_limit).
Необходимо
Найти все возможные размещения трансформаторов (обозначаются X), удовлетворяющие трём правилам, и вывести каждое решение в виде текстовой карты.
Правила размещения
Правило 1: Рядом с каждой вышкой ровно 1 трансформатор
Находящимися рядом считаются восемь соседних клеток (горизонталь, вертикаль, диагональ). Трансформатор должен быть ровно один — не ноль и не два. Это главное ограничение, связывающее вышки и трансформаторы.
Из этого правила следует важный вывод: трансформаторы можно ставить только в соседних с вышками клетках. Клетка, у которой нет вышек по соседству, никогда не будет содержать трансформатор. Это резко сужает пространство перебора.
Правило 2: Трансформаторы не могут стоять рядом друг с другом
Запрещено любое соседство трансформаторов, включая расположение диагонально. Это дополнительное ограничение совместимости: если выбрана клетка для трансформатора, все восемь её соседей автоматически исключаются из рассмотрения для других трансформаторов.
Правило 3: Трансформатор не может располагаться в болоте
Клетки с # запрещены для размещения. Если вышка окружена болотами так, что для трансформатора не остаётся ни одной допустимой клетки, задача для таких входных данных не имеет решения.
Ограничения по строкам и столбцам
Даже после учёта трёх правил может остаться несколько вариантов размещения. Ограничения rows_limit и cols_limit добивают неоднозначность или, наоборот, отсекают все варианты, если ограничения противоречат правилам соседства.
Важный нюанс: ограничения заданы для строк и столбцов исходной карты, а не для какого-то подмножества. Это означает, что строка с lim = 0 не может содержать ни одного трансформатора. Если в такой строке есть вышка, у которой все соседние клетки находятся в этой же строке — решения нет.
Размер карты и вывод
Размер карты определяется по исходным данным — как прямоугольник от (1,1) до (max_r, max_c). Пустые клетки (не вышка, не болото, не трансформатор) обозначаются символом «o».
Формат вывода: каждая найденная карта — это одна строка, в которой строки пронумерованы и перечислены через запятую. Пример из условия показывает ожидаемый формат.
Особенности
Несколько решений. Условие требует «все возможные размещения». Если решений несколько, вывести нужно все.
Отсутствие решений. При противоречивых входных данных (вышка в окружении болот, нулевое ограничение строки при вышке в этой строке) решений может не быть. Запрос должен корректно отработать и вернуть пустой результат.
Границы карты. Их нужно вычислить, а не брать фиксированными. В примере карта 8×8, но данные могут быть другими.
Нумерация строк в выводе. Формат вывода требует пронумеровать строки карты. Имеется в виду номер строки сетки, а не порядковый номер выводимой строки.
Уникальность трансформаторов. Количество трансформаторов равно количеству вышек, каждой вышке — свой трансформатор. Одна клетка не может обслуживать две вышки.
Разбор решения участника
Рассмотрим решение участника с идентификатором 121097.
Запрос towers получает исходные данные для вышек связи и сразу их нумерует:
select row_number() over (order by o.r, o.c)::int as tid, o.r, o.c from objects o where o.objecttype = 'T'Результат
tid | r | c -----+---+--- 1 | 1 | 4 2 | 2 | 2 3 | 2 | 6 4 | 5 | 3 5 | 6 | 7 6 | 8 | 4 (6 rows)В запросе grid получаем все клетки карты исходя из ограничений для строк и столбцов:
select rl.r, cl.c from rows_limit rl cross join cols_limit clРезультат
В результате может получиться много строк, например в рассматриваемом примере их будет 64, так как поле 8x8. Поэтому покажем результат частично
r | c ---+--- 1 | 1 1 | 2 1 | 3 1 | 4 ... 8 | 7 8 | 8 (64 rows)Запрос candidates. Получаем список возможных размещений трансформаторов, для каждого размещения отмечаем номер вышки связи, которая может использовать данный трансформатор:
select row_number() over (order by g.r, g.c)::int as cid, g.r, g.c, array_agg(t.tid order by t.tid)::int[] as tower_ids from grid g join towers t on abs(t.r - g.r) <= 1 and abs(t.c - g.c) <= 1 left join objects o on o.r = g.r and o.c = g.c where o.r is null group by g.r, g.cРезультат
cid | r | c | tower_ids -----+---+---+----------- 1 | 1 | 1 | {2} 2 | 1 | 2 | {2} 3 | 1 | 3 | {1,2} 4 | 1 | 5 | {1,3} 5 | 1 | 6 | {3} 6 | 2 | 1 | {2} 7 | 2 | 3 | {1,2} 8 | 2 | 4 | {1} 9 | 2 | 5 | {1,3} 10 | 2 | 7 | {3} 11 | 3 | 1 | {2} 12 | 3 | 2 | {2} 13 | 3 | 3 | {2} 14 | 3 | 5 | {3} 15 | 3 | 6 | {3} 16 | 3 | 7 | {3} 17 | 4 | 2 | {4} 18 | 4 | 4 | {4} 19 | 5 | 4 | {4} 20 | 5 | 6 | {5} 21 | 5 | 7 | {5} 22 | 5 | 8 | {5} 23 | 6 | 2 | {4} 24 | 6 | 3 | {4} 25 | 6 | 4 | {4} 26 | 6 | 6 | {5} 27 | 7 | 3 | {6} 28 | 7 | 4 | {6} 29 | 7 | 5 | {6} 30 | 7 | 7 | {5} 31 | 7 | 8 | {5} 32 | 8 | 3 | {6} 33 | 8 | 5 | {6} (33 rows)Рекурсивный запрос search находит вышку сотовой связи с минимальным идентификатором, для которой не определён трансформатор, и просматривает возможные варианты расстановки трансформаторов, проверяя все условия задачи. Таким образом получаем список возможных размещений трансформаторов, не нарушающих условий задачи:
select array[]::int[] as chosen_ids, array[]::int[] as covered_ids union all select s.chosen_ids || c.cid, s.covered_ids || c.tower_ids from search s join lateral ( select min(t.tid)::int as next_tid from towers t where t.tid <> all(s.covered_ids) ) nt on nt.next_tid is not null join candidates c on nt.next_tid = any(c.tower_ids) where not (c.tower_ids && s.covered_ids) and not exists ( select 1 from unnest(s.chosen_ids) as x(cid) join candidates pc on pc.cid = x.cid where abs(pc.r - c.r) <= 1 and abs(pc.c - c.c) <= 1 ) and 1 + ( select count(*) from unnest(s.chosen_ids) as x(cid) join candidates pc on pc.cid = x.cid where pc.r = c.r ) <= ( select rl.lim from rows_limit rl where rl.r = c.r ) and 1 + ( select count(*) from unnest(s.chosen_ids) as x(cid) join candidates pc on pc.cid = x.cid where pc.c = c.c ) <= ( select cl.lim from cols_limit cl where cl.c = c.c )Результат
chosen_ids | covered_ids -------------------+--------------- {} | {} {8} | {1} {8,1} | {1,2} {8,2} | {1,2} {8,6} | {1,2} {8,1,10} | {1,2,3} {8,2,10} | {1,2,3} {8,1,10,17} | {1,2,3,4} {8,1,10,18} | {1,2,3,4} {8,2,10,18} | {1,2,3,4} {8,1,10,19} | {1,2,3,4} {8,2,10,19} | {1,2,3,4} {8,1,10,17,22} | {1,2,3,4,5} {8,1,10,18,22} | {1,2,3,4,5} {8,2,10,18,22} | {1,2,3,4,5} {8,1,10,17,31} | {1,2,3,4,5} {8,1,10,18,31} | {1,2,3,4,5} {8,2,10,18,31} | {1,2,3,4,5} {8,1,10,19,31} | {1,2,3,4,5} {8,2,10,19,31} | {1,2,3,4,5} {8,1,10,17,22,28} | {1,2,3,4,5,6} (21 rows)Запрос solutions оставляет только полные размещения трансформаторов, где их количество совпадает с количеством вышек связи и выполнены все ограничения:
select s.chosen_ids from search s where cardinality(s.covered_ids) = (select count(*) from towers) and not exists ( select 1 from rows_limit rl where rl.lim <> ( select count(*) from unnest(s.chosen_ids) as x(cid) join candidates c on c.cid = x.cid where c.r = rl.r ) ) and not exists ( select 1 from cols_limit cl where cl.lim <> ( select count(*) from unnest(s.chosen_ids) as x(cid) join candidates c on c.cid = x.cid where c.c = cl.c ) )Результат
chosen_ids ------------------- {8,1,10,17,22,28} (1 row)В solution_rows для каждого решения строим строки карты:
select s.chosen_ids, rl.r, rl.r::text || ':' || string_agg( case when exists ( select 1 from unnest(s.chosen_ids) as x(cid) join candidates c on c.cid = x.cid where c.r = rl.r and c.c = cl.c ) then 'X' when exists ( select 1 from objects o where o.r = rl.r and o.c = cl.c and o.objecttype = 'T' ) then 'T' when exists ( select 1 from objects o where o.r = rl.r and o.c = cl.c and o.objecttype = '#' ) then '#' else 'o' end, '' order by cl.c ) as row_txt from solutions s cross join rows_limit rl cross join cols_limit cl group by s.chosen_ids, rl.rРезультат
chosen_ids | r | row_txt -------------------+---+------------ {8,1,10,17,22,28} | 1 | 1:XooToo#o {8,1,10,17,22,28} | 2 | 2:oToXoTX# {8,1,10,17,22,28} | 3 | 3:oooooooo {8,1,10,17,22,28} | 4 | 4:oX#ooooo {8,1,10,17,22,28} | 5 | 5:o#TooooX {8,1,10,17,22,28} | 6 | 6:ooooooT# {8,1,10,17,22,28} | 7 | 7:oooXo#oo {8,1,10,17,22,28} | 8 | 8:oooToooo (8 rows)Осталось собрать одно решение в одну строку:
select string_agg(sr.row_txt, ',' order by sr.r) as solution from solution_rows sr group by sr.chosen_ids order by solution
Решение полностью
with recursive
towers as (
select
row_number() over (order by o.r, o.c)::int as tid,
o.r,
o.c
from objects o
where o.objecttype = 'T'
)
,
grid as (
select
rl.r,
cl.c
from rows_limit rl
cross join cols_limit cl
)
,
candidates as (
select
row_number() over (order by g.r, g.c)::int as cid,
g.r,
g.c,
array_agg(t.tid order by t.tid)::int[] as tower_ids
from grid g
join towers t
on abs(t.r - g.r) <= 1
and abs(t.c - g.c) <= 1
left join objects o
on o.r = g.r
and o.c = g.c
where o.r is null
group by g.r, g.c
)
,
search as (
select
array[]::int[] as chosen_ids,
array[]::int[] as covered_ids
union all
select
s.chosen_ids || c.cid,
s.covered_ids || c.tower_ids
from search s
join lateral (
select min(t.tid)::int as next_tid
from towers t
where t.tid <> all(s.covered_ids)
) nt
on nt.next_tid is not null
join candidates c
on nt.next_tid = any(c.tower_ids)
where not (c.tower_ids && s.covered_ids)
and not exists (
select 1
from unnest(s.chosen_ids) as x(cid)
join candidates pc
on pc.cid = x.cid
where abs(pc.r - c.r) <= 1
and abs(pc.c - c.c) <= 1
)
and 1 + (
select count(*)
from unnest(s.chosen_ids) as x(cid)
join candidates pc
on pc.cid = x.cid
where pc.r = c.r
) <= (
select rl.lim
from rows_limit rl
where rl.r = c.r
)
and 1 + (
select count(*)
from unnest(s.chosen_ids) as x(cid)
join candidates pc
on pc.cid = x.cid
where pc.c = c.c
) <= (
select cl.lim
from cols_limit cl
where cl.c = c.c
)
)
,
solutions as (
select s.chosen_ids
from search s
where cardinality(s.covered_ids) = (select count(*) from towers)
and not exists (
select 1
from rows_limit rl
where rl.lim <> (
select count(*)
from unnest(s.chosen_ids) as x(cid)
join candidates c
on c.cid = x.cid
where c.r = rl.r
)
)
and not exists (
select 1
from cols_limit cl
where cl.lim <> (
select count(*)
from unnest(s.chosen_ids) as x(cid)
join candidates c
on c.cid = x.cid
where c.c = cl.c
)
)
)
,
solution_rows as (
select
s.chosen_ids,
rl.r,
rl.r::text || ':' ||
string_agg(
case
when exists (
select 1
from unnest(s.chosen_ids) as x(cid)
join candidates c
on c.cid = x.cid
where c.r = rl.r
and c.c = cl.c
) then 'X'
when exists (
select 1
from objects o
where o.r = rl.r
and o.c = cl.c
and o.objecttype = 'T'
) then 'T'
when exists (
select 1
from objects o
where o.r = rl.r
and o.c = cl.c
and o.objecttype = '#'
) then '#'
else 'o'
end,
'' order by cl.c
) as row_txt
from solutions s
cross join rows_limit rl
cross join cols_limit cl
group by s.chosen_ids, rl.r
)
select
string_agg(sr.row_txt, ',' order by sr.r) as solution
from solution_rows sr
group by sr.chosen_ids
order by solution;Результат
solution
-----------------------------------------------------------------------------------------
1:XooToo#o,2:oToXoTX#,3:oooooooo,4:oX#ooooo,5:o#TooooX,6:ooooooT#,7:oooXo#oo,8:oooToooo
(1 row)Некоторые итоги
Очень странно, но многие присланные решения не проходили тест из формулировки. Они либо выдавали другое решение, либо вообще не выполнялись, сразу показывали ошибку. В общем, причины разные, но факт, что участники даже не пробовали запускать свои решения. Другого объяснения я не вижу.
Также следует отметить много абсолютно одинаковых решений. Понятно, что сейчас без ИИ никто не будет выполнять такие задачи, но хорошо бы посмотреть на полученный запрос, осмыслить его и, может быть, исправить (ведь он, скорее всего, содержит ошибки и не будет работать).
Порадовало, что есть те, кто решал сам. Такие решения сразу видны, они используют весь арсенал возможностей, которые даёт PostgreSQL: это и использование CTE, и JSON, и запросы lateral, и интервальные типы, и многое другое. Это говорит о глубоких знаниях конкурсантов.
Не знаю, интересно ли было конкурсантам решать задачи, но мы точно получили удовольствие, придумывая задачи и решения к ним.
Ждём вас на следующих наших конкурсах.