Чемпионат Урала 2013 (Интернет-версия)

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

Насчет задачи А дам краткую подсказку: все нужно считать в логарифмах.

Задачу F на онсайте придумал и написал я, поэтому про нее чуть больше. Идея за куб простая: идем по столбцам сначала слева направо, а потом наоборот, и для каждой строки храним положение последней встреченной точки, итого для ответа на запрос достаточно для каждой клетки проверить все строки. Теперь соптимизируем это все до квадрата. Заметим, что для если мы при обходе столбцов выкинем все точки, которое не могут быть ближайшими для точек в текущем столбце, то мы сможем найти ответ для всего столбца за линию двумя указателями (указание: для каждой пары "соседних точек" проведем серединные перпендикуляры к отрезкам, соединяющим эти точки, и они будут разделять области, в которых ближайшей точкой будет первая или вторая). Как же убрать "лишние" точки? Просто сделаем проход со стеком (наподобие того, что в алгоритме Грэхема), при добавлении точки будем рассматривать три верхних на стеке, а именно: проведем серединные перпендикуляры к двум имеющимся у нас отрезкам, проведенным между соседними точками, если точка их пересечения лежит левее текущего столбца (правее при обратном проходе), то среднюю точку можно смело выкинуть.

P.S. Решение на задачу F было навеяно алгоритмом Форчуна.

→ Ответить

I_love_Tanya_Romanova

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

По поводу F — проходил ли там куб на онсайте, и упихивается ли куб на Тимусе? После пачки различных оптимайзов и костылей у нас дошло до 26 теста, при том что тесты порядка 1000х1000 начинаются еще с 17, и они у нас в конце летали примерно за 0.3 секунды.

По поводу А — можно пример реализации решения с логарифмами? Нашему, похоже, не хватало точности. В результате пришлось переписывать все в инты.

→ Ответить

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

По слухам, куб на онсайте умудрилась пропихать топ-команда СПбГУ (я бы сам был не против услышать, как они это сделали). Насчет Тимуса: авторы обещали добавить тесты против куба, больше я ничего не знаю.

На самом деле, в А Jokser все-таки перестраховался и по результату вычисления в логарифмах отвечал только в случаях, когда был явный Slideshow и явный Perfect, все пограничные случаи он дополнительно разбирал на интах. Решение без интов, видимо, все-таки существует (абсолютной уверенности у меня нет).

→ Ответить

nk.karpov

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

← Rev. 2 →

