Shtrix's blog

By Shtrix, 14 years ago, In Russian
А)          Необходимо было отсортировать все дома по возрастанию координаты центра х. Для каждой пары последовательных домов (x_i, a_i) и (x_(i+1), a_(i+1)) определить расстояние между домами:
d = x_(i + 1) - x_i + a_(i+1) / 2 + a_i / 2;
если d > T то ans = ans + 2
если d == T то ans = ans + 1
иначе ничего не делаем
в конце к ответу нужно было добавить два, чтобы еще закрыть крайние позиции.

B)            Для простоты написания, нужно было заметить, что геометрическое место точек которые можно выжечь лазером это два прямоугольника. Оставалось только посчитать их суммарную площадь, что делается очень просто по формуле включения-исключения. И не забудьте про 64 битное целое!

С)             Еще раз извиняюсь за ошибку в описании входа. Прочитав немного материала по теории игр и числам Шпрага Гранди вам станет очевидно, что для решения этой задачи достаточно проксорить все числа: x_1, x_1 + 1, ... x_1+m_1-1, x_2, x_2 + 1, .. x_2+m_2 ... x_n, x_n + 1, ... x_n + m_n - 1 и определить является ли результат нулем или нет. Что правда учитывая их количество вам не удастся вложится в ТЛ. По-этому заметим что Вам требуется проксорить не просто какие-то числа, а несколько отрезков вида [x_i, x_i + m_i - 1]. Пускай f([a,b]) = a^(a+1)^(a+2)..^(b - 1) ^ b.
Так как f([x_i, x_i + m_i - 1]) = f([1, x_i + m_i - 1]) ^ f([1, x_i  - 1]); можно ксорить отрезок за О(1), учитывая то что f([1,x]) можно считать так:
if (x mod 4 == 0) f(x) = x;
if (x mod 4 == 1) f(x) = 1;
if (x mod 4 == 2) f(x) = x + 1;
if (x mod 4 == 3) f(x) = 0;
тогда имеем сложность решения О(N)

D)              Решать ее стоило так:
1. Перебрать все левые верхние углы прямоугольников годных для размещения города и для каждого из них посчитать количество земли которую бы было необходимо вывезти для того, чтобы построить город. Для этого нам необходимо считать сумму на прямоугольнике и минимум. Первое делается частичными суммами, а второе на выбор либо двумерным деревом отрезков, либо для этого можно приспособить очередь с минимумом за О(1) (вместо нее также подойдет эмуляция ее с помощью STL-евских multiset и priority_queue).
2. После первого этапа необходимо собрать все данные в массив в форме (<количество вывезенной земли,  координата верхнего угла>) и отсортировать его в лексикографическом порядке (по увеличению количества земли).
3. Пройтись по уже отсортированному массиву проверяя можно ли поставить в данной клетке левый верхний угол города. Для этого нужно оценить не накладывается ли он на уже поставленный. Это можно делать заведя массив булеанов used[][] в котором будут отмечаться уже покрытые клетки. При добавлении города нужно будет просто оббегать весь прямоугольник и проставлять в его клетках true, а при запросе на возможность покрытия будем смотреть только на угловые клетки. (Так "халтурить" можно потому что у нас все прямоугольники одинакового размера и статической ориентации). Не сложно посчитать, что таким образом будет выполнено в сумме не более N*M операций.

E)           Можно было перейти к графу двойственному данному и обнаружить, что он дерево, а также установить взаимно однозначное соответствие между путями о которых шла речь в условии и не пустыми компонентами связности включающих корень данного дерева. Такие компоненты легко считать используя ДП по дереву: DP[u] = (DP[child1] + 1) * (DP[child2] + 1), DP[leaf] = 1. Но конечно такое решение не укладывалось в ТЛ и потому нужно было используя уравнение ДП свести к комбинаторной формуле благодаря рекуррентному соотношению между "нишами"(поддеревья которые идут от края карты вглубь). 
  • Vote: I like it
  • +14
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is there an English version of the Contest #15 Report?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I couldn't pass D in Test #7. Could someone give some tips?