Привет, Codeforces!
Сегодня, 27 сентября в 19:30 МСК, состоится Codeforces Round #202.
Идея раунда зародилась у меня и моих друзей, когда мы стажировались в Facebook этим летом. Возможно, у этого раунда рекордное для Codeforces количество авторов. Авторами задач стали Азизхан Алмахан azizkhan, Михаил Колупаев al13n, Филип Хласек fhlasek, Иван Мандура budabudimir и я, Игорь Демидов caustique.
В подготовке раунда нам помогали Максим Корыстов dark_ai, Александр Федулин Jughead, Ибрагим Исмаилов ibra, Владимир Чалышев cmd и Сергей Скляниченко Sklyack.
Идеи 2 задач мне подали Антон Ермилов ant.ermilov и Дмитрий Краснов navi-spb.
Тестировали раунд Алексей Сафронов yarrr и Алексей Шмелев ashmelev.
Также я хотел бы поблагодарить Геральда Агапова Gerald за помощь в подготовке контеста.
Надеюсь, задачи Вам покажутся разнообразными и интересными. Уверен, что каждый найдет себе задачу по вкусу.
Разбалловка стандартная 500-1000-1500-2000-2500.
Желаю удачи и удовольствия от решения задач!
Поздравляем победителей!
Div. 1
Div. 2
Внимание! Появился разбор всех задач на обоих языках!
Awesome, time of next three rounds are close!
Wow, first contest author from Kazakhstan
your name make me think about my favorite brower
catch a diaosi!!!
I think you're Chinese
Если для человека 19.30 в пятницу по каким-то причинам является неудобным временем, то он пропускает три подряд Div1 раунда. Здорово, не правда ли?
Да уже давно в пятницу вечером большинство раундов проходит :(
Кстати, по нечетным будним дням чаще всего люди ходят на тренировки(спорт зал, бокс, борьба и тому подобное), так что соглашусь, что для многих это действительно неудобное время. Хотя, можно, конечно же, пропустить тренировку.
надо сделать голосование — кому когда удобно?
В этом нет смысла. Кажется, участники должны подстраиваться, а не те, кто делают раунд.
Лично меня пятница устраивает, но я думаю, что лучше проводить соревнования в разные дни и/или в разное время (наверное так будет справедливее по отношению к участникам из разных часовых поясов)
Не участникам решать, в какое время проводить раунд. Как организаторам удобно — пусть так и будет. Но неужели им самим в пятницу вечером в кабак не хочется или куда-нибудь еще? :)
В кабак можно и после раунда сходить)
А после раунда F5! F5! F5!.. :)
Почти 4 тысячи участников отложили поход в кабак. Codeforces за здоровый образ жизни!
Значит бездельникам как я повезло!!!
Всега свободен:)
I'm damm sure, this gonna be some round !!! I mean 5 authors => awesome + cool + exciting !!! :)
Напоминает китайский контест, слишком много авторов :)
Я думаю, что это повлияет на качество контеста и, надеюсь, в лучшую сторону...
i hope there won't be any mathematical problems , but still g & hf to all
It could be fun because Topcoder SRM is just finished.. ;-)
Near two rounds. Goodluck 4 everyone.
Many authors = Many personalities = Different kind of problems = Good for everyone ;)
Не успел зарегаться из-за лагов сервера. Чего делать?
Scores will be announced closer to the beginning of the round. 2 min remain :|
this is the worst contest I've ever seen
Интересные задачи, спасибо!
Однако C кажется настолько классической задачей на корневую...
Ну как на корневую — я написал на джаве, оно даже на моём компе в ТЛ не влезало... Переписал на плюсах — стало работать подозрительно быстро, наверное, у меня бага.
Неужели там нет нормального^W n * polylog решения с какой-нибудь структурой данных?
У меня с 2-кратным запасом на джаве корневая работала. http://codeforces.me/contest/348/submission/4589661
Ну ок, возможно, у меня руки кривые^W^W^W^W не очень оптимально написал. Но всё равно интересно, есть ли
решение...
Авторское решение с корневой, быстрее не умеем.
Весь контест думал про корневую, так и не придумал. Можете поделиться идеей решения?
Разбиваем списки на два типа: тяжелые и легкие. Для всех списков считаем размеры пересечений их списка со списками тяжелых.
Тогда:
1) Добавление к лёгкому: добавляем ко всем числам в тупую, а так же проходимся по тяжелым и добавляем к их посчитанному ответу (размер_пересечения * значение).
2) Добавление к тяжелому: запоминаем, что к этому тяжелому мы добавили x.
3) Ответ для лёгкого: сумма в тупую по числам + проходимся по добавлениям к тяжелым и добавляем это число * размер пересечения.
4) Ответ для тяжелого: берем уже посчитанный ответ + проходимся по добавлениям к тяжелым и добавляем это число * размер пересечения.
http://codeforces.me/contest/348/submission/4589661
А как быстро искать пересечение всех списков с тяжёлыми?
В моём решении я просто сортил списки, брал меньший и бин. поисками проверял в большем.
Можно быстрее: У нас в списках значения 1 <= a_i <= n, следовательно можно для каждого тяжелого списка булевый массив составить: есть ли в нём a_i-ый элемент, и, итерируясь по меньшему, за O(1) проверять.
Можно было делить на легкие и тяжелые немного по-другому. Я в тяжелые кинул все те, что встречаются в запросах больше чем
раз, а в легкие все остальные. Решение от этого не сильно меняется, но на предложенных тестах работает быстрее всех других с контеста :)
1st problem has very weak pretests. I hacked 5 solutions with 25 25 25 100 ))
25 25 50 50 100 is also good for hacking ))
Thx for contest)
Can you tell me how to hacked other's solution?
After you pass the pretest, lock your problem in the dashboard using the icon like a lock, then you can view and hack others' solutions in the room page by double clicking on scores of that problem.
Thank you very much! hehe!!
Мне кажется, или в задаче B (div 1) в какой-то момент пропал разбор первого теста? Не очень-то круто для тех, кто обновил страницу.
А он был ?))) Что-то новое узнается :)
Задачи отличные, но у меня не работал сервер на последних секундах и я не смог отправить решение. Примите меры, пожалуйста.
UPD. AC в дорешку.
ДА! Это было что-то, когда на последних 10-ти секундах я, казалось, отдебажил, наконец, код, и кнопка "Отослать" не нажималась.
Причём в очереди посылок в Div1 нет посылок за последние 20 секунд, в Div2 — за последние 19 секунд, а до этого много посылок почти каждую секунду — то есть не работало вообще у всех. Обычно есть посылка в несколько последних секунд.
Очень хотелось бы услышать какой-нибудь официальный комментарий.
Я прекрасно понимаю, что сервер часто дает сбои, тем более в конце раунда, понимаю что 20 сек от 2 часов это очень мало и можно признать погрешностью, но я совершенно не понимаю, почему видя это нельзя было продлить раунд на условные 5 минут? На мой клар о невозможности сабмита через 20 минут после раунда пришел божественный ответ "без комментариев", после чего мой очаг заполыхал как доменная печь.
И да, мне не жалко 1 единицу рейтинга, я за идею =)
Мы тоже за идею. :)
Подумайте сами, как мы могли заметить, что сервер не работает последние 20 секунд? Я честно во время любого контеста часто (раз в минуту точно) обновляю страницу, иногда время ответа больше, иногда меньше. Иногда бывает, что нужно 20 секунд подождать. Сегодня, в последние 20 секунд, мне кажется, я не обновлял страницу, потому что изучал решения участников, поэтому ничего особого не заметил.
Но... даже если бы я заметил, что сервер не отвечает, за 20 секунд очень сложно перенести раунд (нужно написать рассылку о переносе, и еще поменять время конца раунда). А переносить раунд после его окончания однозначно нельзя. Причина: увидев сообщение о конце раунда, кто-то может уйти от монитора сразу. Получается не справедливо.
Мне кажется, мы поступили разумно, что не поменяли время конца. Такая погрешность — это, конечно, плохо, мы стараемся все сделать, чтобы Codeforces работал стабильнее. Но все были в равных условиях. Если бы попытались поменять время конца, скорее всего баланс был бы нарушен.
Если в беге на 100 метров на олимпиаде рассыпать на дорожке песок или на футбольном матче завязать всем глаза, то все тоже будут в равных условиях — давайте без таких общих аргументов.
Почему тогда раунд рейтинговый? Почему нельзя сделать его нерейтинговым для тех кто от этого пострадал?
Ой, и я пытался сдать за секунд 5 до конца...
Задачи понравились, авторам респект. Как всегда, завис хром на последних секундах, и решение по Б не отправилось. Если оно зайдёт в дорешку, я буду очень зол. Нет, я не обвиняю хром в своей неудаче, я сам виноват, что отправлял в последние секунды, но сами понимаете, как обидно.
Зашло? :)
Нет. Идея правильная, но реализация ужасно кривая)
Зато сберег нервные клетки. Везде нужно плюсы искать.
Я обычно ищу джаву.
Many tricky cases in problem A(Div 2) ... :D
I hacked six solution with 25 25 25 100 &
25 25 25 100 50 ...:)
Thanks for the contest... :)
Mine is 25 25 25 100 & 25 50 50
the problems of today's Div-2 contest are tougher than usual Div-2 contests! i wonder why?
Как генерировать тест для B который валит решение на переполнение lcp? То есть найти набор чисел, lcp которых при переполнении дает число по модулю меньше 10^8.
имеете в виду lcm?
Упс
Например, так: найти такое число вида 264 + k с числом k до 108, чтобы сумма его простых делителей была меньше 105. Например, вот одно такое число: 18446744073709552034 = 2 * 7 * 31 * 673 * 853 * 1669 * 5821 * 7621, k = 418. Ищется несложным перебором.
Ну и дальше есть корень, у его восьми сыновей 2, 7, 31, 673, 853, 1669, 5821 и 7621 сыновей-листьев, соответственно. Теперь, если во все листья повесить ai = 108 яблок, вероятно, всё сломается (кто хочет проверить?).
Pretest 9 for Problem B Div 2 :(
I think pretest 9 is smth like this:
5
3 3 3 3 3 3 3 2 3
Found one special case:
83 4 4 5 10 10 10 10 10Though I didn't pass yet. Answer should be 23.
I think the answer is 41
Yes, my fault. 41 is the correct answer.
To hell with this pretest 9 on Problem B Div 2.
Nothing was helping me, but total rewriting helped.
Might be one of these : 11 3 3 3 3 3 3 3 3 4
OR
9 2 10 10 10 10 10 10 10 9
well, as it turned out, Pretest 9 was a big test case, different from what we expected :P
Why div.2 so hard just on problem B... Do I only have to solve it by DP?
I solved the problem by dp but I saw some greedy solutions but I do not know if there correct
Found one special case:
83 4 4 5 10 10 10 10 10Though I didn't pass yet. Answer should be 41. Greedy seems to be unavailable.
no, 41
it should be 41 41 > 23 I use greedy for my solution but no so sure about it :D
no answer should be 41 since you can use 4 (costs 5 ) and 1 (costs 3)
by a glance on the question I think we need to use at most 2 digits for all optimal solution. O(9*9)?
I think we must try get max numbers and then change some first on other, more big. I don't sure. http://codeforces.me/contest/349/submission/4583482
Yes, It was correct solving. I got OK
no for examle 61 7 8 8 8 8 8 8 8 9 it should be 99811111
Thanks for this testcase.
Need to use DP for problem B.
nope, greedy solution is ok just find maximum digit can be made and use the remainder to change some first digits into higher digit
Cool.. Thanks for your input. I did use greedy at first but messed up with the implementation.
Hope no FST, and be red after this round. :D
Congrats for being RED :)
Thank you.
& whats fst?
It's Failure System Test.
Wow, so many Runtime Errors in final testing for Div1 B. Even Egor failed this problem.
Almost everyone who solved problem Div-1 A did binary search, this is my accepted solution: 4576049
It's just O(1) (after reading the input), to be honest I couldn't prove if this solution is correct or not. Can anyone check it please and tell me why it's correct? Or are the test cases weak?
I can prove only that it is correct — my O(1) solution passed. Proving correctness is harder.
http://codeforces.me/contest/348/submission/4576666
nearly same compared to you
answer >= max(a[i]) and the second inequality is your binary search's inequality. Solve this system and be happy :)
Can you please explain how you applied Binary Search on this problem? I really want to know, because I could just think of brute-forcing it.
You must chhose number of game — m, then check, than all in array <= m and that free players more that m(for arbiter). http://codeforces.me/contest/349/submission/4581586
It's easy to see. Let the answer be K. So the first person can be supervisor in (k — a[0]) games, the second in (k — a[1]) games and so on. So (N * k — sum(a[i])) games there is a supervisor. It must be bigger or equal than K cause there were K games. N * K — sum(a[i]) >= K. K * (N — 1) >= sum(a[i]). And we didn't mentioned that K >= max(a[i]) (that's obvious). So the answer is MAX(MAX([i]), sum(a[i]) / (N — 1));
It is obviously correct. Let xi be the number of rounds skipped by i'th person,
. We need xi ≥ 0, X - xi ≥ ai, so xi ≤ X - ai. Summing up, 
. Consider arbitrary X such that this statement is true. Then you can take xi = X - ai - αi, so that αi ≥ 0, 
. Since right side expression is ≥ 0, such αi exist, this finishes the proof.
Кажется, мы стали забывать, что такое слабые претесты, господа.
Really intresting problems. I liked all of them , especially D form Div1. I think these were very original problems. Congrats to the authors ! Thank you , you made my day ! :D
Btw, can someone explain how to do B-div1 & D-div1.
Actually D is just a quite straightforward application of this theorem: http://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma
Moreover, searching for number of tuples of nonintersecting paths, we can see this article as second link in Google.
This theorem was used in recent Japanese competition.
When will ratings be updated?
Can someone please gives some idea about DIV2 C?
we can solve it by making an equation like this : ans ==> the answer/minimum game must be make
(ans-a1) + (ans-a2) + ... + (ans-an) >= ans (the sum of all players become supervisor must be greater or equal than the minimum game)
in short we can found ans >= ((a1+a2+...+an) / (n-1))
but only by that it'll be failed in test case when there are some players that didn't need to be supervisor at all (in example case : 8 4 4 4 4 1 1 1 1 should output 4 instead 3) so the answer become max(ans,max_game_player_needed)
hope it help :D pls correct me if im wrong
Awesome problem-set..!!
Waiting to know solution of D div.2
deleted!
else if (y > 2) { y-=3; }
must be else if (x > 2) { x-=3; }
Seems like D was solved by 29 people from Asia and ilyakor. May be it was well-known problem for them? rng_58 submitted it on 12th minute.
Maybe it is well-known for Asian guys. I expected also some Russian guys such as Dmitry_Egorov and you will be able to solve it
(this is a russian thread, btw)
I did not know this problem before. I remembered an idea for a (kind of) similar combinatorial problem. The idea is as follows: if you have a pair of intersecting paths
and 
, you can bijectively map them to the intersecting paths 
and 
(by taking the first intersection and swapping the tails). And in the case of problem D "intersecting paths 
and 
" means the same as "arbitrary paths 
and 
".
Maybe Asian people just have better skills in combinatorics? :) Though I'm really surprised that nobody from Russia solved it; I'd expect that such ideas are totakky standard for the members of russian IMO teams.
Меня эта посылка на 12й минуте сбила с толку: подумал, что задача является какой-нибудь несложной модификацией "одной черепашки" и все оставшееся время думал, как расширить состояние в ДП. И лишь к концу раунда, увидев ~20 посылок, начал задумываться, что там не все так просто :)
Hi there! :)
I submitted my B problem's solution in the contest, and the checker gave wrong answer; but in my PC and in even in the custom test, it gives the right answer! Even I submitted it after the contest, but it gave wrong answer too. Here's my submission. Can anybody give any reasons for this? I would be happy if Codeforces moderators could explain this. Thanks! :D
Sorry, I found my mistake :D
Did anyone in Division 2 exceed memory with a DP on Problem B? I haven no idea what happened on mine. :O
You are using a String array of size 10^6 , so it is so obvious the reason why
I'm in div 1 now
Can anyone help me with Div.2 Prob. A ? Link : http://ideone.com/b0HLLw
It shows WA on test case 12. Please help. Thanks.
It looks like you totally misunderstood main problem statement or solution idea. ;-)
Please correct me if I am wrong. With taking input, I am checking whether the desired change is available or not. If true, I am adding 25 to the counter, else , I am printing "NO";
Your code is wrong with case like:
725 25 25 50 50 50 100Answer should be "NO".
Thanks to all for replying. I got my mistake. The shopkeeper can only give change with the help of those bills which he has got from previous transactions i.e; by using 25, 50 or 100 bills.
А расскажите, чем такая идея по Div2-D / Div1-B неправильная... Ориентируем дерево обходом в глубину из вершины. Добавляем все листья в очередь. Пока очередь не пуста — берем top и обновляем его предка, затем добавляем этого предка в очередь (если не сделали этого раньше), делаем pop. Как обновляем предка. В сбалансированном дереве в нем должно стоять такое число: количество сыновей, умноженное на минимум среди них. Количество сыновей мы знаем изначально, поэтому просто обновляем минимумом. ЧЯДНТ? Падало еще на втором претесте. Вот код: codeforces.ru/contest/349/submission/4589209.
Hi everyone!
My solution for Div1 B failed on final test 32, and it cannot be viewed completely under the submission. Does anyone know what final test 32 for Div1 B is?
Thanks!
I do not know about test case #32. However, there goes a common mistake that lcm exceeds "long long" range, which may be divulged under a huge input, but you can pass through the pretest with the mistake.
I was hoping that there would be at least one Big Lebowski fan around here, so I introduced few references into the problem statement. Hope you enjoyed the round :)
Задача Div1-А. Подскажите, если есть N чисел А, то ответ (А + 1)?
Не всегда. Например, на тест
ответ будет 5.
Нет. Например, N=3, A=4. Никак не выйдет за 5 раундов. Доказать можно так: пусть a,b,c — кол-во раундов в котором были ведущими 1, 2 и 3 соответственно. Тогда a+b≥4, b+c≥4, a+c≥4 (чтобы удовлетворить всех). Если сложим эти три неравенства, получим a+b+c≥6. Значит не меньше 6 раундов. Случай, когда N одинаковых чисел ничем не отличается особо от остальных.
Задачи были интересные, спасибо за них)
Could someone explain why this submission has became tl? It's a simple greedy that a lot of people have got accepted with this method. http://codeforces.me/contest/349/submission/4581168 Thanks.
for(int j = 8; i >= 0; j--)...problem with problem B DIV 2.
Where are you, editorial?
Посмотрел некоторые нормальные решения задачи Div.1 B и увидел gcd и/или lcm в коде.. Не ожидал, что моё тупое решение зайдёт по времени, так как просто симулировал алгоритм удаления листьев "по мере надобности", O(N * x), где "x" — количество итераций до тех пор, пока дерево не окажется сбалансированным, а оценить "x" адекватно не смог.
This question is a bit difficult to read
oh man i forgot it yesterday
div 1 problem is really challenge for me, i wonder where is the tutorial?
When will the Editorial come? Can't Wait to see it for Div. 1 B...
Problem B is unpleasantly similar to 2012/13 Czech/Slovak Olympiad in Informatics (these 2 share the problems and are held at the same time), Regional round, problem 2. The only difference is that we had a binary tree in that problem. The general one needs extending the idea and there is a lot of possible overflow to take care of (since that problem was theoretical), but I feel that it helped me get a better result.
Hey Xellos, I like a lot your way of explaining problems ideas, so could you give a short description for Div2 problems. A sort of short tutorial :)
I would, but I still haven't solved Cdiv1, and I kinda don't want to make an actual editorial if I'm not the author. If it doesn't appear in several days and I solve the rest of the problems, I might post one instead.
А писать разбор уже не престижно?))
Screencast
thanks a lot Egor! i really enjoyed watching this!
can u continue to make screencasts for future contests? thanks in advance! :)
For Div-2 B my approach,
Find the minimum d ( minimum amount which takes to paint a digit with highest index) and divide the total paint by min d. This number gives total no of digits which can be painted. i.e. the answer will have this many digits.
Now only thing you can do is, if there is still left over paint ( total paint — paint used upto this point ), you can improve, in the sense you can replace already used digit and left over paint with a higher digit by using greedy method.
Repeat the improvement until you have some left over paint and there is a digit with higher index which you can replace.
My Solution
Still no editorial :/
Editorial, where are you?
Editorial Please ??!!
Please post the editorial for div. 1!!!
Please post the editorial for div 2
Видимо авторы сами все еще не решили свои задачи))
Thanks for the contest!
Won't there be an Editorial?!
Thanks for the editorial too.
Hi! Does anyone of you know an approach to solve Div1 C problem? I'm very curious about its solution.
Thanks to SillyHook06, whose superb contest submission helped me solve this awesome problem !!
The essential idea is to bifurcate all given sets as big and small: Let us denote by T the collection of all big sets [those sets which have size >= sqrt(n)] and by S the collection of all small sets [those sets which have size < sqrt(n)].
What remains is to exploit the following two properties:
1) Each element of S contains atmost sqrt(n) elements.
2) The total number of elements in T is atmost sqrt(n).
To do this, one can precompute for each big set, the sizes of its intersections with all other sets. Precomputation takes O(n*sqrt(n)) and processing each query takes O(sqrt(n)).
I find it difficult to state all details in a short post. Here is my practice submission (with a few comments): 4607191
Big thanks for your reply :)
I will attempt to briefly explain the query processing:
a[i] stores the current value at position i considering only the updates on small sets.
(eg: The initial array is all zeroes. Big set #0 and small set #1 both contain the index 3. Set #0 is updated with 4 and set #1 with 7, then a[3]=7)
ct[i] stores the total update value on big set i
(eg: if set #2 is a big set and is updated thrice with values 2,6,3 then ct[2] is 11).
sum[i] stores the current result of big set i considering only the updates on small sets
(eg: The initial array is all zeroes. Set#0 is big and set #1 is small. The intersection of these sets is of size 2. Set #0 has been updated twice with 3,4 and set #1 once with 5. Then sum[0] will store 10, ignoring all the updates on all big sets including itself.)
Update a small set X: Update a for all elements of X, sum for all big sets.
Update a large set X: Update ct(X).
Query a small set X: Sum up a values of elements in X. Add to this the sum of ct(Y)*|intersection(X,Y)| over all big sets Y.
Query a large set X: Sum up ct(Y)*|intersection(X,Y)| over all big sets Y. Add to this sum(X).
Can someone tell me how to solve div1 B and div1 C? I have no idea.
How about reading the comment just above for div1 C before you ask?
div1 B: DFS the tree; the sum in a subtree of vertex i must be a multiple of some number M[i]; then, M[i]=LCM(M[all sons])*(number of sons of i), find the largest sum in subtree of a son satisfying that. Watch out for long long overflow.
I am sorry I haven't seen the previous comment.Thanks for your reply :)
Классный раунд, спасибо автору за контест. Ждем новых задач...
Отлично! Разбор появился (все кроме Е див. 1) и пропал!)) а ссылка ведет сама на себя
I hope someone can translate the editorial into English ! Thanks.
Well, I have found the entry for English version. It may help me a lot.
Can you give the link for the English Editorial??
You can check here :)
Thanks mate