Если бы вы посмотрели в монитор, то увидели, что эта команда не смогла сдать её. А вот свой куб пропихнула не топ команда СПбГУ. И вообще я на эту задачу в обиде... мы кучу времени ждали по ней AC =(

→ Ответить

gojira

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

+13

В A можно довольно просто поступить: раз каждая фича как минимум удваивает рисование картинки, при 30 фичах (на самом деле даже меньше — при log((максимальная производительность)/(минимальное разрешение)+1) оно обязательно Slideshow. Поэтому просто заводим set включенных опций и считаем замедление только когда их мало. При подсчёте, как только замедление превзошло производительность, сразу делаем break.

→ Ответить

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

-13

Вы использовали факт из условия, на который мы даже не обратили внимания. Очень простая и столь же красивая идея!

→ Ответить

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

У меня в дорешке по F зашла банальная Дейкстра, где соседи — все точки в квадрате 7x7 около данного. Жаль, на контесте около часа пытался запихнуть решение на стандартных сетах — был ТЛ, на своей структуре сразу зашла =(

→ Ответить

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

С Евклидовыми расстояниями в качестве весов ребер?

А как доказывается правильность подобного решения? И правильное ли оно вообще?

→ Ответить

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

← Rev. 2 →

Нет, расстояния вообще считались сразу до соответствующего центра.

То есть алгоритм такой: храним для каждой клетки квадраты расстояний и текущий центр, на котором достигается этот ответ. Изначально кидаем в кучу центры баз, затем на каждом шаге достаем минимум (по расстоянию), делаем ответ для него "окончательным", и релаксируем его соседей (обновляя центр на центр текущего вытащенного минимума и расстояние до этого центра, если оно меньше).

Доказательство корректности — не знаю, изначально мне вообще казалось, что должно работать, даже если рассматривать только непосредственных соседей данной клетки. Но зашло только с рассмотрением всех соседей в радиусе 3 клетки (что, кстати, мне до сих пор непонятно).

→ Ответить

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

К сожалению, Ваше решение все-таки ботва...

Я нашел такой тест, для которого квадрата 3х3 будет недостаточно. Тест, решение за куб для проверки ответа (тестировал я его наспех, вроде правильное, но советую перепроверить код).

Вы изначально сделали ошибочное утверждение: "Все единичные квадраты, центры которых лежат в одной ячейке диаграммы Вороного, образуют связную область".

Расскажу чуть-чуть про особенности теста. В нем точки подобраны так, что они равноудалены от правого нижнего угла квадрата (124; 29) (0-индексация). Если нарисовать диаграмму Вороного, то получится, что центр квадрата (121; 29) находится в средней ячейке, однако, он изолирован от ближайших к нему квадратов с центрами в средней ячейке — (116; 28) однозначно и (117; 28) на границе с левой ячейкой. Так что Ваше решение выдаст для квадрата (121; 29) ответ 14765 вместо 14761.

→ Ответить

trillioner

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

← Rev. 2 →

А вы дорешали задачу А, просто у меня тоже WA#9?(делал с логарифмами) P.S.Accepted, походу проблемы были из-за погрешности, потом написал как Jokser.

→ Ответить

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

+15

Чемпионат Урала славен, как всегда, своими кошмарными условиями....

→ Ответить

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

По поводу задачи С.

Я умею ее решать за квадрат триангуляцией многоугольника, разбором случаев, когда точки лежат в одном треугольнике и в разных треугольниках, и взятием четырехкратного интеграла от полиномиальной функции. Однако, на закрытии я слышал про какую-то формулу, зависящую только от площади многоугольника. Может ли кто-нибудь напомнить эту формулу и то, как она выводится?

→ Ответить

Stigius

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

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

→ Ответить

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

А интересно, авторы сами вывели интегрированием эту константу 4/27, или нашли в готовом виде? Я пытался получить ее методом Монте-Карло. но ее очень трудно отличить от 3/20 — пришлось внимательно считать сэмпл.

→ Ответить

Stigius

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

Честно проинтегрировали. Монте-Карло здесь явно не даёт достаточной точности, чтобы на него можно было полагаться.

→ Ответить

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

На самом деле, если подумать, Монте-Карло выдает что-то между 0.14 и 0.15. Если еще подумать, то крайне маловероятно, чтобы дробь склеивалась из чего-то кроме 2 и 3 — 4/27 в самый раз. Оно, конечно, шарлатанство, но ведь работает же.

→ Ответить

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

Очевидно, что формулы, зависящей только от площади и количества точек нет - для четырехугольника ответы будут разные в зависимости от соотношения площадей частей. Все дело в магической константе 4/27, которую нетрудно вычислить из сэмпла.

→ Ответить

Monyura

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

А чем вызван такой суровый ML в задаче G, это специально чтоб динамическое дерево отрезков рубить?
Просто оно тут выглядит вполне закономерным решением, но по памяти не помещается.

→ Ответить

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

← Rev. 2 →

Насколько мне известно, на Тимусе просто не поддерживается МЛ больше 64МБ. Если не прав — прошу поправить.

Хотя для Битвы Гигантов выставляли 512МБ, так что я скорее всего действительно не прав.

→ Ответить

droptable

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

← Rev. 2 →

→ Ответить

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

Очень, кстати, неудачный принцип — из-за более жестких лимитов на Тимусе результаты несопоставимы с онсайтом (тем более что задачи, в которых неоптимизированное решение работает на грани ТЛ/МЛ, на чемпионатах Урала встречаются довольно часто, и меньшие лимиты на Тимусе создают заметный гемор и тратят время на запихивание)

→ Ответить

droptable

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

← Rev. 2 →

→ Ответить

BekzhanKassenov

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

← Rev. 2 →

Не читайте, я дурак

→ Ответить

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

Ну если сейчас все на Тимусе — тогда хорошо.

Просто в былые времена, помню, на онсайте ТЛ был 5-10 сек, например, а на Тимусе — 3. Это сильно искажало результаты.

→ Ответить

O_A

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

How to solve Problem J(Road to Investor)?

→ Ответить

KrK

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

1) bsearch the overspeeding (o)

2) assume that you overspeed with o through every edge, so your total speed is vi + o.

3) then use Dijkstra on time and see if you can get to n in no more than T.

