Реши задачу(и) с контеста на 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

Сначала разложим задачу по структуре, а потом уже код.

1. Что здесь на самом деле нужно посчитать

Пусть текущее множество вершин со значением 0 — это $S$ .

Ход в вершину $v$ приносит очко тогда и только тогда, когда у $v$ ровно один сосед уже лежит в $S$ .

Полезная лемма для дерева:

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

Это доказывается индукцией по числу оставшихся единиц. Для хода с очком переход имеет вид $1-F'$ , для хода без очка — $-F'$ ; после индукционного шага $F'\in\{0,1\}$ , поэтому нулевой ход не может быть лучше очкового. В случае отсутствия очковых ходов ацикличность дерева позволяет тем же удалением крайних компонент получить значение 0.

Следовательно, исходную игру можно заменить на обычную impartial game:

разрешены только вершины с ровно одним нулевым соседом;
кто не может сделать такой ход — проиграл.

Если эта вспомогательная игра выигрышная для первого игрока, исходное $p-q=1$ , иначе $p-q=0$ .

То есть ответ здесь всегда только 0 или 1.

2. Что происходит на пути между $x$ и $y$

Рассмотрим единственный путь

v_0=x,v_1,\ldots,v_k=y.

Во вспомогательной игре нулевые вершины растут двумя связными областями: от $x$ и от $y$ .

Вне пути никаких конфликтов быть не может: если ветка уже прикреплена к нулевой вершине пути, её можно целиком постепенно закрасить.

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

Для каждой $v_i$ обозначим через $b_i$ число вершин во всех ветках, отходящих от неё не по пути.

Нам нужна только чётность $b_i$ .

Почему: игра в такой подвешенной ветке всегда длится ровно столько ходов, сколько в ней вершин. Поэтому её число Шпрага—Гранди:

b_i\bmod 2.

3. DP по оставшемуся отрезку пути

Пусть

G(l,r)

— число Шпрага—Гранди игры, когда между двумя уже занятыми областями остались вершины пути $v_l,\ldots,v_r$ .

Если $l=r$ , единственная вершина уже имеет двух нулевых соседей, поэтому:

G(l,l)=0.

Если $l<r$ , можно взять либо левый, либо правый конец.

После взятия $v_l$ :

остаётся $G(l+1,r)$ ;
активируются боковые ветки $v_l$ , их SG равен $b_l\bmod2$ .

Значит первый вариант:

G(l+1,r)\oplus (b_l\bmod2).

Аналогично справа:

G(l,r-1)\oplus (b_r\bmod2).

Поэтому

G(l,r)=\operatorname{mex}\left( G(l+1,r)\oplus b_l,\; G(l,r-1)\oplus b_r \right),

где в b сразу храним только чётности.

У $x$ и $y$ боковые ветки активны изначально, поэтому итоговый SG:

G(1,k-1)\oplus b_0\oplus b_k.

Если он ненулевой — ответ 1, иначе 0.

DP зависит только от предыдущей диагонали, поэтому память $O(n)$ .

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

Для честного перебора маленьких деревьев я использовал состояние mask нулевых вершин и точный minimax:

F(mask)= \max_v \left( [c_v=1]-F(mask\cup\{v\}) \right).

Проверки:

перебраны все помеченные деревья до $n=6$ и все пары $x,y$ : 20796 позиций, расхождений 0;
ещё 5000 случайных деревьев с $2\le n\le10$ : 5000/5000 совпадений с полным minimax.

Для примера из условия алгоритм получил:

text
1
1
0
0

что полностью совпадает.

5. Сложность

Путь и размеры подвешенных частей находятся за $O(n)$ .

Интервальный DP:

O(d^2)\le O(n^2),

где $d$ — длина пути между $x$ и $y$ .

Память:

O(n).

При $n=3000$ в худшем случае получается примерно 4.5 млн DP-переходов. На тесте-пути из 3000 вершин вычисление заняло около 0.9 с в текущем окружении. При лимите 2 с, сумме $n\le3000$ и памяти 256 МБ укладывается.

Код

python
import sys

it=iter(map(int,sys.stdin.buffer.read().split()))
t=next(it)
o=[]

for _ in range(t):
    n=next(it)
    x=next(it)-1
    y=next(it)-1

    a=[[] for _ in range(n)]
    for i in range(n-1):
        u=next(it)-1
        v=next(it)-1
        a[u].append(v)
        a[v].append(u)

    p=[-1]*n
    p[x]=x
    q=[x]
    for v in q:
        if v==y:
            break
        for u in a[v]:
            if p[u]==-1:
                p[u]=v
                q.append(u)

    c=[]
    v=y
    while v!=x:
        c.append(v)
        v=p[v]
    c.append(x)
    c.reverse()

    z=[0]*n
    for v in c:
        z[v]=1

    b=[0]*len(c)
    for i,v in enumerate(c):
        for u in a[v]:
            if z[u]:
                continue
            s=[(u,v)]
            while s:
                w,pa=s.pop()
                b[i]^=1
                for h in a[w]:
                    if h!=pa:
                        s.append((h,w))

    m=len(c)-2

    if m<=1:
        g=0
    else:
        d=[0]*m

        for k in range(2,m+1):
            e=[0]*(m-k+1)

            for i in range(m-k+1):
                l=i+1
                r=i+k

                u=d[i+1]^b[l]
                v=d[i]^b[r]

                if u and v:
                    w=0
                elif u!=1 and v!=1:
                    w=1
                else:
                    w=2

                e[i]=w

            d=e

        g=d[0]

    o.append(str(int((g^b[0]^b[-1])!=0)))

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

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

질문

사고

Python

Python

Python

사고

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

사고

답변

1. Что здесь на самом деле нужно посчитать

2. Что происходит на пути между $x$ и $y$

3. DP по оставшемуся отрезку пути

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

5. Сложность

Код

이 Q&A 공유하기

질문

사고

Python

Python

Python

사고

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

사고

답변

1. Что здесь на самом деле нужно посчитать

2. Что происходит на пути между xxx и yyy

3. DP по оставшемуся отрезку пути

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

5. Сложность

Код

이 Q&A 공유하기

2. Что происходит на пути между $x$ и $y$