Реши задачу(и) с контеста на Python. Требования к...

Question

Реши задачу(и) с контеста на Python. Требования к стилю кода:

Переменные называй короткими буквами (a, b, c, d, i, j, k, n, m, s, t и т.п.), не словами и не в духе "результат", "количество" — как будто спешащий человек на контесте, а не нейросеть.
Комментариев не пиши вообще, даже коротких.
Можно небольшие неаккуратности стиля (непоследовательные отступы между блоками, где-то однострочный if, где-то нет, разное именование похожих по смыслу переменных в разных задачах) — но без синтаксических ошибок и без потери читаемости настолько, что код не работает.
Не используй докстринги, type hints, избыточную обработку ошибок, f-строки там где обычный print/join достаточен — пиши просто, как в блокноте на контесте.
Не добавляй ничего сверх необходимого (без функций-обёрток, если задача не требует, без классов, без argparse и т.д).
Обязательно перед тем как показать финальный код:

Реши задачу и придумай/выведи формулу или алгоритм сам, не гадай.
Проверь решение брутфорсом или стресс-тестом на случайных данных (небольшие n), сравни с честным перебором, покажи что совпадает.
Прогони через пример(ы) из условия.
Если ограничения большие — проверь производительность на большом тесте (близком к максимальным n/t).
Дополнительно:
Не бросайся сразу писать код или перебирать варианты руками — сначала явно выпиши структуру задачи (что известно, что нужно доказать), и распланируй шаги вывода формулы/алгоритма.
Если после ~5-7 минут рассуждений нет закрытой формулы или чёткого алгоритма — остановись, покажи текущий прогресс, доказанные промежуточные факты и на чём застрял, вместо того чтобы молча продолжать перебор.
Оцени сложность итогового алгоритма (Big-O по времени и памяти) и явно проверь, что она укладывается в лимиты (n, TL, ML) до того как писать финальный код.
Если задача требует ответ по модулю — используй его только в финальном коде; во время вывода формулы работай с точными числами/логикой, чтобы не запутаться в mod-арифметике раньше времени.
Не переписывай brute-force как единственную проверку по одному случайному тесту — прогони стресс-тест минимум на 100-1000 случайных маленьких кейсов.

Answer 1

Разбираю обе задачи. F удалось закрыть полностью и проверить. По G завершённого доказанного построения пока нет, поэтому по твоему пункту 6 не буду выдавать гипотезу за решение: после F покажу, что именно по G уже доказано и где остаётся разрыв.

F. Красивые столбики

1. Структура задачи

Нужно понять две вещи:

Как характеризовать уже красивый массив.
Когда некоторый отрезок можно сделать «достаточным» за 0 или 1 изменение.

Ключевая характеристика такая.

Назовём отрезок [l,r] хорошим блоком, если

a_l=a_r=\max(a_l,\ldots,a_r).

Тогда массив красивый тогда и только тогда, когда его можно разбить на хорошие блоки длины хотя бы 2.

Почему хороший блок покрывается хорошими парами: возьмём все позиции максимума внутри блока. Между двумя соседними вхождениями максимума нет элемента >= него, поэтому они образуют хорошую пару. Все такие пары вместе покрывают весь блок.

В обратную сторону берём глобальный максимум массива. Его первое и последнее вхождения образуют хороший блок. Никакая хорошая пара из левой части не может пересечь первое вхождение максимума, и аналогично справа. Поэтому остаются две независимые красивые части; применяем рассуждение рекурсивно.

2. Сколько изменений нужно одному блоку

Пусть хотим сделать [l,r] хорошим блоком.

Обозначим:

q_1(l)=\text{первый }j>l,\quad a_j>a_l,

а q2(l) — второй такой индекс.

Также

p(r)=\text{последний }j<r,\quad a_j>a_r.

Ноль изменений

Нужно

a_l=a_r,\qquad r<q_1(l).

То есть концы равны, и внутри ничего строго больше них нет.

Ровно одно изменение

Есть ровно три варианта.

Первый:

a_l>a_r,\qquad r<q_1(l).

Тогда меняем a[r] на a[l].

Второй:

a_l<a_r,\qquad l>p(r).

Тогда меняем a[l] на a[r].

Третий:

a_l=a_r,\qquad q_1(l)<r<q_2(l).

То есть внутри ровно один элемент строго больше концов. Меняем его на значение концов.

Других случаев для одного изменения нет: если меняется конец, он обязан стать равным второму концу; если меняется внутренний элемент, концы уже должны быть равны.