→ Ответить

O_A

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

thank you.

→ Ответить

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

Кто как решал В? Слышал про рандомизированное решение от Jokser, но не врубился до конца. Есть ли конструктивное решение?

→ Ответить

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

← Rev. 4 →

-8

На самом деле, то решение, которое придумали Jokser и mexmans, полностью детерминированное, но не доказанное.

Задачу проще всего объяснять в терминах n-мерного гиперкуба {0;1}ⁿ, в котором нам нужно найти наидлиннейший путь между двумя вершинами. Заметим, что если четность координат начальной и конечной вершины одинакова, то Гамильтонов путь между этими вершинами не существует (т.к. в Гамильтоновом пути 2ⁿ - 1 ребро, а при переходе по ребру четность координат меняется), поэтому в таком случае будем искать путь длины 2ⁿ - 2.

Идея решения: разрежем гиперкуб поперек той координаты, которая у начальной и конечной вершин различаются (назовем ее x_i). Далее обойдем "первую" половину, перейдем вдоль координаты x_i и обойдем вторую половину. Как именно делать эти обходы — додумай сам (советую начать с разбора случая, когда начальная и конечная точка различаются только по одной координате).

→ Ответить

foxermen

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

Подскажите, как решается задача D, про оптимизацию.

→ Ответить

Monyura

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

Можно узнать какое решение предполагали авторы по G? ДО над массивом чисел из запросов с операциями добавления на отрезок числа, добавлением на отрезок арифметической прогрессии и обнулением на отрезке тлешится. Да и по памяти впритык, если вообще поместится.

→ Ответить

riadwaw

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

На зарытии говорили, что ДО

→ Ответить

knightL

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

+10

ДО заходит. 7 тест вроде еще не самый сложный. Правда в моём ДО был другой набор операций: добавление на отрезок арифметической прогрессии, установление отрезка в число и сумма на отрезке. Правда из-за сжатия координат пришлось еще одно дерево держать — количество реальных точек на отрезке.

→ Ответить

Monyura

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

Я вот тоже не могу понять, почему моё не успевает ответить даже на 60 000 запросов, там конечно большая константа, но не на столько же. А как ты добавляешь на отрезок арифметическую прогрессию, без прибавления на отрезок числа? Ведь добавление прогресии разбиваеться на добавление прогресии к левому отрезку и добавления числа + прогресии к правому.

→ Ответить

knightL

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

ну это такой вопрос... Я считаю, что прибавление арифметической прогрессии это прибавление к i-тому элементу числа a+i*b, а этой операции почти не нужны никакие вспомогательные.

Просто можно подумать, что прибавление константы используется для того, чтобы добавить энергию, которая накопилась с предыдущей операции, ко всем секциям, а я этого не делаю. Если дополнительно делать прибавление ко всем вершинам, которые соответствуют реальным секциям стены, то моё решение проходит совсем впритык.

→ Ответить

thnkndblv

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

Can somebody give me an idea for F. Game Optimization?

→ Ответить

Xellos

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

