Всем привет!
2 мая в 11-00 МСК в системе Яндекс.Контест для команд-участников Открытого Кубка состоится "зеркало" XX Чемпионата Урала. Контест не является этапом опенкапа, зато победитель получит куда больше, чем какие-то рейтинговые очки — кубок интернет-чемпиона Урала :) Среди авторов контеста — winger, Kurpilyansky, Stigius, Erop, AlexFetisov и куча других Уральских (и не только) ветеранов. Спасибо GlebsHP, TeaPot и SirShokoladina за ценные советы и прорешивание комплекта, а также MikeMirzayanov за систему Polygon, которая позволила подготовить комплект большой распределенной по всему свету команде :)
Авторы контеста не только тормоза и пишут анонс только сейчас, но считают, что подготовили интересный комплект.
Лайк, шэр, репост, все дела :)
UPD
Ссылка на вход: https://official.contest.yandex.ru/contest/2486/enter/
UPD2
BREAKING NEWS! Если у вас нет опенкаповского логина, но вы все же очень хотите получить наш кубок, вы можете зарегистрироваться тут: https://contest.yandex.ru/contest/2486
UPD3 Не опенкаповские команды на контест должны попадать по ссылке выше, опенкаповские — по https://official.contest.yandex.ru/contest/2486/enter/
Statements: https://www.dropbox.com/s/nrdu4jaqamqnjdp/chu-statements-en.pdf?dl=0 https://www.dropbox.com/s/xg18wiej9xm8yqw/chu-statements-ru.pdf?dl=0
Кубок интернет-чемпиона существует только в интернете? Или отправите почтой России?)
Кубок существует в реальности, будет отправлен как-то (по итогу контеста решим, как).
почему не провести его на Codeforces, зачем Яндекс контест?
Изначально планировался опенкап, но в силу некоторых причин опенкап не случился. Систему проведения "зеркала" не поменяли, можно сказать по привычке.
.
Прошу прощения за вопрос не по теме поста. А еще гран-при кубка в этом сезоне планируются?
Вроде бы нет. Это причина, почему ЧУ не стал этапом опенкапа: изначально планировалось этапов, и они уже прошли.
Потому-что на Codeforces и так проводилось много разнообразных чемпионатов,от них все уже сильно устали. Хотя да, на КФе было бы гораздо лучше.
Will the contest be standard ICPC format? (5 hours and teams of 3 people)
Yes.
No.
Where can I find the link to the mirror contest?
Now you can find link in the post.
А как именно писать на Яндекс контесте? Я сейчас туда зашел никаких упоминаний ЧУ? Будет секретная ссылка как обычно? И под каким логином туда заходить (опенкаповским)?
Добавили ссылку в пост. Контест заливался вчера-сегодня.
По первой ссылке нет условий: ни PDF, ни HTML.
По второй тоже.
UPD: комментарий, полученный от члена жюри: бл***.
аналогично
The same.
The problem statements of mirror contest are not available.
Everyone here is experiencing the same problem.
Now post the in links
Дайте условия почитать, а то на яндекс контесте Internal server error.
(Почему не на тимусе? Зачем все усложняете? Какая-то возня с опенкаповскими и неопенкаповскими логинами, условия недоступны, что дальше?)
Условия доступны в посте
Круто.
Statements are available by the link above the submit form.
What is the solution of G?
My solution is O(nx3). It is obvious, that we should start by solving tasks, that will add 0 to utility. Only after that we will start solving other ones. The order doesn't matter for the first part and for the second part we should solve the one with higher a. Now, let's just iterate over the debt X after first part and calculate the best result with DP[i][j][k] — best utility that we can get by solving tasks starting with i, so that we reduce debt for the first part to j and to k for the second part having the debt after the first part exactly X.
I'm not sure that I understand you correctly. The set of tasks that add zero utility may change while you start taking them. Consider the following test:
For x = 105 taking the task with zero utility add will not be optimal. Does your program proceed all these tests correctly? Those tests failed all solutions we tried. (Yes, those numbers violate the constraints, you can just divide all numbers by 5).
Yes, it works on these tests. They are not hard actually.
The main idea is that after you decide what the debt Y will be after you pick all with zero utility, the first and second part become nearly independent. What is left to do is to partition all tasks into these two sets such, that debt after processing the first one will reduce from X exactly Y and the sum of utility after processing second one with initial debt Y is maximal. That is what we need DP for. On each step we decide whether we solve the task in first part (it must have zero utility then) or in the second.
This solution can be improved to work O(nx). You should go in order of increasing of a[i] and count dynamics d[i][j] — utility that we lose, where i — number of problems we go through, j — debt we get after solving problems of first type (that we solve with 0 actual utility).
I don't understand this O(nx) approach. Do you have code or can you write 2-3 lines of pseudocode? Thanks.
deleted
Как решать F,H?
F: по каждому циклу отдельно, там внутри вполне очевидный Фурье. Не забыть хранить "свёрнутые" Q-шки по разным длинам, их там не так много, а лишний N^2 получить не хочется.
H: Подвесим дерево. Для каждой вершины вычислим сколько раз 1-ая технология встречается по пути от корня до неё, пусть это F(X). Научимся находить кол-во первой технологии на пути от неких A до B: пусть общий предок C и его родитель D, тогда кол-во первой технологии будет f(A) + f(B)-f(C)-f(D). Получается нам нужны пути у которых это выражение равно единице. Обобщаем на M технологий: для каждой технологии берём некое случайное hash(X), и в каждой вершине храним суммы этой функций по всем технологиям встречающимся от корня. Нам нужен путь у которого выражение будет равно сумме всех этих случайных значений. Его можно найти динамикой по поддеревьям с слиянием меньшего множества к большему.
Можно подробнее?
Набор циклов одной длины l надо обрабатывать за раз. Если отметить все колонки, которые соответствуют какому-то циклу этой длины, можно увидеть, что обработка этих колонок сводится к циклической свертке чисел, лежащих на этом цикле, с последовательностю ql, элементы которой получаются суммированием позиций в q, дающих одинаковый остаток по модулю l. Различных длин циклов не более
, построить ql по q можно за O(m), поэтому построение всех ql займет время 
.
Понял, спасибо.
Thanks a lot to authors for the problem I!!! I love to write very stupid solution for the geometry problem, then iterate over all possible epsilons and finally rewrite the solution to BigDecimals to get AC.
BTW, it can be solved using only integer arithmetics.
So you solved it after freeze?
Yes.
Ну тут вроде всё более менее понятно. Для каждой команды есть задачи, которые они щёлкают (халва), есть такие, которые никогда не решат на 5часовом контесте (гробы). Это могут быть и идейные, и технические гробы. А между ними средние.
Теперь если две команды уровнем различаются существенно, но жюри даёт такие, что они халва для обеих команд, то кто будет выше — это случайная величина. Если же жюри даёт гробы для обеих, то опять же слабой команде может чуть больше повезти и она сдаст гроб, а сильная не сдаст.
А вот если в комплекте будет задача, которая гроб для одной команды и средняя для другой, то исход предрешён. И это хорошо с точки зрения отбора самой сильной.
Как с таким быть? Стараться, чтоб не было “резких ступенек” между соседними задачами. Иначе те, кто повиснут на этой ступеньке и те, кто её перешагнут и повиснут за ней неотличимы. Если без ступенек не обойтись, то их нужно сделать пониже (скажем, на 2 задачи ниже, чем выход в следующий этап или медали). Т.е. если у вас медали от n задач, то лучше, чтоб ступенька была между n — 1 и n — 2.
Хоть бы ссылку дал :) Не все же знают, кого ты цитируешь.
Троллинг удался, но ведь всё по делу. Провалили вы подготовку набора задач. Для команд, которые будут бороться за медали ACM ICPC 2016 очень даже хороший выдался набор. Для большинства оставшихся команд — четыре задачи и плохое настроение за последние 2-3 часа контеста.
.
А в чем позиция? Несколько раз прочитал коммент от dalex и ничего не понял.
Кто-то знает как решать К?
Заметим, что вероятность выигрыша Саши, при условии что мы знаем всего его карты и выбранный им цвет color, зависит только от количества карт цвета 0 и цвета color у него в руке. Чтобы посчитать эту вероятность, нужно перебрать количество карт цвета 0 и цвета color среди открытых y верхних карт колоды и просуммировать вероятности тех событий, при которых Саша выиграет.
Чтобы решить задачу, нужно перебрать количество карт цвета 0 в руке Саши, затем перебрать выбранный цвет color и количество карт этого цвета у Саши. Теперь осталось набрать остальные карты в руку Саши, при этом рука должна быть такой, что зафиксированный цвет color был и правда самым выгодным для Саши. По уже зафиксированной информации мы можем легко понять сколько максимально карт каждого цвета может быть у Саши (вероятность выигрыша по этому цвета должна быть меньше, чем вероятность выигрыша по цвету color). С помощью ДП (а-ля рюкзак) можно посчитать вероятность зафиксированного события.
Замечания:
У меня такое же решение, сравниваю вероятности в double, но ВА на 6-ом тесте. Что может быть?
С каким eps сравниваются вероятности? В моем правильном решении с 1e-6.
UPD. А чего меня минусуют?
Я про сравнение вероятностей на равенство. Так как к сравнению даблов дополнительно проверяется равенство соотвествующих вероятностей по модулю 109 + 7, то сравнение с большим eps — это норм. А вот если сравнивать с маленьким eps, то можно случайно ошибиться и решить, что одинаковые вероятности неравны.
Если вы считаете, что это пляска с бубном, то можете написать решение с точным вычислением вероятностей. Как я уже писал выше, оно влезает в TL.
А можно посмотреть код?
что, если значения в даблах близки, а по молулю 10^9+7 значения различны – как узнать, какая из вероятностей больше? опять в даблах?
Ага, я сравнивал в даблах (и в других альтернативных дабловых решениях жюри также). Обосновать такой факт математически я не могу, настрессить тест против такого хака у меня тоже не получилось.
Может быть, тесты и оказались слабыми. Но раз существует точное решение, укладывающееся в TL, я решил, что существование недоказанного даблового решения вполне допустимо для данной задачи. Все равно эту задачу на онсайте никто даже не отсабмитил, а в интернет-туре сабмитило две команды. Кстати, спасибо tourist за AC по этой задаче :)
А задачи чемпионата выложат на тимусе?
Да. Но недели через две-три — программный комитет разъехался в отпуска, а там есть некоторая работа по вёрстка html для тимуса.
Я прошел по ссылке на вход из поста, теперь не могу выйти; дайте пожалуйста ссылку на выход
Solution of F:
Note than if x and y and consecutive Fibonacci numbers, than y2 - xy - x2 = ± 1. Proof:
So we can find at most four candidates for the answer. (Using discrete logarithm for taking square root easily passes).
For each y, we want to check if there is such n that
We can use baby-step-giant-step again (here we using that period of fibonacci numbers is at most linear in p).
Когда Тимус поднимется?
мы скучаем
How to solve B Memory leaks(xn = (xn−1 + xn−2) mod p,(p is a prime),for a y,to find k (xk=y) or say k doesn't exist)?
This is how I solved.
F(0) = 0; F(1) = 1; F(n) = F(n — 2) + F(n — 1). Then matrix 2x2:
F(n — 1) F(n)
F(n) F(n+1)
is n-power of matrix:
0 1
1 1
There is property: det(AB) = det(A)*det(B), if A and B — same size square matrixes.
det([0 1; 1 1]) = -1 => det(([0 1; 1 1])^n) = (-1)^n => F(n)*F(n) — F(n — 1)*F(n+1) = (-1)^n
We are given p and x. If x = F(n) the we need find F(n + 1) = F(n — 1) + F(n). Assume F(n) = x. Then we've got modular equation:
a*(a+x) — x*x = (+/-)1 (mod p)
a*a + a*x = x*x (+/-) 1 (mod p) | *4
4*a*a + 4*a*x = 4*x*x (+/-) 4 (mod p) | +x^2
4*a*a + 4*a*x + x^2 = 5*x^2 (+/-) 4 (mod p)
(2*a+x)^2 = 5*x^2 (+/-) 4 (mod p)
Now we need find sqrt(A) mod p. This is standart algorithm. This. O(sqrt(p)*log(sqrt(p))).
This is how we find at most four values for a. Then we need to check whether matrix
[a x; x (x + a) mod p] power of [0 1; 1 1] mod p. This is standart algorithm too (This. Brute-force says power can be at most 2*p. O(sqrt(p)*log(sqrt(p))).
So we found all values of a.
P.S. There are two corner cases: p = 2; p = 5. (Both algorithms works on odd prime p. For p = 5 power can be at most 4*p).
P.P.S. There is more easy way?
Any hints or solution for H?
Any hints or solution for H?
Problem link : http://acm.timus.ru/problem.aspx?space=1&num=2085