Comments 20
Покажу и свое решение задачи про параметры. Оно использует рекурсивный запрос и JSON для отслеживания текущего состояния параметров (есть удобные операции - и || для удаления и добавления ключа в объект, получается имитация множества).
WITH RECURSIVE enumerated AS (
SELECT *, row_number() OVER (ORDER BY ts) n FROM params
), r(ts, n, params) AS (
SELECT null::timestamp, 0::bigint, '{}'::jsonb
UNION ALL
SELECT p.ts, p.n,
CASE
WHEN p.value IS NULL THEN r.params - p.parameter_name
ELSE r.params || jsonb_build_object(p.parameter_name, 1)
END
FROM r, enumerated p
WHERE p.n = r.n + 1
), lens AS (
SELECT ts, n, array_length(array_agg(keys),1) len
FROM r, jsonb_object_keys(params) keys
GROUP BY ts, n
), intervals AS (
SELECT tsrange(ts, lead(ts) OVER (ORDER BY ts)) tsr, max(len) mlen
FROM lens
GROUP BY ts
)
SELECT lower(tsmr), upper(tsmr), mlen
FROM (
SELECT unnest(range_agg(tsr)) tsmr, mlen
FROM intervals
WHERE mlen = (SELECT max(mlen) FROM intervals) AND mlen > 1
GROUP BY mlen
);
Мне кажется, что эта задача банальным подсчетом точек изменений решается изящнее и эффективнее, чем через json, рекурсию или интервалы:
WITH src(parameter_name, ts, value) AS (
VALUES ('max_connections', '2025-01-10 11:30'::timestamp, '500'),
('max_connections', '2025-01-11 12:30', NULL),
('max_connections', '2025-01-11 15:30', '500'),
('max_connections', '2025-01-12 12:30', NULL),
('max_connections', '2025-01-12 15:30', '500'),
('work_mem', '2025-01-10 11:30', '8MB'),
('work_mem', '2025-01-12 14:00', '16MB'),
('max_connections', '2025-01-12 14:00', '1000'),
('max_connections', '2025-01-17 12:30', NULL),
('shared_buffers', '2025-01-12 12:30', NULL),
('shared_buffers', '2025-01-12 13:30', '20000'),
('shared_buffers', '2025-01-14 10:00', NULL),
('shared_buffers', '2025-01-15 07:40', NULL),
('temp_buffers', '2025-01-09 10:20', '2000'),
('temp_buffers', '2025-01-11 11:30', null),
('temp_buffers', '2025-01-12 12:30', '1500'),
('temp_buffers', '2025-01-14 03:15', null),
('maintenance_work_mem', '2025-01-09 10:20','1000'),
('maintenance_work_mem', '2025-01-10 13:26', null),
('maintenance_work_mem', '2025-01-12 12:30', null),
('maintenance_work_mem', '2025-01-12 14:30', '1500'),
('maintenance_work_mem', '2025-01-15 14:30', null),
('max_worker_processes', '2025-01-08 00:30', '16'),
('max_worker_processes', '2025-01-12 14:00', null)
)
-- определяем "в точке", как должно измениться кол-во "недефолтных" параметров
, diff AS (
SELECT
*
, CASE
WHEN value IS NOT NULL AND lag(value) OVER(PARTITION BY parameter_name ORDER BY ts) IS NULL THEN +1
WHEN value IS NULL AND lag(value) OVER(PARTITION BY parameter_name ORDER BY ts) IS NOT NULL THEN -1
ELSE 0
END diff
FROM
src
)
-- находим суммарное количество "недефолтных" в каждой точке
, sum AS (
SELECT
*
, sum(diff) OVER(ORDER BY ts) parameters
FROM
diff
)
-- помечаем точки, изменяющие суммарное значение
, rngs AS (
SELECT
*
, parameters IS DISTINCT FROM lag(parameters) OVER(ORDER BY ts) is_rng_start
FROM
sum
)
-- находим следующую точку изменения суммарного значения - это конец интервала
, rnge AS (
SELECT
*
, lead(ts) OVER(ORDER BY ts) ts_end
FROM
rngs
WHERE
is_rng_start
)
-- отбираем максимум с учетом возможного дублирования
SELECT
ts ts_start
, ts_end
, parameters
FROM
rnge
ORDER BY
parameters DESC
FETCH NEXT 1 ROWS
WITH TIES;
Да так тоже можно, но ваше решение пройдет не все тесты. Оно выведет интервал в случае, если все параметры заданы null, хотя такой интервал должен быть исключен. И в случае, если во всех интервалах менялось по одному параметру, тоже выведет все интервалы, а по условию задачи такие интервалы должны быть исключены.
В первом туре участвовало свыше 4 500 человек...
Я, конечно после всех скандалов с "конкурсами", охотно верю, но где бы это проверить?
На сайте олимпиады, есть протокол 1 го этапа. В нем те кто набрал, хоть сколько то баллов. https://challenge.braim.org/challenge/360/stage/1249/protocol/0cbda256-e59b-45a9-9aaf-daf18e8132bf
Часть (почти 1000 человек) набрало 0 баллов. Часть отсеялось по формальным критериям.
Господа, господа, вы упускаете одно решение (с) Рик и Морти
Задача про варенье, без оконных функций и т.д.
with daily_jam as (
select at, sum(qty) as qty
from jam
group by at
having sum(qty) > 0
)
select count(*)
from daily_jam d1
inner join daily_jam d2 on d2.at = d1.at - 1
inner join daily_jam d3 on d3.at = d1.at - 2 and (d1.qty + d2.qty + d3.qty) >= 4
inner join daily_jam d4 on d4.at = d1.at - 3 and (d2.qty + d3.qty + d4.qty) >= 4
inner join daily_jam d5 on d5.at = d1.at - 4 and (d3.qty + d4.qty + d5.qty) >= 4
inner join daily_jam d6 on d6.at = d1.at - 5 and (d4.qty + d5.qty + d6.qty) >= 4
inner join daily_jam d7 on d7.at = d1.at - 6 and (d5.qty + d6.qty + d7.qty) >= 4Да, но если заменить 5 и 3 на другие числа, может получиться уже не так привлекательно (:
Это понятно. Но в задаче было 5 и 3 :) По факту это семь дней подряд с вареньем и еще так, чтобы любые три дня подряд из них было 4 и более банок варенья в сумме.
Можно и гибче
with daily_jam as (
select at, sum(qty) as qty
from jam d
group by at
having sum(qty) > 0
), fresh as (
-- список дней, являющихся концом трехдневного марафона поедания варенья
select d.at
from daily_jam d
inner join daily_jam n on n.at > d.at - 3 and n.at < d.at -- два предыдущих дня
group by d.at
having (max(d.qty) + sum(n.qty)) > 3 -- количество банок за данный день и два предыдущих
and count(n.at) = 2 -- два предыдущих дня имеют место быть
)
select count(*) from (
select count(*)
from daily_jam d
inner join fresh f on f.at > d.at - 5 and f.at <= d.at -- данный день и четыре предыдущих венчали трехдневные поедания варенья
group by d.at
having count(*) = 5
) tПо 4-й задаче предложу решение чуть на иных механизмах:
-- проверяем ходы и секрет вместе
WITH chk AS (
SELECT
*
, regexp_split_to_array(code, '') chars
, NOT(code !~ '(.).*\1' AND code ~ '^[0-9A-F]{4}$') is_error
FROM
regexp_split_to_table(upper(current_setting('bulls.secretcode') || ',' || current_setting('bulls.game')), ',')
WITH ORDINALITY step(code, n)
)
-- PG выберет за нас подзапрос в зависимости от корректности данных
(
SELECT
'error' gameparty
FROM
chk
GROUP BY
1
HAVING
bool_or(is_error) -- хоть где-то есть ошибка
UNION ALL
SELECT
string_agg(code || ' ' || b || 'B' || (c - b) || 'C', ',' ORDER BY n)
FROM
chk
, (
SELECT
chars secret
FROM
chk
WHERE
n = 1
)
, LATERAL (
SELECT
count(*) FILTER(WHERE x = y) b -- только "быки" на своих местах
FROM
unnest(chars, secret) T(x, y)
) b
, LATERAL (
SELECT
count(*) FILTER(WHERE x = ANY(secret)) c -- "коровы" вместе с "быками"
FROM
unnest(chars) T(x)
) c
WHERE
n > 1
)
LIMIT 1;5-я задача на основе предыдущего варианта:
WITH gameparty AS (
SELECT
*
, parts[1] code
, regexp_split_to_array(parts[1], '') chars
, parts[2]::integer b
, parts[3]::integer c
FROM
regexp_split_to_table(upper(current_setting('bulls.gameparty')), ',')
WITH ORDINALITY T(step, n)
, regexp_match(step, '^([0-9A-F]{4}) (\d)B(\d)C$') parts -- заодно и формат проверяем
)
SELECT
xcode code
FROM
generate_series(0xFFFF, 0, -1) i -- нужен максимальный код, так что сразу генерим реверсивно (до первого подходящего, благодаря LIMIT)
, lpad(upper(to_hex(i)), 4, '0') xcode
, regexp_split_to_array(xcode, '') secret
, LATERAL (
SELECT
bool_and((b, c) = (xb, xc - xb)) chk -- совпадение быков/коров во всех ходах
FROM
gameparty
, LATERAL (
SELECT
count(*) FILTER(WHERE x = y) xb
FROM
unnest(chars, secret) T(x, y)
) b
, LATERAL (
SELECT
count(*) FILTER(WHERE x = ANY(secret)) xc
FROM
unnest(chars) T(x)
) c
) T
WHERE
NOT EXISTS ( -- при корректности кодов в исходнике
SELECT
NULL
FROM
gameparty
WHERE
code IS NULL OR
code ~ '(.).*\1'
LIMIT 1
) AND
xcode !~ '(.).*\1' AND -- отсекаем коды с повторными символами
chk -- оставляем только удовлетворившие всем ходам
LIMIT 1;Не все тесты прошло решение, например если все ходы не попадают на секретное число, то есть нет быков и коров. Запрос ничего не покажет. На конкурсе, у многих участников этот тест не проходил.
Для вот таких данных
set bulls.gameparty='5678 0B0C,9056 0B0C, 12AB 0B0C, EF25 0B0C';
Оба запроса очень интересные. Сохранил в решения.
Вторая задача
select from_date, to_date, size from (
-- определяем интервалы групп и максимальное количество параметров в группе
select min(ts) from_date, max(coalesce(next_ts, 'infinity')) to_date, grp, size, max(size) over () max_size from (
-- добавляем синтетическую id группы в виде кумулятивного кол-ва групп и добавляем дату начала следующей группы для определения конца данной группы
select *, sum(case when coalesce(prev_size, 0) <> size then 1 else 0 end) over (order by ts) grp, lead(ts, 1) over (order by ts) next_ts from (
-- делаем группы по adjacent датам с одинаковым кол-вом переопределенных параметров. сначала добавляем кол-во параметров из предыдущей группы, если это кол-во не равно текущему кол-ву параметру группы, то это новая группа
select *, lag(size, 1) over (order by ts) prev_size from (
-- добавляем количество переопределенных параметров на каждую дату. количество +1 если параметр не был переопределен и стал переопределен, -1 если был переопределен и стал не переопределен, иначе 0
select *, sum(case when value is not null and prev_value is null then 1 when value is null and prev_value is not null then -1 else 0 end) over(order by ts) size
from (
-- добавляем предыдущее значение для каждого параметра на определенную дату
select *, lag(value, 1) over(partition by parameter_name order by ts) prev_value
from params
) t
) t
) t
) t
group by grp, size
) t where size = max_size and size > 1
order by 1Sign up to leave a comment.
«IT-Планета 2025»: задачи второго этапа по PostgreSQL