A possible solution (I never tried to implement it, I'm too lazy):

consider the squares in a single row; we pass those squares once from the left and once from the right, only counting distances from the bases in the columns we've passed already; the result for any square is the minimum of those 2 values for this square
in every column, it's apparently enough to consider the bases in rows closest to our row, so for every square, the distance we're looking for is a minimum of some quadratic functions for given x-coordinate (the y-coordinate is the same in our row)
now, observe that if we have quad. functions in forms

f(x)=x**2+Ax+B; g(x)=x**2+Cx+D

where f(x) > g(x), A > C, then for any larger x, we'll still have f(x) > g(x), so we can just forever forget the base corresponding to f(x) and never check if it gives the minimum - so, we need to keep a list of possible functions (bases) and be able to choose the one that gives a minimum and drop one all which can't give a minimum anymore (and add one, but that's trivial), and very fast. So we keep their linked list, sorted decreasingly in f(x) and increasingly in the linear coefficient (A), and in a heap, we keep "events": the minimal x for which a function with larger A obtains a larger value than the one right before it in the list; when we move to the next square in the row and add the (at most 2) nearest bases in that column, we keep deleting functions for which this happens and re-calculate those values in the heap (we still need to take care of situations in which the other function of the given event has been deleted already), and then choose the last function in the list. It's similar to slope optimization in dynamic programming.

every function add/delete can be processed in log time (we only have O(C) functions and therefore also events); we do this for every row, so total time is O(RC log C).

→ Ответить

Jarekczek

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

← Rev. 4 →

From every base send 4 spies in four directions. Initial ~~lenght~~ width of the spy is 1, but with each step we add 1 dot on both sides. Spy tries to update the dots it meets, if he is the first to reach a dot. When a spy detects that it stumbled on the area closer to another spy (who visited the dot earlier) it reduces its line.

The idea is taken from stones thrown into water, but instead of circles there are squares.

In my implementation I was checking the spy line and if there was a gap of length at least 3, the line was split to skip that hole (spies are split as well, so their number grows in this case). In dense board many spies get quickly totally removed. Spies are kept in queue.

I was so curious whether this approach was acceptable. Now that timus released this problem, I know it works (got AC with 1.23 s, however needed to work hard on memory usage, using bit fields).

→ Ответить

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

Есть идея, на которую можно опираться при решении H. Возьмем два вектора и выясним, для каких θ проекция первого вектора на единичный вектор (cosθ;sinθ) будет больше проекции второго, а для каких — наоборот.

На основе этой идеи строится решение с сортировкой O(n²) углов, а после сортировки найти оптимальный ответ можно за O(n²).

Мое решение на Java, в котором я сортировал не углы, а вектора по их θ, заходит почти впритык (за 1.875с). Вопрос: можно ли избавиться от ресурсоемкой сортировки?

Especially for Timur_Sitdikov: твое решение использует всего 168 КБ памяти, так что у тебя никакой сортировки точно нет. Можешь сказать, как ты решал?

→ Ответить

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

← Rev. 2 →

Идея этого решения принадлежит команде СПб АУ, в частности его рассказал мне SergeyLazarev. Возьмем пучок из C направлений и просто для каждого направления найдем множества векторов мощности 1, ..., n такие, что проекция их суммы на данное направление будет максимальной (это делается сортировкой + жадностью). Ответ к задаче получаем, выбирая лучшее по всем C направлениям. Зашло при C = 5000, не проходило при 1000. Интересно было бы составить тест, ломающий это при больших C.

→ Ответить

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

А направления выбираем абсолютно рандомно?

→ Ответить

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

В моей реализации были направления на вершины правильного C — угольника. Возможно, рандом тоже прошел бы.

→ Ответить

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

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

→ Ответить

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

Тест:

3
1000000 9951
999999 10051
999998 10150

Ответ:

1000049.5100753763
2000099.017651376
3000148.5201757927

Твое решение, судя по всему, выдаст в первой строчке 1000049.5100263787.

→ Ответить

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

Это трудно представить, но в моей реализации ответ 1000049.5100753763 получается при С = 5000, а 1000049.5100263787 — при С = 4999! При этом тот же неверный ответ получается и при некоторых больших С (например, 6600). Спасибо за тест. Хотя, конечно, это еще не полноценный взлом — относительная погрешность слишком мала.

Написал решение в личное сообщение для экспериментов)

→ Ответить

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

Да, я забыл, что в условии сказано "абсолютная или относительная погрешность".

Судя по результатам некоторого матанализа, сделать тест, заваливающий твое решение с 5000 направлениями и при этом дающий относительную погрешность больше 5 * 10^- 8, невозможно. Так что быть твоему решению вечно со статусом AC :).

→ Ответить