3. Почему ответ всегда не больше 2

Можно сделать

text
a[1] = 10^9
a[n] = 10^9

Тогда весь [1,n] — хороший блок, поскольку все значения не превосходят 10^9.

Значит ответ только 0, 1 или 2.

4. DP

Пусть:

b[i] — префикс 1..i разбивается на хорошие блоки без изменений;
c[i] — префикс 1..i разбивается с ровно одним изменением.

b[0]=True.

Нужно быстро искать подходящие начала l.

Для этого поддерживаются:

по каждому значению — старт с максимальным q1[l];
два лучших старта с различными значениями концов для случая a[l]>a[r];
два последних старта с различными значениями для случая a[l]<a[r];
отложенные события для случая q1[l]<r<q2[l].

q1,q2 находятся двумя монотонными стеками за O(n). Ближайший предыдущий строго больший элемент считается ещё одним стеком непосредственно во время DP.

Итого все операции амортизированно O(1).

Сложность

Для одного теста:

O(n)

по времени и

O(n)

по памяти.

Суммарно n <= 2*10^5, то есть в ограничения укладывается.

5. Проверка брутфорсом

Я сравнил алгоритм с честным перебором:

все массивы значений 1..3 для n=2..7: 3276 тестов;
ещё 2000 случайных массивов с n=2..9, значениями 1..5.

Всего 5276 маленьких тестов.

Для каждого сравнивалось минимальное число операций, а затем отдельно проверялось, что массив после выведенных операций действительно красивый.

Результат:

text
OK 5276 cases

Несовпадений нет.

6. Пример из условия

Получился вывод:

text
1
1 3
1
5 7
0
2
1 1000000000
8 1000000000
0

В четвёртом тесте операции отличаются от примера, но также оптимальны: после них весь массив покрывается парой (1,8).

7. Максимальный тест

На случайном n=200000:

text
0.96 sec
129560 KB

Это локальный замер CPython; при лимитах 2 sec / 256 MB запас есть.

Финальный код F

python
import sys

z=iter(map(int,sys.stdin.buffer.read().split()))
t=next(z)
o=[]
for _ in range(t):
    n=next(z)
    a=[0]+[next(z) for i in range(n)]

    q=[n+1]*(n+1)
    w=[n+1]*(n+1)
    s=[]
    d=[]
    for i in range(1,n+1):
        while d and a[d[-1]]<a[i]: w[d.pop()]=i
        e=[]
        while s and a[s[-1]]<a[i]:
            j=s.pop()
            q[j]=i
            e.append(j)
        while e: d.append(e.pop())
        s.append(i)

    b=[False]*(n+1)
    c=[False]*(n+1)
    b[0]=True
    v=[None]*(n+1)
    e=[0]*(n+2)
    ee=[0]*(n+1)
    x={}
    y={}
    f={}
    g=(0,0,0)
    h=(0,0,0)
    r=(0,0)
    rr=(0,0)
    s=[]

    for i in range(1,n+1):
        l=e[i]
        while l:
            j=a[l]
            d=f.get(j)
            if d is None or w[l]>d[0]: f[j]=(w[l],l)
            l=ee[l]

        while s and a[s[-1]]<=a[i]: s.pop()
        p=s[-1] if s else 0

        d=x.get(a[i])
        if d is not None and d[0]>i: b[i]=True

        d=y.get(a[i])
        if d is not None and d[0]>i:
            c[i]=True
            v[i]=(d[1]-1,1,None)

        if not c[i]:
            d=f.get(a[i])
            if d is not None and d[0]>i:
                l=d[1]
                c[i]=True
                v[i]=(l-1,0,(q[l],a[l]))

        if not c[i]:
            d=g if g[2]!=a[i] else h
            if d[0]>i:
                l=d[1]
                c[i]=True
                v[i]=(l-1,0,(i,a[l]))

        if not c[i]:
            d=r if r[1]!=a[i] else rr
            if d[0]>p:
                l=d[0]
                c[i]=True
                v[i]=(l-1,0,(l,a[i]))

        if b[i-1]:
            l=i
            d=x.get(a[l])
            if d is None or q[l]>d[0]:
                x[a[l]]=(q[l],l)
                z1=(q[l],l,a[l])
                if g[2]==a[l]: g=z1
                elif h[2]==a[l]:
                    h=z1
                    if h[0]>g[0]: g,h=h,g
                elif z1[0]>g[0]: h,g=g,z1
                elif z1[0]>h[0]: h=z1
            if r[1]==a[l]: r=(l,a[l])
            else:
                rr=r
                r=(l,a[l])
            if q[l]<n:
                j=q[l]+1
                ee[l]=e[j]
                e[j]=l

        if c[i-1]:
            l=i
            d=y.get(a[l])
            if d is None or q[l]>d[0]: y[a[l]]=(q[l],l)

        s.append(i)

    if b[n]: o.append('0')
    elif c[n]:
        i=n
        while v[i][1]: i=v[i][0]
        j,k=v[i][2]
        o.append('1')
        o.append(str(j)+' '+str(k))
    else:
        o.append('2')
        o.append('1 1000000000')
        o.append(str(n)+' 1000000000')

