«IT-Планета 2024»: задачи второго этапа по PostgreSQL

[MasterMentor]

Оч позитивная новость!

Лайхак участникам конкурсов и олимпиад: просмотр хороших фильмов - отличный способ восстановиться после напряжённой умственной работы.

По теме рекомендую х/ф Телевикторина - Quiz Show (1994) с непревзойдённой игрой

Рэйфа Файнса в главной роли (Лучшие фильмы: Список Шиндлера, Отель «Гранд Будапешт», Английский пациент).

х/ф Телевикторина

И, главное, не отчаивайтесь: не удалось победить в одном конкурсе - смело направляйтесь к другому!

[RedWolf]

Первую задачу можно сделать только с оконными функциями:

-- Выбираем записи, где все головы спят, event_time - начало интервала сна
-- Конец интервала - следующая с точки зрения event_time запись для любой головы.
-- Опять таки, мы можем так делать, потому что мы избавились от дубликатов заранее,
-- так что следующая запись будет выходом из сна
select event_time, next_event_time
from (
     -- Считаем кумулятивную сумму по head_state (-1 - спим, 1 - не спим). 
     -- Если у нас набралось -3 для данной строки, то все головы спят.
     -- Мы так можем делать, потому что мы избавились от дубликатов в первом подзапросе
    select event_time, sum(case when head_state = false then -1 else 1 end) over(order by event_time) status, 
           lead(event_time) over(order by event_time) next_event_time
    from (
      -- избавляемся от событий, дублирующих предыдущие события
      select * from (
        select *, lag(head_state, -1) over(partition by head_id order by event_time desc) prev_state 
        from cerberus
      ) t 
      where coalesce(prev_state, true) <> head_state
    ) t
) t where status = -3;

[erogov]

Симпатично! И верные 8 баллов из 10 (мы не знаем заранее количество голов).

[RedWolf]

Уели!

Тогда так

select event_time, next_event_time
from (
    select event_time, sum(case when head_state = false then -1 else 1 end) over(order by event_time) status, 
           lead(event_time) over(order by event_time) next_event_time
    from (
      select * from (
        select *, lag(head_state, -1) over(partition by head_id order by event_time desc) prev_state 
        from cerberus
      ) t 
      where coalesce(prev_state, true) <> head_state
    ) t
) t where status = -1 * (select count(distinct head_id) from cerberus);

Или даже так

select event_time, next_event_time
from (
    select event_time, sum(case when head_state = false then -1 else 1 end) over(order by event_time) status, 
           lead(event_time) over(order by event_time) next_event_time, sum(case when head_id <> next_head_id or next_head_id is null then 1 else 0 end) over () head_count
    from (
      select * from (
        select *, lag(head_state, -1) over(partition by head_id order by event_time desc) prev_state, lead(head_id) over (order by head_id) next_head_id
        from cerberus
      ) t 
      where coalesce(prev_state, true) <> head_state
    ) t
) t where status = -1 * head_count;

[erogov]

Первый вариант в десятку! А вот во втором есть ошибка.

[RedWolf]

Почему? В вашем примере будет три записи, где следующий head_id не равен текущему или отсутствует.

Грубо говоря,

head_id | next_head_id | Not equals
1 1 F
1 2 T
2 2 F
2 2 F
2 3 T
3 NULL T

Считаем Not equals и получаем 3.

p.s. Можно было бы избавиться от суммы во внешнем подзапросе, но не хотелось два раза писать вызов lead или использовать какие-то магические числа для обозначения отсутствующей головы.

[erogov]

Вот такой тест не проходит:

SELECT setseed(0.0);
INSERT INTO cerberus 
  SELECT ((random()+0.5)*3)::int, d, random() < 0.5 
  FROM generate_series('2023-10-21 01:00:00'::timestamptz, '2023-10-22 01:00:00'::timestamptz, '5 minutes') d;

Получаются разные результаты.

[RedWolf]

Да, сам себя перехитрил. Тогда остается первый вариант :)

[Dddn]

Я по заголовку подумал, что статья будет про 1С.

[erogov]

Хм, а что в заголовке намекает на 1С?

[jansnein]

Вот пример для 4 задачи, в котором однозначность хода определяется тем, будет объявлен шах или мат. Ход - Nc3. Если походит левый конь - будет шах, если правый - мат, так что совсем по-хорошему информацию о том, ставиться ли шах или мат выкидывать нельзя, иначе вот в таких ситуациях оно работать не будет(хотя ход будет однозначно определяться)

[erogov]

Хм, а ведь действительно. Думаю, что на практике в таких случаях все же указывают конкретного коня, хотя формально неоднозначности нет. Тестами такая экзотика не проверялась, конечно.