Задача А.
Так как ограничения были не большими можно предложить много разных решений, например построить граф на N*4 вершины и пустить bfs. Быстрым же решением за O(1) было: пронумеруем целочисленные точки лежащие на квадрате, к примеру так как показано на рисунке:
Тогда вычислить по координатам номер точки не сложно к примеру если точка имеет координату y==n -> что её позиция n + x (если нумерация как на рисунке с нуля). Получается что мы преобразовали квадрат в прямую с тем осложнением что можно попасть из клетки N*4 – 1 в клетку 0, то есть у нас не прямая а круг, с отмеченными точками от 0 до 4*N-1 расстояние между смежными двумя точками 1, значит несложно взять разность индексов точек и узнать расстояние при движении по часовой и против часовой: (a-b+4*n)%(4*n) и (b-a + 4*n)%(4*n), ближайшее расстояние и будет ответом.
Задача B
При таких ограничениях на количество запросов нельзя было итеративно добавлять лестницы. Но задачу упрощал тот факт что контрольных ячеек в которых нужно было узнать количество камней было не больше 100, по этому можно было для каждой «интересно» ячейки просмотреть все запросы и посчитать сколько каждый из них добавлял камней, таким образом сложность: O(K*M) что вполне укладывалось в отведённые 2 секунды. Более быстрое решение за O(N+M+K) выглядит так: будем держать в памяти две величины: a – сколько нужно добавлять сейчас к ячейке, v – на сколько должна изменится, в текущей ячейке будем обновлять величину a и v так чтобы a равнялось количеству камней в ячейке после всех операций, а v – на сколько a увеличивается при переходе на следующую ячейку. Тогда задача сведётся к тому что нужно правильно обновлять a и v, что делать не очень сложно, к примеру если есть запрос (x,y,z) – то в ячейке x нужно к a добавить x а к v добавить 1, так как с каждой следующей ячейкой количество камней из за этого вопроса будет увеличиваться на 1. Аналогично после ячейки y уже нужно от v отнять 1 и забрать из a текущее количество камней вложенное запросом, сохранив все такие пары запросов в отдельном массиве можно за один проход посчитать всё.
Задача C
Сначала посчитаем сколько есть массивов у которых каждый следующий элемент начиная с второго не меньше предыдущего. Чтобы сделать это быстро – возьмём листочек в клеточку высотой 1 клеточка и длиной N*2-1 клеточку, далее выберем N-1 клеточку и поставим в них крестики – теперь пусть этот листик кодирует массив, пусть количество пустых клеточек от начала массива до первого крестика будет равнялся количество 1 в массиве(они соответственно идут подряд и если есть хотя бы одна единица – то именно с 1 начинается масив), количество пустых клеточек от первого крестика до второго – количество двоек в массиве и так дальше, легко заметить что количество пустых клеточек будет равно N*2-1 – (N-1) = N. Получается что любой листочек кодирует массив который нам подходит и более того все возможные массивы можно закодировать с помощью такого листочка в клеточку. Всех различных листочков ровно C(N*2-1, N) (биномиальный коэффициент из N*2-1 по N). Такое число можно вычислить по формуле с факториалами, единственная сложность – деление. Так как модуль был простым – можно было вычислить обратный элемент в поле по модулю и заменить деление умножением. Получим количество неубывающих последовательностей, соответсвенно есть столько же невозрастающих, осталось отнять те которые попадают и туда и туда, а это не что иное как массив у которого все числа одинаковые
Задача D
Задачка оказалась весьма сложной. Для начала если нет занятых клеточек – вычислить ответ очень даже не сложно – ответом будет сума манхэттенских расстояний, с учётом того, что в манхэттенском расстоянии можно сначала посчитать расстояния по одной координате потом по другой и потом просто просуммировать, ответ найти не сложно. Что же получается когда есть занятые клетки. Сначала посмотри на одну занятую клетку. Если клетка из которой ищутся расстояния не лежит на одной горизонтали или вертикале с занятой – то она абсолютно не влияет на сложность добраться до остальных клеток:
Это происходит из за того что в каждую ячейку с предыдущего фронта расстояний (множества ячеек расстояние до которых сейчас максимальное, эти фронты образуют ромбы как можно заметить на рисунке или из формулы манхэттенского расстояния) есть два варианта как добраться до ячейки, учтем правило что никакие две ячейки не могут быть смежными (ни по диагонали ни по вертикали ни по горизонтали) получается что такая ячейка нам не мешает. Но внимательный взгляд в картинку наводит на очевидную мысль: как раз ячейка которая находится на одной вертикали/горизонтали имеет только одну ячейку соседа из предыдущего фронта, посмотрим что происходит если такая ячейка одна:
Все ячейки после за занятой начинают «запаздывать» на 2 по расстоянию, но более важно то что изменился фронт!! Теперь (с верхней стороны фронта) есть 2 ячейки для которых переход с предыдущего фронта единственен, и как следствие есть дальше встретится занятая ячейка на пути у «угла» фронта – появится новый отрезок запоздавших ячеек и угол фронта снова изменится, так как нас интересует только одна сторона его расширения (с другой стороны больше не может быть занятых ячеек по условию) можно сказать что он сместится от начальной ячейки:
Получается можно просчитать сколько ячеек будет «запаздывать», тем более что запоздание всегда равно двум. Для каждого направления можно выбрать каждую занятую клетку и проверить слева-справа есть ли дальше по этому направлению смежные ячейки и добавить суму запоздания всему отрезку который тормозит первая занятая ячейка. Получается это можно вычислить за квадрат количества занятых клеток, которых не больше min(N,M). Остальное – детали. Нужно вычислить суму манхэттенских расстояний с учетом существования занятых ячеек. Для этого можно сначала вычислить суму для поля, если бы там не было занято, потом для каждой занятой – посчитать расстояние до всех остальных – отнять дважды, так как сначала отнимает учтённые лишние расстояния когда мы выходили из этой ячейки и второй раз отнимаем все те расстояния которые были учтены для всех остальных ячеек в данную. Правда в таком случае дважды отнимутся расстояния между двумя занятыми ячейками – придется добавить их (сложность тоже квадрат). Всего получается решение за O(K^2) где K – количество занятых ячеек.