sys.stdout.write('\n'.join(o))

G. Заполнение таблицы — текущий доказанный прогресс

Здесь я дошёл дальше простой гипотезы, но до полностью доказанного конструктивного алгоритма не дошёл, поэтому останавливаюсь согласно твоему пункту 6.

После разрезов удобно перейти от координат разрезов к длинам полос:

R=(r_1,r_2,\ldots),\qquad C=(c_1,c_2,\ldots).

Точно решается одномерный случай

Пусть есть последовательные куски длин s1,s2,...; кусок длины x должен содержать перестановку 1..x, соседние клетки разных кусков тоже должны различаться.

Тогда:

кусок длины 1 жёстко равен [1];
кусок длины 2 имеет лишь две ориентации: [1,2] и [2,1];
кусок длины хотя бы 3 позволяет независимо подобрать два разных значения на концах и фактически «сбрасывает» ограничения.

Отсюда одномерная последовательность выполнима тогда и только тогда, когда в каждом максимальном участке, состоящем только из длин 1 и 2, находится не больше одной единицы.

Эквивалентно, запрещена ситуация

1,\underbrace{2,2,\ldots,2}_{\text{сколько угодно}},1.

Например [1,2,1] невозможно:

text
1 | 2 1 | 1

или

text
1 | 1 2 | 1

— один из стыков обязательно ломается.

Необходимые условия для G

Если существует горизонтальная полоса высоты 1, то вдоль неё задача буквально превращается в этот одномерный случай для массива C.

Поэтому C обязан удовлетворять условию выше.

Симметрично: если существует вертикальная полоса ширины 1, то условию должен удовлетворять R.

На малых тестах получается очень сильная гипотеза:

этих двух условий также достаточно.

Я перебрал все небольшие разбиения с n,m <= 4, nm <= 9; точный перебор заполнений не нашёл ни одного контрпримера этой гипотезе.

Она также полностью объясняет пример:

первые три теста проходят;
в четвёртом R=C=[1,1,2];
уже две соседние единицы делают заполнение невозможным.

Ещё один доказанный кусок

Прямоугольники площади 1 и 2 можно рассматривать отдельно.

У прямоугольника площади 2 есть только две ориентации, то есть одна бинарная переменная. Ограничение между двумя такими маленькими блоками задаёт XOR между их ориентациями; соседство с блоком площади 1 фиксирует ориентацию.

То есть всю систему блоков площади 1/2 можно проверять DSU с чётностями.

Для более крупного блока доказано следующее: если уже заполнены только его верхний и левый соседи, то при площади хотя бы 3 всегда существует перестановка 1..S, избегающая совпадений с ними. Это следует из Холла: запрещённые пары являются объединением максимум двух частичных паросочетаний.

Где остаётся разрыв

Нельзя просто заранее заполнить большие блоки: их выбор способен позже зажать блок площади 1/2.

Но и нельзя произвольно заполнить сначала все маленькие: например, ориентации четырёх соседних блоков площади 2 способны зажать центральный 2x2.

То есть необходима глобально согласованная конструкция. Именно её полного доказательства у меня сейчас нет.

Поэтому код G не привожу: на текущем этапе это был бы либо недоказанный greedy/random, либо решение, которое прошло маленький брут, но может упасть на контрпримере. Это как раз тот случай, для которого ты отдельно попросил остановиться, а не угадывать.

Реши задачу(и) с контеста на Python. Требования к...

Domanda

Pensiero

compare brute

enumerate small cs and prev satisfying ordinary boundary !=

Let's implement exact backtracking dynamically generating permutations for block sizes <=6

generic fill block via bipartite matching with fixed neighbors

exact feasibility by assigning each block permutation, backtracking for small product

redefine debug based prior funcs still in state?

copy construct with debug

Rebuild until failure and print neighbor cells maybe modify quickly by adapting debug?

cells tl,tr,bl,br

Risposta