Opencup, GP of Central Europe

9 лет назад, # ^ |

В некоторых задачах ведь и было до сотых:)

Интересно, как именно определяли эти TL. Аккуратно подогнали вручную? Если взять ограничения с pdf с ejudge, и поделить на ограничения на Яндексе, то для разных задач получаются ощутимо различные результаты.

И еще, у кого более-менее быстро работало решение G — можете показать? Хочу понять, что именно мы делали плохо:) По остальным задачам решения без особых оптимизаций заходили с двукратным запасом, а здесь у нас еле-еле 0.97.

→ Ответить

snarknews

9 лет назад, # ^ |

Таймлимиты ставились как 5x от времени запуска лучшего авторского решения (model solution) на c++ на каждой из систем. Запускалось одно и то же решение. Разные отношения TL показывают, что Xeon с Яндекса и Quad Core с OpenTrains работают по-разному, и к простому масштабированию это не сводится.

Дробные TL вызваны тем, что во время прошлых Гран-При были ситуации, когда в погрешность округления до целых "пролезало" изрядное количество решений.

→ Ответить

Goofy57

9 лет назад, # ^ |

+39

А как объяснить то, что времена работы программы на различных запусках порой очень сильно различаются в Яндекс Контесте? У нас на 5 последовательных посылках в дорешивание задачи J вердикты варьируются от 2.1 ОК до 2.3 TL (и, как поговаривают тут на сборах, это различие бывает еще сильнее). И это то самое решение, которое, как нам кажется, работает локально максимум 0.5 секунд.

→ Ответить

yarrr

9 лет назад, # ^ |

← Rev. 4 →

+17

Меня тут попросили приложить некие доказательства, так вот они.

Задача E1 со сборов в МФТИ. Мое кривое n * lg(n)² решение с простым кодом: http://pastie.org/private/mlyvxyzzczqi2g3yzdfl3w

Вердикты на разных запусках: http://i.imgur.com/rBSz4k6.png

Задача L7 с тех же сборов: http://pastie.org/private/05vj1xwlfdsao9iaypa

Вердикты: http://i.imgur.com/6d7jWJb.png

Я не знаю, что там прогревается и как тестируется, но я искренне считаю, что разницы в 35% быть не должно, иначе это приводит к всяким шаманизмам вида "отправим решение 5 раз, авось пройдет".

→ Ответить

pavel.savchenkov

9 лет назад, # ^ |

G: 235 ms

→ Ответить

9 лет назад, # |

← Rev. 2 →

F: построим разбиение на циклы (произвольное), потом помержим соседние циклы пока все не смержится. Как строить разбиение на циклы: достаточно пройтись сверху вниз, добавляя ребра в приоритете "лево", "право", "низ". Это вроде бы доказуемо работает, правда там неприятный разбор случаев, мы на контесте до конца не доказали.

Upd. Translation to English, requested by dragoon.

First, let's construct a set of cycles, and then merge them into a single cycle. Merging is actually quite easy: 2 cycles which have at least 1 neighboring segment can be merged into a single one with a trivial transformation.

So, the problem is reduced to the following: "assign edges so that each cell has exactly 2 edges incident to it" (this is equivalent to constructing a set of cycles). It turns out that this can be done quite easily: iterate over board from top to bottom and add missing edges with the following priority: "left", "right", "bottom". It seems to be provably correct, but there are many cases one needs to take into account in the proof, so we didn't bother with the complete proof during the contest.

→ Ответить

9 лет назад, # |

← Rev. 3 →

B. Посортим запросы по ёмкости, пройдём по ним в этом порядке. Понятно, что в каждый момент времени множество заправок — набор компонент связности, которые merge'атся с увеличением ёмкости. Понятно, что моменты merge — это когда мы достигаем минимального расстояния между заправками. Такие event'ы можно по-разному обрабатывать, мы просто для каждого ребра добавили событие (Merge ближайшей заправки левого конца и ближайшей заправкт правого конца, момент времени — (расстояние до левого конца от его ближайшей заправки + расстояние до правого конца от его ближайшей заправки + длина ребра)).

Итого решается за Дейкстру + сортировку.

Upd. Translation to English, requested by dragoon.

Let's sort queries by capacity. For each fixed capacity, the set of stations consists of several connected components; these components merge if capacity increases.

Let's find the moments of merging. Two stations merge when the capacity is equal to the shortest distance between these stations. So, let's iterate over all edges in the graph. Consider edge e = (v₁, v₂). Let s₁ be the closest station to v₁, s₂ — the closest station to v₂. Then, we add event at capacity dist(s₁, v₁) + dist(s₂, v₂) + len(e) to merge components of s₁ and s₂. Note that we're only interested to the closest stations to the ends of each edge.

So, the solution is as follows. Compute shortest distances to all nodes from stations, add events, sort them (together with queries) and process the events with DSU. I.e., the code is just Dijkstra + sort() + DSU.

→ Ответить

Ac-93

9 лет назад, # |

+11

Кто может рассказать E?

→ Ответить

el_sanchez

9 лет назад, # ^ |

+30

Если n не делится на gcd(p, q), то, конечно, игра продлится бесконечно.

