152A - Оценки
В этой задаче нужно было сделать ровно то, что написано в условии. Вот приблизительный код решения.
for (int i = 0; i < n; ++i){
bool wasBest = false;
for(int j = 0; j < m; ++j){
bool isBest = true;
for(int k = 0; k < n; ++k)
if(a[k][j] > a[i][j])
isBest = false;
if(isBest)
wasBest = true;
}
if(wasBest)
ans++;
}
152B - Шаги
В этой задаче нужно бюло посчитать формулу — для позиции (x, y) и вектора (dx, dy), сколько шагов до упора может сделать мальчик. Эту же величину можно было считать пользуясь "почти" бинарным поиском. Ниже приведу код вычисления этой величины, написанный RAD.
for (long long cof = 1100000000; cof; cof /= 2)
while (onField(xc + cof * dx, yc + cof * dy)) {
xc = xc + cof * dx;
yc = yc + cof * dy;
ans += cof;
}
152C - Записная книжка
В этой задаче нужно было заметить, что на месте первого имени можно получить любое имя специального вида. А именно, любое имя вида s = s1 s2 s3 s4 ... sm, где s1 — первый символ любого из заданных имен, s2 — второй символ любого из заданных имен, ... sm — m-й символ любого из заданных имен. Тогда ответ на задачу — это произведение cnti (1 ≤ i ≤ m), где cnti — это количество различных букв стоящих в именах на позиции i.
152D - Рамки
Нужно было понять: нарисовано ли на картинке две рамки.
Так как у рамок длина стороны была не менее 3, то давайте выделим те x- и y-координаты, на которых встречаются хотя бы 3 подряд идущих символа '#'. Понятно, что координаты углов рамок следует выбирать только из этих выделенных x и y. В общем случае различных выделенных x не более 4, и различных выделенных y не более 4.
Кроме случая, когда высота или ширины одной из рамок 3, а длина больше 3, и одна из сторон второй рамки заполняет хотя бы часть внутренности первой.
Например:
####### ####### ####### #.....# #######
Первая рамка:
####### #.....# ####### ....... .......
Вторая рамка:
....... ####### #.....# #.....# #######
В примере различных y-координат 7.
Аккуратно обработаем такие случаи отдельно, что вполне просто. (Оставим всего 4 y-координаты: минимум, максимум, второй минимум и второй максимум).
Иначе, если количество выделенных x- и y-координат не более 4, то переберем углы первой первой и второй рамки и проверим, что выбранные рамки — корректные рамки и нет лишних символов '#'. Проверка осуществляется за O(n + m) или за O(1) (с использованием частичных сумм).
152E - Сад
Задача решалась динамическим программированием. Пусть dp[mask][v] — это стоимость минимального корректного покрытия бетоном, если мы рассматриваем в качестве важных элементов только элементы маски mask и покрытие дополнительно покрывает вершину v = (i, j) поля.
Есть два вида переходов.
Во-первых мы можем, как бы разрезать покрытие по вершине v. Тогда нужно перебрать подмаску вершин submask, которые уйдут в левое покрытие и сделать соответсвующий переход. Обновить dp[mask][v] значением dp[submask][v] + dp[mask ^ submask][v] - cost(v).
Во-вторых, возможно, в данной вершине v в оптимальном покрытии маски mask, захватывыющим вершину v, нельзя сделать разрез разделяющий множество вершин. В таком случае, эта вершина образует своеобразный <<хвост>>. То есть существует такая вершина u, в которой можно сделать разрез, при этом кратчайший путь из вершины u в v целиком принадлежит оптимальному покрутию. Преподсчитаем заранее кратчайшие пути между всеми парами клеток. Теперь чтобы сделать этот переход, первоначально посчитаем значение динамики dp[mask][v] для всех вершин v только с учетом первого перехода. Теперь можно делать второй переход. Для всех u, dp[mask][v], обновить значением dp[mask][u] + dist(v, u) - cost(u).
Отдельно нужно обработать состояние, в котором ровно один бит в маске, при этом вершина соответсвующая этому биту равна v. В таком случае ответ, понятно, равен cost(v).
Таким образом, каждое получается решение за O(min(3k·n·m, 2k·(n·m)2)).
А может кто-нибудь рассказать какое-нибудь другое решение Е без динамического программирования?
Ну или хотя бы опровергнуть решение такое: найти Дейкстрой от каждого нужного участка до всех остальных кратчайший путь, запомнив участки, которые в него входят, затем построить из получившихся путей Краскалом дерево, после чего внести в ответ все участки, попадающие на ребра получившегося дерева. Понятное дело, что будут случаи, когда ребра накладываются друг на друга, но есть мнение, что все равно такой ответ будет оптимальным.
Дейкстрой не получится, т.к. не обязательно, если путь между участками самый короткий, то он входит в решение: (5й тест)
4 5 4
3 10 9 9 4
9 3 4 6 9
10 7 6 4 1
3 6 3 7 1
1 5
4 2
1 2
4 3
Если запустить Дейкстру из клетки (1, 5), то до вершины (1, 2) кратчайшим будет путь: (1, 5) -> (1, 4) -> (1, 3) -> (1, 2), но он не войдет в ответ.
.X..X
.XX.X
..XXX
.XX..
Ну, как и ожидалось.. И все-таки есть еще какое-нибудь решение кроме ДП?
А можно ли написать D как-то элегантно и коротко? Мне удалось её сдать только через полчаса после окончания соревнования и код получился монструозный.
Если реализовывать решение из разбора, то где-то 100 строк кода довольно понятного:)
Я не рассматривал отдельно случай как в разборе... а тупо перебирал все валидные углы из первых трёх и последних трёх "выделенных x- и y-координат". Получается довольно лаконично.
А зачем использовать бинпоиск в B?! Есть же такая тупая идея:
if dx > 0 then
tx := (n — x0) div dx;
if dx < 0 then
tx := (x0 — 1) div abs(dx);
if dx = 0 then
tx := INF;
{аналогично для y}
inc(ans, min(tx, ty));
Бинпоиск избавляет от разбора случаев, что получается компактнее, да и набагать в нем труднее.
Окей, принято. Хотя я не набагал и так не считаю :)
Ну, сам посуди, в бин. поиске ты просто перебираешь все возможные ответы и находишь верный, а в твоем решении надо понять когда на что делить и не забыть про случай с нулем. Возможно, кому-то это и проще, но я, как человек с маниакальной невнимательностью, предпочту первый способ. На самом деле я тоже написал, как и ты, но просто не додумался сразу до бин. поиска)
А это олимпиад-way — даже квадратное уравнение решать бин-поиском ;)
I was wondering if this idea is correct for task E ( I passed pretest in the competition but received WA10 at system test ). For each field of the matrix I run Dijkstra's algorithm with that field as source where cost ( u, v ) = Field[v] ( u and v are pairs of integers ). Then I reconstruct each paths from each of K important nodes to source and check if I have min path. Can you give me an example for which my idea fails or send me test #10. Thank you. :)
Если я не ошибаюсь, "почти бинарный поиск" из разбора называется "регулярный поиск". Каноничная реализация выглядит так:
Максимальное расстояние поиска 2*(1<<31)-1.
Я всю жизнь встречал название "двоичные подъемы".
Я, честно говоря, не понимаю, почто минусы.
Я выражение "регулярный поиск" встречаю первый раз. Тем не менее, термин "двоичные подъемы" я встречал действительно часто: начиная с одного из алгоритмов LCA, и заканчивая многими разборами разных задач, где применяется эта идея: что масштабируясь сверху вниз по степеням двойки, мы либо двигаемся вперёд, если влезаем, либо не двигаемся.
Более того, я так и не смог нагуглить хотя бы одно место, где такая штука называется "регулярный поиск". Просветите меня, где я неправ.
First time to write Dijkstra for task E, but it seems not the correct solution. Overall solution is not necessary to be shortest path for each pair.
I also have a solution similar to what they mentioned but a little different.
I try the following for each of the k! permutations of important nodes:
S={1stnode}
foreach i=2:k
1) Get shortest path between i and any of the nodes in S
2) Add cost of that path to total cost
3) Add nodes in that path to S
Minimize over all permutations.
It fails at test case 19 which is pretty large so I can even see fully. Can someone tell me what's wrong with the solution?
This is a simple 3*3 example(1 are important squares):
2 1 2
1 6 1
2 1 2
The answer is:
10
.X.
XXX
.X.
Your solution's ans:
12
XXX
X.X
XXX
Some nodes are useless if there are only 2 important squares(Only nodes in the shortest path is useful),but useful if there are many important squares. (Just think the square 6 above.It isn't in the shortest path of any pair important squares,but it's benefit for all the important squares.) So considering only one node each time is incorrect.
I see your point. Thanks a lot :)
I tried this approach of minimization over all permutations of the k important nodes by doing the following:
for each permutation
i from 1:K-1:
calculate the sortest path from i to i+1
all grid positions along the shortest path are reseted to 0
reset the grid to original after each permutation
gets WA on test case 10. I wonder if this idea is simply wrong. By the way, it works for the sample given by coolingging.
I must confess I was a bit surprised at the "almost binary search" suggestion for problem B. You can just do straight divisions to check the maximum amount of steps possible!
Problem E is a good problem. I feel that i learned a lot.
1206361 — человек очень веселым образом выводит ответ.
P.S. Занял последнее место с результатом -1266 баллов.
я правильно понимаю, что в следствие отсутствия randomize у него random(4) всегда будет принимать одно и то же значение, при том отличное от 1? так-то неплохой способ заствить торопливых людей постараться завалить его решение и тем самым получить минус.
Вообще да, конечно, взламывать можно. Но стоит ли пробовать? Даже при наличии
randomize();нужно иметь достаточно хорошую карму, чтобыrandom(4);вернул 1. В среднем из 4х взломов пройдет 1, ты заработаешь 100 баллов за успешный взлом, но -150 за неуспешные.обфускация на лицо :(
I think that E is a very good state of the compressed DP problem,and It is very similar with the 2008 Chinese Informatics Olympiad winter camp's test of trip ( tour plan ).I think tha they are all good.
почему в тегах к задаче Е есть "деревья"? Можно как-то решить используя деревья?
кэп проясняет, что ответ к задаче это дерево минимального веса, содержащее все нужные вершины.
По поводу задачи E — Я не придумал дп на масках, но придумал ДП по профилю, не стал его кодить, ибо надо было уходить. Но успел оценить число профилей, у меня получилось что ширина профиля 14 клеток и всего профилей порядка 40 тысяч. умножить на 200 (позиция, где сейчас излом профиля) и переход за O(14) Возможно такое получиться упихать в две секунды.
Сань, опиши подробнее, пожалуйста, очень интересно было бы такое решение почитать =) я тоже на масках придумал, с профилем ничего путного в голову не пришло, очень хочу твой разбор почитать. Только сдай предварительно, чтобы не было голословным ;)
вот код но он падает на 6-ом тесте по WA, возможно набагал при поворотах, а может идейно.
идея — дп по изломанному профилю, профиль содержит 0 если в клетке пусто, или номер компоненты связности (нумеруем от единицы). Если мы по ходу дп натыкаемся на крутую клетку, мы не имеем права её не взять, а также нужно следить за тем, чтобы существующие компоненты связности не остались в конце концов изолированными, т.е. в конце чтобы осталась ровно одна компонента. Думаю что даже если это отдебажить, прога получит ТЛ неизбежно.
UPD: Я переписал часть с поворотом, сделал кучу проверок на целостность, на соответствие инпуту, все равно WA, странно.
ссылку код обновил, теперь получает заслуженный TL профилей выходит больше чем 1 << 19, я не правильно оценил их количество во время контеста. Но при меньших ограничениях на ширину поля, это могло проходить, так что можешь посмотреть код, раз было интересно как такое кодится.
can someone tell what's the meaning of "name number 1" in problem statement C -> Link
I will be grateful.
Thanks.
I also can't get the idea!! Since we are swapping prefix and i & j should be >=1 & <=n. thats a problem for me!! Is this possible that, After swapping I've got a new word then I can also perform swap operation on this??
Yes!! I've got it in my manner. Suppose, you have ABC & DEF .. then the possible different names are ABC,DEF,AEF,DBF,ABF,DEC,AEC,DBC=8 . Go with some example in paper.
В задаче Е заходит решение, в котором перебираются три вершины, которые будут добавлены в важные, а потом между полученными важными вершинами строится минимальный остов. Магическое число 3 как-то можно обосновать, или это просто тесты такие?
Could anyone please give a more elaborate explanation of the solution of problem E.
Can somebody plz explain what does v represent in dp[mask][v] as explained in the editorial of Question E Garden
In the complexity analysis of problem E, you forgot to account for all pairs' shortest paths precomputation. Usually one would use Floyd-Warshall for APSP with a complexity of $$$O((n \cdot m)^3)$$$. However, the graph in this problem is sparse with $$$|E| \le 4 |V|$$$, making a series of $$$O(|V|)$$$ Dijkstras another viable solution with the overall complexity of $$$O((n \cdot m)^2 \log (n \cdot m))$$$.