| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
Здравствуй, сообщество Codefores!
Рад сообщить вам, что 3 августа на тимусе состоится интернет-версия XVII Чемпионата Урала.
Время начала соревнования в вашем часовом поясе вы можете посмотреть здесь.
Предлагаю после контеста обсудить задачи в комментариях.
GL & HF
UPD: Напоминаю, что до начала контеста осталось совсем немного.
Скажите , как решаются задачи А и F. По задаче А у меня не проходил 9 тест , а в задаче F — TLE на 29 тесте.
Насчет задачи А дам краткую подсказку: все нужно считать в логарифмах.
Задачу F на онсайте придумал и написал я, поэтому про нее чуть больше. Идея за куб простая: идем по столбцам сначала слева направо, а потом наоборот, и для каждой строки храним положение последней встреченной точки, итого для ответа на запрос достаточно для каждой клетки проверить все строки. Теперь соптимизируем это все до квадрата. Заметим, что для если мы при обходе столбцов выкинем все точки, которое не могут быть ближайшими для точек в текущем столбце, то мы сможем найти ответ для всего столбца за линию двумя указателями (указание: для каждой пары "соседних точек" проведем серединные перпендикуляры к отрезкам, соединяющим эти точки, и они будут разделять области, в которых ближайшей точкой будет первая или вторая). Как же убрать "лишние" точки? Просто сделаем проход со стеком (наподобие того, что в алгоритме Грэхема), при добавлении точки будем рассматривать три верхних на стеке, а именно: проведем серединные перпендикуляры к двум имеющимся у нас отрезкам, проведенным между соседними точками, если точка их пересечения лежит левее текущего столбца (правее при обратном проходе), то среднюю точку можно смело выкинуть.
P.S. Решение на задачу F было навеяно алгоритмом Форчуна.
По поводу F — проходил ли там куб на онсайте, и упихивается ли куб на Тимусе? После пачки различных оптимайзов и костылей у нас дошло до 26 теста, при том что тесты порядка 1000х1000 начинаются еще с 17, и они у нас в конце летали примерно за 0.3 секунды.
По поводу А — можно пример реализации решения с логарифмами? Нашему, похоже, не хватало точности. В результате пришлось переписывать все в инты.
По слухам, куб на онсайте умудрилась пропихать топ-команда СПбГУ (я бы сам был не против услышать, как они это сделали). Насчет Тимуса: авторы обещали добавить тесты против куба, больше я ничего не знаю.
На самом деле, в А Jokser все-таки перестраховался и по результату вычисления в логарифмах отвечал только в случаях, когда был явный Slideshow и явный Perfect, все пограничные случаи он дополнительно разбирал на интах. Решение без интов, видимо, все-таки существует (абсолютной уверенности у меня нет).
Если бы вы посмотрели в монитор, то увидели, что эта команда не смогла сдать её. А вот свой куб пропихнула не топ команда СПбГУ. И вообще я на эту задачу в обиде... мы кучу времени ждали по ней AC =(
В A можно довольно просто поступить: раз каждая фича как минимум удваивает рисование картинки, при 30 фичах (на самом деле даже меньше — при log((максимальная производительность)/(минимальное разрешение)+1) оно обязательно Slideshow. Поэтому просто заводим set включенных опций и считаем замедление только когда их мало. При подсчёте, как только замедление превзошло производительность, сразу делаем break.
Вы использовали факт из условия, на который мы даже не обратили внимания. Очень простая и столь же красивая идея!
У меня в дорешке по F зашла банальная Дейкстра, где соседи — все точки в квадрате 7x7 около данного. Жаль, на контесте около часа пытался запихнуть решение на стандартных сетах — был ТЛ, на своей структуре сразу зашла =(
С Евклидовыми расстояниями в качестве весов ребер?
А как доказывается правильность подобного решения? И правильное ли оно вообще?
Нет, расстояния вообще считались сразу до соответствующего центра.
То есть алгоритм такой: храним для каждой клетки квадраты расстояний и текущий центр, на котором достигается этот ответ. Изначально кидаем в кучу центры баз, затем на каждом шаге достаем минимум (по расстоянию), делаем ответ для него "окончательным", и релаксируем его соседей (обновляя центр на центр текущего вытащенного минимума и расстояние до этого центра, если оно меньше).
Доказательство корректности — не знаю, изначально мне вообще казалось, что должно работать, даже если рассматривать только непосредственных соседей данной клетки. Но зашло только с рассмотрением всех соседей в радиусе 3 клетки (что, кстати, мне до сих пор непонятно).
К сожалению, Ваше решение все-таки ботва...
Я нашел такой тест, для которого квадрата 3х3 будет недостаточно. Тест, решение за куб для проверки ответа (тестировал я его наспех, вроде правильное, но советую перепроверить код).
Вы изначально сделали ошибочное утверждение: "Все единичные квадраты, центры которых лежат в одной ячейке диаграммы Вороного, образуют связную область".
Расскажу чуть-чуть про особенности теста. В нем точки подобраны так, что они равноудалены от правого нижнего угла квадрата (124; 29) (0-индексация). Если нарисовать диаграмму Вороного, то получится, что центр квадрата (121; 29) находится в средней ячейке, однако, он изолирован от ближайших к нему квадратов с центрами в средней ячейке — (116; 28) однозначно и (117; 28) на границе с левой ячейкой. Так что Ваше решение выдаст для квадрата (121; 29) ответ 14765 вместо 14761.
А вы дорешали задачу А, просто у меня тоже WA#9?(делал с логарифмами) P.S.Accepted, походу проблемы были из-за погрешности, потом написал как Jokser.
По поводу задачи С.
Я умею ее решать за квадрат триангуляцией многоугольника, разбором случаев, когда точки лежат в одном треугольнике и в разных треугольниках, и взятием четырехкратного интеграла от полиномиальной функции. Однако, на закрытии я слышал про какую-то формулу, зависящую только от площади многоугольника. Может ли кто-нибудь напомнить эту формулу и то, как она выводится?
Авторское решение тоже за квадрат с триангуляцией. Проще чем ваше оно за счёт следующих наблюдений. Во-первых, для треугольников ответ действительно константа, умноженная на площадь (это легко доказать из свойств аффинных преобразований). Т.е. случай точек в одном треугольнике совсем тривиальный. Во-вторых, интегрируемая функция линейна по каждой из переменных, поэтому часть интегралов можно заменить на значение функции в средней точке, умноженное на длину отрезка интегрирования.
А интересно, авторы сами вывели интегрированием эту константу 4/27, или нашли в готовом виде? Я пытался получить ее методом Монте-Карло. но ее очень трудно отличить от 3/20 — пришлось внимательно считать сэмпл.
Честно проинтегрировали. Монте-Карло здесь явно не даёт достаточной точности, чтобы на него можно было полагаться.
На самом деле, если подумать, Монте-Карло выдает что-то между 0.14 и 0.15. Если еще подумать, то крайне маловероятно, чтобы дробь склеивалась из чего-то кроме 2 и 3 — 4/27 в самый раз. Оно, конечно, шарлатанство, но ведь работает же.
А чем вызван такой суровый ML в задаче G, это специально чтоб динамическое дерево отрезков рубить?
Просто оно тут выглядит вполне закономерным решением, но по памяти не помещается.
Насколько мне известно, на Тимусе просто не поддерживается МЛ больше 64МБ. Если не прав — прошу поправить.
Хотя для Битвы Гигантов выставляли 512МБ, так что я скорее всего действительно не прав.
.
Очень, кстати, неудачный принцип — из-за более жестких лимитов на Тимусе результаты несопоставимы с онсайтом (тем более что задачи, в которых неоптимизированное решение работает на грани ТЛ/МЛ, на чемпионатах Урала встречаются довольно часто, и меньшие лимиты на Тимусе создают заметный гемор и тратят время на запихивание)
.
Не читайте, я дурак
Ну если сейчас все на Тимусе — тогда хорошо.
Просто в былые времена, помню, на онсайте ТЛ был 5-10 сек, например, а на Тимусе — 3. Это сильно искажало результаты.
How to solve Problem J(Road to Investor)?
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.
thank you.
Кто как решал В? Слышал про рандомизированное решение от Jokser, но не врубился до конца. Есть ли конструктивное решение?
На самом деле, то решение, которое придумали Jokser и mexmans, полностью детерминированное, но не доказанное.
Задачу проще всего объяснять в терминах n-мерного гиперкуба {0;1}n, в котором нам нужно найти наидлиннейший путь между двумя вершинами. Заметим, что если четность координат начальной и конечной вершины одинакова, то Гамильтонов путь между этими вершинами не существует (т.к. в Гамильтоновом пути 2n - 1 ребро, а при переходе по ребру четность координат меняется), поэтому в таком случае будем искать путь длины 2n - 2.
Идея решения: разрежем гиперкуб поперек той координаты, которая у начальной и конечной вершин различаются (назовем ее xi). Далее обойдем "первую" половину, перейдем вдоль координаты xi и обойдем вторую половину. Как именно делать эти обходы — додумай сам (советую начать с разбора случая, когда начальная и конечная точка различаются только по одной координате).
Подскажите, как решается задача D, про оптимизацию.
Можно узнать какое решение предполагали авторы по G? ДО над массивом чисел из запросов с операциями добавления на отрезок числа, добавлением на отрезок арифметической прогрессии и обнулением на отрезке тлешится. Да и по памяти впритык, если вообще поместится.
На зарытии говорили, что ДО
ДО заходит. 7 тест вроде еще не самый сложный. Правда в моём ДО был другой набор операций: добавление на отрезок арифметической прогрессии, установление отрезка в число и сумма на отрезке. Правда из-за сжатия координат пришлось еще одно дерево держать — количество реальных точек на отрезке.
Я вот тоже не могу понять, почему моё не успевает ответить даже на 60 000 запросов, там конечно большая константа, но не на столько же. А как ты добавляешь на отрезок арифметическую прогрессию, без прибавления на отрезок числа? Ведь добавление прогресии разбиваеться на добавление прогресии к левому отрезку и добавления числа + прогресии к правому.
ну это такой вопрос... Я считаю, что прибавление арифметической прогрессии это прибавление к i-тому элементу числа a+i*b, а этой операции почти не нужны никакие вспомогательные.
Просто можно подумать, что прибавление константы используется для того, чтобы добавить энергию, которая накопилась с предыдущей операции, ко всем секциям, а я этого не делаю. Если дополнительно делать прибавление ко всем вершинам, которые соответствуют реальным секциям стены, то моё решение проходит совсем впритык.
Can somebody give me an idea for F. Game Optimization?
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.
From every base send 4 spies in four directions. Initial
lenghtwidth 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).
Есть идея, на которую можно опираться при решении H. Возьмем два вектора и выясним, для каких θ проекция первого вектора на единичный вектор (cosθ;sinθ) будет больше проекции второго, а для каких — наоборот.
На основе этой идеи строится решение с сортировкой O(n2) углов, а после сортировки найти оптимальный ответ можно за O(n2).
Мое решение на Java, в котором я сортировал не углы, а вектора по их θ, заходит почти впритык (за 1.875с). Вопрос: можно ли избавиться от ресурсоемкой сортировки?
Especially for Timur_Sitdikov: твое решение использует всего 168 КБ памяти, так что у тебя никакой сортировки точно нет. Можешь сказать, как ты решал?
Идея этого решения принадлежит команде СПб АУ, в частности его рассказал мне SergeyLazarev. Возьмем пучок из C направлений и просто для каждого направления найдем множества векторов мощности 1, ..., n такие, что проекция их суммы на данное направление будет максимальной (это делается сортировкой + жадностью). Ответ к задаче получаем, выбирая лучшее по всем C направлениям. Зашло при C = 5000, не проходило при 1000. Интересно было бы составить тест, ломающий это при больших C.
А направления выбираем абсолютно рандомно?
В моей реализации были направления на вершины правильного C — угольника. Возможно, рандом тоже прошел бы.
В целом, между таким решением и рандомом большой разницы нет. Я попробую придумать контрпример против того и другого. Вроде, должно валиться.
Тест:
Ответ:
Твое решение, судя по всему, выдаст в первой строчке
1000049.5100263787.Это трудно представить, но в моей реализации ответ 1000049.5100753763 получается при С = 5000, а 1000049.5100263787 — при С = 4999! При этом тот же неверный ответ получается и при некоторых больших С (например, 6600). Спасибо за тест. Хотя, конечно, это еще не полноценный взлом — относительная погрешность слишком мала.
Написал решение в личное сообщение для экспериментов)
Да, я забыл, что в условии сказано "абсолютная или относительная погрешность".
Судя по результатам некоторого матанализа, сделать тест, заваливающий твое решение с 5000 направлениями и при этом дающий относительную погрешность больше 5 * 10 - 8, невозможно. Так что быть твоему решению вечно со статусом AC :).
Спасибо) На самом деле, идея действительно классная. Думаю, именно из-за этого, по словам ведущего церемонии закрытия чемпионата, для команды СПб АУ "под столом завалялся диплом 3 степени" :)
I wonder how to solve problem G. I try to solve it with Segment Tree. It is not a simple Segment Tree because I will not try to build the whole tree at first, as you know, n is too large and Memory Limit is 65536KB(too small) Actually (m * logn) nodes will be visited, so I will just arrange space to the node when it is the first time to visit the node. But I still got a Memory Limit Exceed.