Иначе сначала сделаем вынужденные ходы-прибавления (не более 2), не умаляя общности, ход снова за первым игроком и имеется n камней.

Пусть n не делится на p, иначе ответ понятен. Тогда, если p < q, то мы всегда можем оставлять не более p - 1 камней и вынудить этим соперника положить ещё ровно q. Тогда за конечное время получится забрать всё (например, из соображений о разрешимости диофантова уравнения px + qy = n).

Остаётся p > q. Тогда, если мы в какой-то момент оставим хотя бы q камней, то сработает предыдущий случай, но уже для соперника, поэтому надо делать единственно возможный ход в от 0 до q - 1 камней (если он есть, иначе мы проигрываем). Останется n mod p камней. Далее по той же логике их количество станет уменьшаться на p - q, поэтому, если n mod p делится на p - q, то мы победим, иначе инициатива будет передана противнику.

→ Ответить

TonySnark

9 лет назад, # |

Может ли кто-нибудь рассказать, как решать С? Нужно было как-то усовершенствовать простое ДП по маске товаров и числу рассматриваемых магазинов?

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

Зачем число магазинов? Просто ДП по маске (ну и разумеется для каждой маски товаров посчитать, из какого магазина и за сколько эту маску выгоднее всего брать).

→ Ответить

TonySnark

9 лет назад, # ^ |

Спасибо!

→ Ответить

9 лет назад, # ^ |

А как учитывать что можно получить одинаковую цену из различных магазинов?

→ Ответить

9 лет назад, # ^ |

В смысле? Мы на каждом шагу покупаем какую-то маску из какого-то магазина. Понятно, что покупать маску надо только из самого выгодного для неё магазина (даже если их несколько; нам интересна только оптимальная цена). Т.е. решение выглядит так: предпросчитываем для каждой маски оптимальную цену, потом динамика по всем маскам с перебором подмасок и переходом с использованием оптимальной цены.

→ Ответить

9 лет назад, # ^ |

Пока писал что я имею в виду, понял что это что-то нереальное.

Спасибо, зашла.

→ Ответить

9 лет назад, # ^ |

+30

Кстати, можно действительно написать динамику по маскам и магазинам:) Получится n * m * 2^m. Почти так же, как и стандартная динамика "какой лучший ответ для маски х, если использовали только первые у магазинов", но дополнительно храним в маске 0/1 — покупали мы уже что-то в текущем магазине или нет. Тогда если пытаемся купить при 0 в этом флажке — к цене товара прибавляется цена посещения самого магазина.

→ Ответить

iensen

9 лет назад, # ^ |

← Rev. 3 →

А как получается n·m·2^m?

Пусть мы сейчас в магазине N, и у нас есть маска M. В этом магазине можно купить любую комбинацию товаров, которые еще не были куплены. Получается, если K товаров не куплены, то есть 2^K вариантов что-либо купить.

Суммарно выходит вроде n·3^m У вас есть код? Как делать переход за O(m)?

→ Ответить

9 лет назад, # ^ |

Так переходы ведь будут по одному предмету, а не сразу на произвольную маску — если К товаров не куплены, то есть К вариантов перехода-покупки.

Исходный код.

→ Ответить

iensen

9 лет назад, # ^ |

Понятно,cпасибо! Я писал что-то похожее, но в состоянии динамики зачем-то еще хранил последний купленный предмет. Получалось O(2^m * m² * n), и Time Limit Exceeded.

→ Ответить

9 лет назад, # |

Как решать K?

Я делал граф из отдельных координат по иксу и по игреку, соединял рёбрами соседние координаты. Плюс добавлял нулевые рёбра вида X-Y из ввода. Ну и находил кратчайший путь из начальных координат в конечные. Это TL10.

→ Ответить

scorpion

9 лет назад, # ^ |

+23

Для каждой вершины не больше четырех ребер нужно добавить: отсортировали по иксу — добавили соседей и аналогично по игреку.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

Действительно, можно было и так. Спасибо.

Обидно. Асимптотика та же самая.

UPDATE: Оказывается дело было в алгоритме поиска кратчайшего пути. Первый раз он меня так подвёл. Поменял на дейкстру с e-maxx.ru и получил AC.

→ Ответить

rsFalse

9 лет назад, # |

← Rev. 2 →

In div.2 I tried to solve O (or N in my pdf problem set). About Hacktris. How did you solved it? I tried slow variant — O(W*H), but have a mistake at 27 testcase. Can't find my mistake — http://ideone.com/W6eUNZ (Perl)

→ Ответить

dragoon

9 лет назад, # |

I guess only remaining are H, I and J. Any thoughts?

→ Ответить

9 лет назад, # ^ |

J. Let's choose some root. For each speleologist, let's compute the highest node in the tree which he can reach on his path (LCA + binary ascent, or how is it called in English). These nodes should form a chain, otherwise the answer is "NIE". Let's take the lowest node from the chain and check it (2 LCA per speleologist). If all the checks pass, we know the answer otherwise the answer is "NIE".

So, we have 3 LCA and 1 binary ascent per speleologist, which fits in TL if implemented carefully.

→ Ответить

9 лет назад, # ^ |

+34

You can find analysis here.

→ Ответить