ооп. А если множество одно, а последовательности длин разные?

А кто-нибудь может это доказать (хотя бы нестрого)? Мы делали весьма хардкорно: перебирали перестановку из отражений, применяли их к многоугольнику и находили вектор, который соединяет центры масс, проверяли, что он подходит. Это еще и в лонг даблах не заходит, только целочисленно.

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

пффф, тест:
4
0 4
4 7
7 3
3 0
8 1
13 1
13 6
8 6
ответ НО (если я не ошибся), насколько я понимаю, ваше решение выдаст YES? мне кажется, или он валит всякие площади, длины сторон, углы и периметры

Одно из авторских решений — такое как у вас, другое за O(площадь прямоугольника). Оно основано на том, что "диагональный bounding-box" можно за быстро пересчитывать при добавлении некоторых клеток, которые нужно осветить, а также уменьшения допустимого ответа (можно пересчитывать за O(кол-во добавленных клеток)). А если начнем перебирать ответ с суммы длин сторон, и будем отнимать по единице каждый раз (до того момента, пока существуют клетка такая, что поставив в нее лампочку, осветим необходимые клетки), то всего будет обработано O(площадь) клеток.

А что за "грязный хак"?

Как-то сложновато. Верно, но сложновато. Можно просто перебрать все повороты второго многоугольника (их 8). Теперь для первого и рассматриваемого найти минимальные вершины (самые нижние левые), а дальше просто пройтись двумя форами, проверяя на соответствие координаты вершин, по часовой и против часовой стрелки. Хотя, может, профессионалу мой способ покажется менее рациональным и удобным, не знаю, не знаю :) UPD. Тьфу, выше уже было такое решение. Ну да ладно)

Я эту задачу вообще случайно сдал: решаю по монитору, вижу, что все Ф сдают, читаю (потом оказалось, что это Е) понимаю, что может все не так уж и просто, но раз люди за 5-10 минут сдают, значит эвристики с площадью, периметром, углами должны работать. Пишу, сдаю, потом несколько секунд удивляюсь, что задачу Ф я так и не сдал, но зато получил первый успешный сабмит по Е :)

збс

Ты не прав.

Надо создавать массивы длины N.

Разбить треугольное поле на n диагоналек.

   . 
  X..
 XXX..
XXXXX..

Посчитать динамику dp[i][j] — количество способов покрыть поле, таких что мы уже покрыли последние i диагоналей (три на предыдущей картинке), причем мы уже пробовали ставить на первые j побочных диагоналей. N^2 состояний, каждое считается за O(N) (надо перебрать сколько мы покрыли до этого). Можно заметить, что нам нужно сумму по всем переходам посчитать, это можно с помощью частичных сумм на одной из диагоналей или ее же считать прямо при итерации по второй размерности динамики. Итого получится O(N^2)

Подвесим дерево за какую-нибудь вершину. Посчитаем динамику: downSq[v] сумма квадратов путей до всех вершин вниз, чтобы ее пересчитывать понадобится down[v] сумма путей до всех вершин вниз. Тогда просто

down[v] = sum(c is children of v, down[c] + count(c) * w(vc))

где w(vc) — вес ребра, count(c) — количество вершин в поддереве c

downSq[v] = sum(c is children of v, downSq[c] + 2 * down[c] * w(vc) + count(c) * (w(vc)^2))

Формула может быть немного неправильная, если что исправьте, главная идея, что если к элементу прибавить d, то квадрат изменится на 2 * d * val + d ^ 2.

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

D. Сортировка, но чуть-чуть необычная. Рассмотрим две произвольные строки s1 и s2. a1=s1+s2, a2=s2+s1. Если a1<a2, то строка s1 будет раньше чем строка s2, иначе позже.

A. f[i][j][k] = можно ли дойти до клетки (i,j) и не показаться на всех снимках с 1 по k. Если можно, то храним откуда пришли. Ну а потом восстановление ответа.