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

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

111       111
2 1       2 1
22222  -> 22111
  1 2       2 1
  112       222

Потому что:

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

2) Каждая единичка должна быть инвертирована хоть раз.

3) Соответственно получаем множество клеток, которые должны быть инвертированы хоть раз — все единички, а также все клетки левее и/или ниже.

4) Любую пару инверсий можно заменить на пару инверсий: объединение и пересечение инвертируемых множеств.

5) таким образом, любой набор инверсий можно заменить на другой такой набор, что в него будет входить инверсия, соответствующая первому ходу данного алгоритма.

6) Далее по индукции =)

Мне тоже, но я решил, что 16*16 — слишком много, поэтому сделал для 4*4.

Добавьте в состояние направление. Тогда сумма просто явно очевидно выписывается с учетом того, что (x+1)y = xy+y. А дальше можно сжать назад в 4. Только лично мне не понятно зачем.

хм, а я понял его как "количество голосовавших должно быть положительно"
UPD он валидный хотя бы потому, что я тестил его в арене :)

или неправильно обрабатывали 0

не подскажешь контртест на непроверку min<=max ?

Ещё можно не проверить, что минимальное значение получилось неотрицательным.

Нет, это потому, что забывали проверять, что минимальное значение не меньше 0, а максимальное — не больше числа голосующих

Причем это уже несколько последних СРМов так.

Вот такой у них отличный софт

Я не понял чего ты не понял. Ты понял что есть состояния, ты понял как построить переходы. Что еще нужно? Давай посмотрим на граф, где вершины это состояния.
"В каждое состояние можно попасть из четырех: (i-1; j; a-1; b), (i-1; j; a; b-1), (i; j-1; a-1; b), (i; j-1; a; b-1). Как проверить, что переход в одно из следующих возможен понятно."
Этими словами ты описал как направлены рёбра, ты также знаешь условия при которых ребро есть или отсутствует. Например при выполнении некоторого условия у нас может быть ребро из (i-1, j, a-1, b) в (i, j, a, b).
граф ацикличен в силу того, что сумма i+j+a+b только возрастает если двигаться по ребрам. тебе нужно посчитать число способов добраться из вершины (0, 0, 0, 0) в (X0, X1, X2, X3) как это сделать? ДП, такое дп ты писал не один раз я думаю. Например можно поставить 1 в (0, 0, 0, 0) и бфсом приплюсовывать эту величину к тем вершинам, в которые ведут рёбра. Можно делать с помощью рекурсивного дп, рассчитывать это в обратном направлении, как это сделал PEIN. И да, прямо таки бфс нам здесь не нужен, ведь мы можем разбить граф на слои по значению суммы i + j
UPD: бфс не годится для произвольного ацикличного графа, не знаю почему я так написал, но в общем это классическая задача о подсчёте количества путей.

В арене топкодера, Practice Rooms