Сегодня мы открываем регистрацию на чемпионат по спортивному программированию Яндекс.Алгоритм-2015. В этом году чемпионат пройдёт полностью в онлайне, на платформе Яндекс.Контест. Участником может стать каждый, кто умеет решать алгоритмические задачи и воплощать решения на одном из 13 языков программирования.
Яндекс.Алгоритм состоит из нескольких отборочных раундов, в каждом из которых нужно решить пять задач за 100 минут. В финал, который состоится 6 августа, выйдут 25 лучших по результатам отбора. Призёров ждут денежные призы: 300 тысяч рублей за первое место, 150 — за второе и 90 — за третье. Кроме того, 512 сильнейших участников Алгоритма получат футболки от Яндекса.
В отборочный этап будет приглашен каждый, кто решит хотя бы одну задачу в тренировочном или квалификационном раунде, которые пройдут 3 и 17 мая.
UPD Тренировочный раунд уже сегодня!
UPD Приглашаем принять участие в квалификационном раунде — он пройдет в формате виртуального контеста, начать который можно до полуночи с 17 на 18 мая. Финалистам ACM ICPC привет =)
UPD Не пропустите первый раунд отборочного этапа Яндекс.Алгоритма, который пройдет сегодня, 24 мая 2015, в 21:00 (UTC+3). Раунд продлится 100 минут по правилам TCM/Time.
Экспорта в календарь не хватает
Финальный раунд длиною в минус год — необычно.
Нужно будет накодить машину времени?
Вернулась в прошлое и поправила =)
Мне кажется, тут тоже косяк:
Раунд заканчивается одновременно с началом.
Всего лишь взломать систему Яндекс.Контест, зайти через админа и поменять дату.
Sorry, form unavailable Need auth.
What's wrong?
You need to be logged into Yandex to register. Use social auth for easy registration
I think I have logged into Yandex. And the message above is what I got.
What social auth do I need?(I am confused about this). Thanks for helping me.
maybe you're logged into yandex.com and trying to access yandex.ru, or vice versa.
You can log in using your facebook, google or twitter accounts, check https://mail.yandex.com/
Fixed. Thanks anyway.
Готовы ли вы встать в 5 утра ради футболки?
готовы ли вы не ложиться до
5 утра6 40 ради футболки?Готовы ли вы выступить на двух других отборочных раундах достаточно хорошо, чтобы не было необходимости вставать в 5 утра ради футболки?
Спросил Боря, писавший первый gcj раунд в 4 утра и занявший без каких-либо вопросов 15 место
Я просто пытаюсь уменьшить конкуренцию на раунде в 5 утра, только тссс...
не совсем понимаю, как определятся эти 512 сильнейших, может кто-то объяснить или дать ссылку на почитать?
дак это в правилах вроде написано
сначала баллы(гран-при 30), потом задачи, потом время
спасибо, даже не знаю, как я не заметил))
кто еще не видел, вот описание:
Результат отборочного этапа включает три значения: сумму зачетных очков, количество решенных задач и суммарное штрафное время за три раунда.
Участник располагается выше в итоговой таблице отборочного этапа, если имеет:
больше зачетных очков;
больше решенных задач при равенстве зачетных очков;
меньше штрафного времени при равенстве зачетных очков и одинаковом количестве решенных задач.
Странно, что эту фразу никто до сих пор не прокомментировал :).
К слову, вот тут Egor откликнулся уже через 6 минут после опубликования поста.
Потому что это уже стало мейнстримом
Ну там чуть другая ситуация была, людям пообещали онсайт, а потом его отменили.
Анонсировать отсутствие онсайта перед началом отборочных раундов несколько честнее чем после их окончания.
Я делаю акцент в первую очередь на значительном снижении финансирования СП двумя его крупными спонсорами в России. А так, я с Вами полностью согласен.
С другой стороны, в этом сезоне Яндекс организовал такую вещь, как спонсорский зачет OpenCup. ИМХО весьма заметное вложение в финансирование СП. И общий призовой фонд там в несколько раз выше, чем в том же Яндекс.Алгоритм 2015.
Хотя от этого факт отсутствия онсайта не становится менее неприятным.
Если честно, когда я увидел объявление об этом спонсорском зачете, у меня возник лютый фейспалм.
Цитирую свои тогдашние мысли: "Яндекс собирается оплатить поездку на сборы таким монстрам, которым ее с вероятностью 99% и так оплатит их собственный вуз".
А вообще, если задуматься о выражении "аффилированные стороны" в контексте обсуждаемой нами темы, то могут возникнуть весьма интересные гипотезы :).
P.S. Углубляться дальше в эту деликатную тему я не намерен.
Мы в 1%, значит. Нам никто не оплатил бы Петрозаводск, а сейчас мы бы искали спонсоров для поездки на финал — точно так же, как некоторые финалисты от SEERC в прошлом году. Хотя да, к финансированию СП в России это вроде не относится.
Да, я догадываюсь, что в России с этим дела обстоят немного иначе.
P.S. В прошлом году поездку на онсайт оплачивал Яндекс, или она была за счет участников?
Если честно, я именно насчет вас допускал, что у вас могут быть проблемы.
Оплачивал Яндекс.
Можно попробывать.
че за чуваки у тебя на аватарке?
Братья Пилоты в черном, очевидно же
Will you send reminders before every round?
Обновите Mono, пожалуйста. Используемой сейчас версии 5 лет уже =/
Пытался вспомнить какой у меня там аккаунт на Яндексе
@
Случайно взломал аккаунт какого-то Никиты Рипатти из Перми...
...тем временем в Яндексе:
-- Так, уволить безопасников! И нанять Рипатти. Только не перепутайте, правильного Рипатти!
Where will be the final round take place?
Russian post version says that the championship will be fully online :(
В правилах написано "К участию не допускаются организаторы конкурса, сотрудники Яндекса или аффилированных компаний, а также их близкие родственники"
А в положении о конкурсе написано "6.7. Сотрудники Организатора и аффилированных с ним компаний, иные задействованные в организации Конкурса лица, а также члены их семей могут стать Участниками, но не могут претендовать на выход в финал Конкурса и получение призов."
Чему верить?
Второму, вероятно, т.к. всегда можно с фейкового акка сыграть и никто никогда об этом не узнает.
А почему я на главной странице вижу большую кнопку "Зарегистрироваться", хотя я уже зарегистрирован? И вообще, факт того, что я зарегистрирован, на сайте никак не показывается.
И на какой странице ждать задач? И таймер обратного отсчета было бы неплохо ввести.
Получилось найти задачи?
Пока нет. Ждем информации.
"У вас нет прав просматривать это соревнование"
думал, что косяк с регистрацией, а она висит :(
edit: о, теперь "Соревнование завершено. Отправка решений запрещена"
Контест есть, прав нет; регистрация висит
Появились. https://contest.yandex.ru/algorithm2015/contest/1237/enter/ Но "У вас нет прав просматривать это соревнование"
А, вот, надо же, ссылка на контест появилась. В 22:01, правда.
Контест начался — "у вас нет прав просматривать это соревнование" :(
"У вас нет прав просматривать это соревнование"
Это нормально?
Соревнование завершено. Отправка решений запрещена
Уже лучше :)
Соревнование еще не началось До старта осталось 00:05:39
Ещё лучше!
Why am not I allowed to enter warmup round?
Оказалось, проблема с запретом на просмотр не только у меня.
Кнопка, по которой смотреть задачки, появилась с опозданием в пару секунд. И она не работает!!! Пишет, что у меня нет прав на просмотр данного соревнования.
UPD: Стало лучше: "Соревнование завершено. Отправка решений запрещена". Теперь хоть можно с чистой совестью идти спать, а не искать способ хотя бы прочитать задачи.
We will start the round at 22:10, thank you for your patience
I hope you guys are not managing the contest from the Yandex Moscow office at Sunday, 22:00 :)
It's still unavailable for me
The absence of the exact date seems now suspicious to me :(
Lie
Лида, что делать?
Всё, контекст закончился.. кто не успел, тот опоздал))
Как быстро закончился!
"The contest is over. Submissions are not allowed"
Да, за 5 минут обернулись...
Ух ты, два раза закончился!! :)
А соревнование тем временем завершено))
Мне кажется или самая сложная задача контеста, это добраться до задач?
Не беспокойся — найдётся всё.
Со временем.
My friend says he can see the problems but all I get is "The contest is over. Submissions are not allowed". Sounds quite unfair?
He's lying and shouldn't be your friend anymore.
Well he sent me a problem statement, so I guess he just created a problem for the lie! :D
Why would he lie to you wihout a preparation? Don't be naive. :)
Same here
Я вижу это "Соревнование завершено. Отправка решений запрещена".
По-прежнему "Соревнование завершено. Отправка решений запрещена" хотя уже 22:13
Можно сделать разминочный раунд виртуальным 24-часовым — и все будут счастливы и не будут до ночи решать задачи :)
Всё же перед массивным онлайном неплохо провести нагрузочное тестирование системы.
Позор для Яндекса :)
Да ладно, для этого ведь и тренировочный
Отправил запрос через "Обратная связь" — пока тишина. Кому-нибудь поддержка ответила?
Появился обратный отсчет, ура! Искренне надеюсь на то, что больше никаких проблем не будет.
Кажется уже починили.
The countdown timer is shown now.
Now it says the contest will start in 3 minutes, but my friend sent me a picture of the statement already... Gonna be a fair competition I see!
https://www.youtube.com/watch?v=96UQEVK05kM
I saw problem A and started coding it but now it says the contest has not started yet. =.=
Hey, that's unfair! We need some men in black to fix that for ya.
Ваше решение отправить не удалось. UPD: У вас нет прав просматривать это соревнование.
У вас нет прав просматривать это соревнование
Снова "У вас нет прав просматривать это соревнование"
Just when you thought it's all going well — "You are not allowed to view this contest".
I'm getting Bayan flashbacks here :\
Можно по обсуждать первую задачу пока не исправят сервер :)
Не проще ли её решить?
Не стоит... =)
так не интересно :(
Даже условие загрузить не успел :(
А я успел и решить, но отправить не успел(
В Yandex код вообще тестируют, или сразу в production?
А чем по-вашему мы сейчас с вами занимаемся?)
https://www.youtube.com/watch?v=96UQEVK05kM
3 май 2015, 22:32:36
Соревнование завершено. Отправка решений запрещена
What can I do sometimes ?!!!!!
А систему отправки задач не предусмотрели? :)
Ваше решение отправить не удалось
А потом все получат штраф за кучу посылок
"Ваше решение отправить не удалось"
?????
"Ваше решение отправить не удалось"... Вроде же Яндекс контест работал хорошо раньше. Как его так сломать то умудрились? :)
Whenever I try to submit a solution, it tells me:
"Your solution was not submitted."
Help?
I can't submit my c++ solution for A. Any clue? :D
Problem B is identical to a problem from Canadian OI, with minor changes to the statement and identical input format/sample data:
http://wcipeg.com/problem/ccc03s2p3
I think all problems used for this round are not new. I don't see any troubles with giving old problems to the warm-up round.
In the rules it says
Official Rules
Problems in the warm-up (testing) rounds were used on different contests like OpenCup or local contests. Problem about cube was used on some ancient SnarkNews Series; but in there it was taken not from Canadian OI, but from some other source (dont remember precisely, which one though).
Original problems must be for all official rounds (Qualification, three Online rounds and Online Final). Testing round(s) use selections — main goal of it is to test if the system is working ok and to remind TCM/Time rules to players, and for this goal selection from different sources works okay.
I met problem with same idea several times in different old contests, so it was added as "classical problem"; i am surprised that number of players solving them is not that big.
May be, first time it appeared in Canadian OI (atleast format points at it). Btw, tests were changed abit to catch some special cases.
See also the following problems:
https://contest.yandex.ru/contest/424/problems/F/
http://wcipeg.com/problem/ccc13s2p6
What is the solution for this problem?
link
Верните кнопку отправить вслепую :)
постараемся вернуть её к 17 мая, она нам тоже очень нравится
Huge thanks for everyone who stayed with us until the normal flow of the round. We'll make sure that Qualification round on May 17 will run smoothly.
А на что ты готов ради футболки ?! :)
Разбор будет?
Как решать задачу С и D?
Отражаете одну из точек относительно y=0 и выводите квадрат длины отрезка между точками.
Ты забыл добавить, что выводите ответ. Потом еще выводите точку и 20-ть нулей. Досих пор бомбит от такого
Неужели не очевидно, что сумма квадратов модулей разности целых чисел будет целым числом, но формат вывода никто не отменял?
Про сумму квадратов конечно очевидно. Но формат вывода, эмс, обычно задача читается быстро, и форматы просматриваются мельком. в данном случае, выведите с точностью 20 знаков олололо. Не особо это прикольно вообщем.
А не подскажете, с чего вдруг http://pastebin.com/srsWzmQb не прошло какой-то тест?
Не влезало в int, вероятно.
Если y1 и y2 с разных сторон от y=0, инвертировать y2 не нужно. y2-y1 вместо '+'
Эта ситуация невозможна по ограничениям из условия.
Почему? Координаты могут быть как положительные, так и отрицательные )
А, нет, извините ) y неотрицательные ) Я по невнимательности решала другую задачу )
Можно код посмотреть?
код
Переставить и, при надобности, отразить от оси Ox точки так, чтобы они были по разные стороны от Ox, тогда это просто расстояние между двумя точками, которое без корня вычисляется.
Ординаты точек положительны, отражать нужно всегда.
Отразить точку B относительно оси абсцисс и найти квадрат расстояния между точками.
D: сортируем массив и считаем гистограмму количества каждого числа. Минимальный ответ = размер гистограммы — 1. (количество различных чисел — 1)
Для максимального ответа мне было лень думать и я просто промоделировал выставление разных соседних чисел из гистограммы, а потом уже посчитал получившийся ответ. Держим два указателя: текущий элемент гистограммы и следующий, когда следующий обнуляется — двигаем, когда текущий обнуляется — приравниваем его к следующему.
Обозначим точку, первую точку через A, а вторую точку через B. Отразим точку B симметрично относительно прямой y = 0 и получим точку B′. Тогда из любого пути AKB (K – это некоторая точка на прямой y = 0) можно, отразив симметрично относительно абциссы его участок BK, получить равный ему по длине путь AKB'(т.к KB' = KB), длина которого по неравенству треугольника не меньше AB'. Значит ответ это квадрат расстояние между A и B'.
How to solve C ?!
If points are on the different sides to axis x result is euclidean distance between them. Else change y of first point to -y.
It is stated, that both points are on the top side the river, so you don't have to check whether cities are on different sides of the river.
А как решать А? Столько жадностей перепробовал :)
Коннектить две вершины с наименьшей степенью.
...но я же так и делал :(
в чем подвох? edit: вот код http://pastebin.com/yL4K6jep
Вы добавляете одно ребро больше 1 раза.
/facepalm, спасибо
ВА 21
Попробуйте тест: 9 18 4
ну падает. а как можно по-другому написать "выбираем две вершины с мин степенью и их соединяем"?
vector<pt> ans; while(m--) { int mn1 = INF, i1 = -1, mn2 = INF, i2 = -1; forn1(i, n) { if(deg[i] < mn1) { mn1 = deg[i]; i1 = i; } } forn1(i, n) { if(deg[i] < mn2 && i != i1 && !g[i1][i] && !g[i][i1]) { mn2 = deg[i]; i2 = i; } } cerr << "vertex == " << i1 << ' ' << i2 << endl; cerr << "degs == " << deg[i1] << ' ' << deg[i2] << endl; deg[i1]++; deg[i2]++; g[i1][i2] = g[i2][i1] = true; ans.pb(mp(i1, i2)); }Видать, я не прав, и такая штука не заходит, только не могу понять, что не так.
А сам я отправил то же, что и Fcdkbear ниже написал.
Зашло такое: перебираем чувака у которого степень меньше К, коннектим к нему остальных в порядке возрастания количеста друзей у них пока степень нашего чувака не станет равна к (степень == количесто друзей). В конце если нужно добиваем количество связей до М еще неиспользованными связями
Такое зашло, спасибо. Осталось доказать :) Или это уже где-то было?
А что тут доказывать?
Все вершины поставим по кругу. Если k — четное, то для каждой вершины ее соединяем с
левыми соседями и 
правыми соседями. Если k — нечетное,то каждую вершину соединяем с 
левыми соседями и 
правыми соседями, а также соединяем все вершины v, u такие что 
. Если у нас количество ребер меньше чем M, то просто добавляем ребро между не соединенными вершинами.
How to change the country flag that is shown to the right of my name in the standings?
Кто же получили футболки?
"20 футболок случайно выбранным участникам этого раунда, сделавшим хотя бы одну посылку"
Всего 20 футболок. 637 участников. Вероятность её получить 3%. =)
Было бы справедливее "решившим хотя бы одну задачу", тогда количество сократится в два раза :)
щас договоришься, ТОП-20 ток дадут.
Как B решать?
Лень регистрировать на яндекс контест, чтобы проверить идею (Может, найдется не ленивый и добавит в Тренировки?), но, кажется, такое должно пройти: проверяем все детали куба на возможность сдвинуть на одну клетку в любом направлении. Если получилось хоть с одной(хотя бы с одним направлением) — непрочный, иначе — прочный.
Прикладываем силу во все 6 сторон к каждому кубику и смотрим, какое количество кубиков при этом сдвинулось. Если оно меньше, чем общее количество кубиков, то куб непрочный, если равно, то прочный.
Достаточно в 3 стороны по очевидным причинам
Как вы решали Е про коней? Почему там бфс валится?
Правильно написанный не валится :)
Бфс — это правильное решение. Вот, например, мой код.
Я имел в виду запустить для первого коня, потом для второго. И среди всех (i, j) | d1[i][j] == d2[i][j], выбрать нужную.
поле 5 на 5. в левой верхней клетке стоит (2, 2)- конь, в правой нижней — (1, 1)
им выгодно встретиться в правой нижней клетке, каждый сделает по 2 хода, но для 2 коня это не является кратчайшим путем дойти до той клетки.
А кто получил футболки так и не отписали
Могу предположить, что получившим футболки они все же написали.
Раз уж мы тут предполагаем, то предположу что обладателей футболочек обьявят в том же письме, где скажут о том, квалифицировался участник или нет
Михаил прав, осталось лишь немного подождать. Мы постараемся не сильно заваливать вас письмами =)
Внезапно только сегодня вспомнил, что тренировочный раунд где-то тут должен быть. Могли бы и прислать напоминание, хотя, может, оно и к лучшему.
Напоминание было (во всяком случае у меня) еще 30 апреля.
А, да, действительно. Успелось уже и забыться.
I can't wait more for the editorial. Can anyone give the accepted code for problem A? Thanks.
You can use Havel–Hakimi algorithm to solve the problem.
Because there is at least one solution. You can first build a degree sequence with all degrees equal to k. The divide the rest degrees to each element of the degree sequence evenly.
My code for reference: http://paste.ubuntu.com/10994941
Is it possible to solve this problem ignoring K? I mean, create a sequence of edges based only on N, and then take the first M edges of it. (Yes, the sequence must ignore M too :)
For a challenge I have been trying to solve A this way, but failed. I still do not know the answer.
Well, I ignored K, but had not ignored M though
Sooo, who are the t-shirt winners ?!
Каждый раз, когда жюри не пишет авторские решения на джаве, в мире грустит один котик.
I couldn't understand open/blind submission. What is difference ?! What are advantages of open/blind. Does blind mean : "I don't need feedback" or sth else ?!
When you use blind way, you dont have feedback but you have additional bonus instead of penalty time. I.e. you choose harder way and are awarded for it with the decreasing of total penalty.
hmm got it... So if my solution gets OK in open submission does it mean I have solved that problem I mean it checks all tests ?!
Yes.. It means ur solution passed all the test-cases
To be precise, it's not instead of a penalty, it's in addition to penalty (so you have both penalty and bonus)
Where can I solve previous Yandex contests?
(of last year and last to last year)
EDIT-1 : Found 2014 in GYM
Here: https://contest.yandex.ru/algorithm2014/schedule/
And here: https://contest.yandex.ru/algorithm2013/schedule/
Thanks
Is there public standings page?
Not until the end of the contest. It will be unfair if contestants who haven't started yet could see someone's final results.
It still would be cool to see the standings for those who are not registered.
Вот в правилах сказано:
То есть получается, чем в большем количестве раундов ты участвовал, тем лучше? Как-то это странно. Или можно участвовать в одном раунде? Не все же могут поучаствовать в утреннем раунде.
Можно ли кеш поменьше сделать для таблички результатов?
После сдачи задачи нужно ждать 1-2 минуты, чтобы он обновился.
Huh, memory limit is 64Mb ; o? Kinda completely missed that, I haven't seen such small memory limit as a standard limit for some time and it costed me one problem ; d.
Same for me.
I'll read statements more carefully. I'll read statements more carefully. I'll read statements more carefully...
Like this ?!
UPD I understood why minus. I think you you thought it doesn't calculate if your memory exceeds 64MB, but before this submission memory was around 135MB.
My first submission stayed with the "waiting" status for about half an hour and I had a stupid bug that I had to wait half an hour to correct. I hope this doesn't happen in the Elimination rounds.
А про футболки с тренировочного так в письме и не сказали(кто получил и т.п.)
Top 512 participants according to the cumulative result of all three elimination stage rounds will receive a contest T-shirt. what does it mean "cumulative result",there is 3 round,and in each only top 30 user can earn points,3*30=90 and how 512? pls some1 explain me
А где можно поменять имя, отображаемое в таблице результатов?
Здесь
Это не помогает. Кроме того, у меня в таблице не рисуется флажок, хотя в профиле страна указана.
What is the solution for Problem B — Optimal Playlist ?
Binary search, then condense strongly connected components and topologically sort them. Components will form a chain iff the required path exists.
What about finding Minimum Cost Spanning Tree in DAG? Would this approach work?
No: for example, in graph (1->2,1->3) there is an oriented tree, but no path visits all nodes.
Ah, missed qualification again.
Can someone give some hints for problem C? Thanks.
My approach was following. Let's store in f[d][j] j-th parameter of d-th document, in s[d] relevance for d-th document and in some structure r — sorted relevances with numbers of corresponding documents (it was set<pair<long long, int> > in my code). Then for each query it's easy to update. For 2 K it was just top K elements of set. For 1 d j v:
I used order statistics tree. I guess using STL set container would have sufficed too.
А была уже какая-то информация о футболчках? А то я, как оказалось, при регистрации ввел не тот email.
How to solve E problem ?!
We need to find the number of pairs (A, B) such that A divides N, B divides M and L <= AB <= R. First generate all divisors of N and M. Then iterate over A (divisor of N). Corresponding B must be in the interval [L/A, R/A]. The number of divisors of M from this interval can be found by binary search.
You may even iterate through all divisors of N and M and just check if L<=A*B<=R.
Yes, it seems that the worst case is the number 223092870=2×3×5×7×11×13×17×19×23, which has only 2^9 divisors, so it's 2^18 pairs at most.
i think the worst case is 931170240. this number have 1344 divisors.
I am pretty sure, that your estimation is not correct (for example, you may use 2*2*2*2*2 instead of 2*23), but you may assume that the number of divisors for such small numbers is O(N1 / 3), and the total complexity of our algorithm will be O(N2 / 3)
I'm still unable to understand what Problem B was. Can someone please explain the output of the sample case or any other case?
You should find a path in the given graph with minimum possible max edge weight.
Как поменять флаг рядом с ником в таблице результатов?
А таблица будет видна тем, кто не участвует?
Да.
https://contest.yandex.ru/contest/1239/standings/
Couldn't understand the purpose of problem X — Fake testing problem.
People were asking for some way to be able to test code on the server in case of compiler configuration problems. I think this solution proposed.
You can build your source file on Testing server and run it. e.g. you can debug TL for your solution.
it's as codeforces's custom test
How to solve problem B (Elimination round 1)?
My solution — in cycle pick every city as a center.
Central city can be allocated to either top or bottom cities group depending on where you need it by shifting line some infinitesimal amount up or down. We can do it because no three cities lie on the same line.
After you picked central city you can use magic atan2 function and simulate rotating line through your central city and calculate how many people live above or below it. You can do it by sorting two lists by atan2 value (or one list) and going through it with two pointers. Pick minimum, but remember that you can always allocate central city the way it's better for you (my code was like abs(abs(x) — central)).
I bet there are easier solutions but this one got ACed and I am happy with that.
For me it was tough round, much tougher then Round 1 in GCJ this year. I solved just one problem and spend 1 hour solving Saw or Not To Saw — I think I was very close, but couldn't get through WA3 :(
Moved to: Proper thread for discussion
You can use orientation in integers, but use atan2 in doubles?
With coordinates limited by 1,000, double precision should be more then enough for all angles. Though I already see that it was bad solution — over complicated. Costed me 15-20 minutes of my time.
coordinates were limited by 2⋅104
and with good tests no solution with bad-written doubles should pass imho
If so, I defy you to show us test where atan2 is not sufficiently precise (on long doubles, why not?)
of course it's difficult to construct such test. And in this problem I think atan2 is sufficiently precise
so maybe using orientation everywhere is paranoia, but a good one ;)
This is overcomplicated? I think that your solution is the simplest possible one. What can be even more simplified?
I used more complicated approach where I maintained array of prefix sums of possible divisions when sweeping points with line of a fixed inclination and updated it appropriately when rotating this line.
I liked idea of taking pairs of dots and drawing lines between them. I think if this idea struck my mind I would finish this question in 15 minutes, not 35. But I often experience that — coding more complicated solution.
But thank you for admitting that red coders sometimes do complicated things too. :)
What do you mean by that idea?
Found it in this thread above. I just realized that it is O(n^3), to test all pairs of cities and calculate population on each side. So maybe not good idea. Ok, my solution is not over complicated :)
It isn't real solution, but here's some magic!
http://ideone.com/YeLtmM
Rotate point around origin by
, and try all possible y axis, as a "divide line". Do it K times.
Did it pass all tests? I tried with this idea, but failed on test #12 :((
Update: Accepted. There was a bug in my solution. :sosad:
I wrote a similar fake solution. I tried MAGIC = 20,000 random dividing lines :)
http://ideone.com/MTRn2I
How to solve Problem F — To Saw or Not to Saw?
I got 2 formulae by using similarity of triangles:
Got WA on testcase 3.
ans = gcd(a, c) * min(b / a, d / c)
It may sound really stupid.. but how can one get to this formula?
Let me rewrite it a bit:
ans = gcd(2a, 2c) / 2 * min(b / a, d / c)
The first part d = gcd(2a, 2c) comes from the following observation. Let's assign integer numbers to each peak of the saws and let's put two saws so that 0-th peak of the first saw will be exactly above the 0-th peak of the second saw and denote this coordinate as X = 0. If you plot the rest of the peaks then peaks of the first saw will have coordinates xi = 2a * i for each integer i, similarly peaks of the second saw will have coordinates yi = 2c * i. Then you plot all those peaks as points on X-axis and the question is what is the smallest distance of first saw peaks and second saw peaks. In other words what is the min(dist(xi, yi)) = min(abs(2a * i - 2c * j)) for any integer i and j. If you solved enough number theory problems it will be clear to you that this is equal to d = gcd(2a, 2c) = 2·gcd(a, c).
Now you have this d number. If you plot peaks again you should see that the optimal solution would be to move one of the saws d / 2 units left or right and then move them towards each other as much as possible. How much you will be able to move it depends on the "sharpness" of the saw's teeth (i.e, b/a ratio). Then if you know d already the result is simply l = d / 2 * b / a. Then you replace b / a with min(b / a, d / c) because you need to consider the case when first saw has "sharper" teeth.
Thank you :).
It's crystal clear now..
Thanks for your time
well and if a = c ? I put min(b,d) but it's WA on 4th
D решил, B не решил. Нормально.
Just my luck. Picked the weird looking problem earlier on only to realize there was an easier one waiting. Started solving and couldn't submit by 5 seconds. Submit in upsolving mode and get Accepted.
Как решали задачу B?
Задача с очень боянистой (но не очень приятной для кодинга) идеей
Искомая прямая "почти" проходит через две любые точки (то есть она как бы проходит, но сдвинута на epsilon).
Решение за O(N3). Перебираем две точки, образующие прямую, для всех остальных смотрим с какой они стороны. Наши две точки пробуем кидать 4-мя способами в одну из двух сторон. Вероятно, это ТЛ, но помагает понять АС идею.
Решение за O(N2logN). Перебираем первую точку, остальные сортируем по углу относительно нее. Далее интересующие нас суммы можно пересчитывать двумя указателями.
Я с шестой попытки сдал O(N3)
http://mirror.codeforces.com/blog/entry/17456#comment-223092
Топ 3 сдали задачу в последние две минуты. Хорошо, что я рефрешил таблицу без чая во рту.
Ну я дописал минут за 8 до конца, и тестировал до последней минуты. Сорри :)
У eatmore особо циничное штрафное время, конечно.
Can someone start a new thread with editorial to the problems of Elimination Round 1.
I think I can learn a lot from the editorials of this round. Problems were a lil tough for a beginner like me.
It's already there apparently: http://mirror.codeforces.com/blog/entry/18078
Thanks :)
PS : The thead started just after I posted that comment :)
B — избитый баян. Сколько она мне попадалась, столько я и сидел весь контест дебажил. В итоге не сдал.
same here.
Зачем она нужна в контесте? То есть я не спорю, что я сам рак и прямую покрутить за час сорок не смог. Но задача же просто делит участников на две группы: уже крутили и сидят учатся крутить.
P.S. Поделитесь реализацией хорошей, пожалуйста.
http://pastebin.com/pdKnmANh
Ну, я не крутил, затолкал O(N3logN) с отсечкой по времени.
Классно, что тут скажешь.
Подарите мне кто-то ровные руки. У меня асимптотически верное решение 1.6 секунды работает.
Кстати если кто-то скажет, почему так медленно — буду благодарен. Код
Может быть atan2 нужно посчитать заранее, а не внутри компаратора.
Да, спасибо, это ускорило решение до 165 мс (в 10 раз на этих тестах, ничего себе).
Отличная реализация. Мне впадлу было крутить, я перебирал (пока TL позволяет) направление прямой и двигал её за O(n).
Enjoy
Это конечно не крутилка, но все равно.
http://mirror.codeforces.com/blog/entry/18080?#comment-229640
Тупо куб с branch-prediction хаком.
cpp — 0.79 sec java — 1.3 sec
Очень неприятно когда задача, которую видишь в первый раз, для всех остальных избитый баян.
Ну вот для меня она стала бояном с GCJ этого кода. Пока правда похоже не избитым, потому что решение упало.
Приношу извинения за эту задачу, действительно, не первой свежести идея. Пришлось в последний момент заменять задачу, нашлась вот эта.
По-моему, лучше было вовсе 5 задач оставить.
Там ещё куб с отсечением по ответу легко проходит (у меня куча посылок, но это WA).
А почему нельзя было в контесте хотя бы одну утешительную задачу сделать? Все-таки первый раунд, не финал :)
По задумке утешительной была задача F. Неловко получилось.
а как ее решать?)
Сейчас, скоро напишу краткий разбор.
Утешил. Спасибо.
Задачей B все утешились :(
My code (for Elimination Round 1 problem E) gets TLE in test 9 with 2.093s. How can I improve it? What's the problem?
Thank you in advance!
Here is how I did it. Hope it helps.
I am currently too sleepy to read your code so I can't really say why yours failed. Sorry.
Thanks, it helped. I forgot to compress queries in which k=1.
Кстати, теперь все раунды должны быть такой же сложности, иначе в борьбе за футболочку возникнет несправедливость
Почему? Раунды же суммируются. Разве что несправедливость в зависимости от таймзоны.
Ну да, я это имел в виду. Те, кто пропустят более легкий раунд, окажутся в выигрыше по сравнению с теми, кто пропустят более тяжелый
Скорее наоборот, на более лёгком раунде можно решить больше задач, поэтому тот, кто его пропустит, окажется в проигрышном положении.
Да, точно. В очередной раз убеждаюсь, что мне нельзя писать комменты после часа ночи :)
Таким ходом организаторы убьют сразу двух зайцев: 1) обеспечится турнирная справедливость 2) уменьшатся расходы на футболки ;)
My opinion is that problemset was very nice! C, D and F were very interesting in my opinion! B and E were also OK. Unfortunately A was tedious, any deeper thought, just a lot of cases to consider.
You can write A with almost no special cases
How? My solution has about 10 ifs.
I do not measure number of cases in number of ifs, rather in number of different constructions. My solution
OK, that sounded like a challenge, so I went for it and managed to get this accepted by this code: http://ideone.com/kFdFxb It doesn't contain that many ifs (only 5), but it is still tedious >_>... I think that analysis of those cases is nonomittable (case when cur_wid == l[hor] is especially nasty xd) and if you have more elegant solution I would like to see it.
During contest I didn't give that task a deeper thought, because I haven't even read it, because in half of the contest I have to made a choice which problem to do next — A, C or D. A had least amount of ACs within top people (but now I see that it had much more ACs that time :d) and had longest description, so I disregarded A and choose D since I quickly got and idea how to do this. After contest I thought that it's all about cases, so I didn't think about this much :P.
Are you implying that you haven't seen about 10 problems which are basically equivalent to B? Those half-plane things appear over and over and over again.
Uh, OK, indeed it is not very innovative problem, but at least there was not anything which will cause me to complain about something, for example no restoring result, no collinear points etc.
For problem C,I find the fomula: dp[n][k]=dp[n-1][k-1]*(n-k+1)+dp[n-1][k]*k (1<k<n) using bruteforce.But what's the logistic in it?
(I guess that you meant problem C). Don't tell me that it's true :o!? That looks very mysterious for me. I got AC (after contest) using much more complicated DP with n^3 states, some binomials and stupid trick allowing me to fit in O(n^2) space ;__;.
UPD: Yeah, it looks that it's true, however I don't have time now to wonder why is that. Here's my code: http://ideone.com/GdOSTe but compared to your solution I guess it can be mainly used to make fun of me :P.
Can you explain more about your idea?I really can't understand it.
I consider similar type of game. When we delete only the smallest card, not smallest or largest. Observe that game when there are n cards and we want to end up with k-th card is a sum of two independent games of that type (one with cards 1..k, one with cards k..n) when we delete last card in turns of the same number — this is key observation to whole solution (one of them (k..n) is reversed, that means that we delete the largest card instead of the smallest one).
Given that I compute dp[a][b][c] which tells how many of such games are that we are given a cards, largest card is on b-th position and we delete it c-th moment we see it. pref[a][b][c] = sum dp[a][1..b][c]
Fitting in O(n^2) space is little tricky. Given formulas for dp I can compute dp for dp[a][..][..] given only dp[a-1][..][..], I do not need previous values of a, but when counting answer I have to combine games of sizes k and n-k+1, so I either need to separately count this for dp[k] and run everything once again for dp[n-k+1] or observe that analogous property holds for number of checks and when combining games I always combine two games with the same number of checks (I used second approach).
I think the c-th moment factor is also the hard and key point to solve the problem.And it really needs observation.
This formula is also number of permutations with k-1 rises (position such that a_i < a_i+1). It's easy to see why it's correct but I still haven't found connection between that and C problem. Maybe there is a bijection?
Here is the explanation
And by the way, why is that formula correct for calculation the number of permutations with k-1 rises? UPD Got it, nevermind
Как решать D?
Понятно, можно считать l = 0.
Будем набирать x начиная с младших битов (они идут справа налево). Рассмотрим немного неправильное решение: динамика dp[сколько разрядов прошли][верно ли, что готовый суффикс числа x ≤ суффикса r][есть ли перенос при сложении k + n]. Проблема такой динамики, что она считает количество подходящих k, а не x.
Тогда сделаем так: dp[i][gr][маска переносов (1, 2 или 3)] -- сколько таких x, что их можно получить на таком суффиксе, при этом они будут больше/не больше соответствующего суффикса r и все переносы, которые вообще возможны при получении такого x записаны в маске. Тогда все x разбились на не пересекающиеся классы.
Переход -- перебрать следующий разряд x, внутри перебрать возможные остатки, посчитать новые возможные остатки.
Код
Я решил так. Перепишем уравнение в виде (k XOR x) — k = n. Пусть x = 2a1 + 2a2 + ... + 2am — двоичное разложение. Тогда возможные значения левой части — это ±2a1±2a2±...±2am. (Остальные биты от ксора с иксом не меняются, а эти m меняются либо с 0 на 1, либо с 1 на 0.) Если обозначим через a сумму членов с плюсом, а через b — с минусом, то условие перепишется так: a-b=n, a+b=x, a&b=0. Или, избавляясь от переменной a, b&(n+b)=0, x=n+2b. Последнее условие нам дает ограничение на b (x<=r <=> b <= (r-n)/2). То есть нам нужно найти f(n, b) = количество b<=r таких, что b&(n+b)=0.
Будем строить b начиная с младшего бита. Если n=2n' четно, то и b должно быть четно (=2b'), и при этом n'&(n'+b') = 0, то есть получаем f(n, r) = f(n', r') = f(n/2, r/2). Если же n нечетно, то младший бит в b может быть как 0, так и 1. Аналогично разбирая эти 2 случая, получаем f(n, r) = f(n/2, r/2) + f(n/2 + 1, (r-1)/2). (Деления целочисленные; +1 во втором слагаемом из-за переноса разряда.)
Тут можно заметить, что 2 рекурсивных вызова в последнем равенстве очень похожи (весьма вероятно, что на следующих уровнях рекурсии они будут вызывать f с одинаковыми параметрами). Кроме того, если n оканчивается на много единиц (плохой случай — много ветвлений), то n/2+1 заканчивается на много нулей (хороший случай — нет ветвлений). В общем, у меня зашла рекурсия с мемоизацией всего за 2 миллисекунды: http://pastebin.com/C1vBnHFs
this was hard