Привет, Codeforces!
19 февраля 2016 года в 18:00 MSK состоится восьмой учебный раунд Educational Codeforces Round 8 для участников из первого и второго дивизионов. Надеюсь плотность контестов на Codeforces в эти несколько дней вас не спугнёт и вы напишете ER8.
<В конце добавилась фраза про простые задачи>
О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.
Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день, в течение которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.
Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.
Не стесняйтесь присылать простые (и даже очень простые) задачи (но обязательно интересные). Почти каждый раунд достаточно быстро выбираются кандидаты для задач C, D, E, F, а вот задача A обычно ставится самой последней, когда уже почти всё готово.
</В конце добавилась фраза про простые задачи>
В этот раз, впервые, полностью комплект задач был предложен участниками сообщества. Задача А была предложена пользователем unprost. Задача B взята из комплекта, который прислали Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. Задачу D предложил Kareem Mohamed Kareem_Mohamed (я её правда сильно усложнил, чтобы вам было интереснее :-)). Задачу E прислал Ali Ahmadi Kuzey. Задачи C и F были предложены Камилом Дебовски Errichto.
Благодарю их и всех кто присылает задачи или просто наброски!
Подготовкой задач в этот раз занимался не только я (Эдвард Давтян). Большое спасибо Камилу Дебовски Errichto, который не только предложил задачи C и F, но и подготовил их. Спасибо Маше Беловой Delinur за проверку английских текстов условий. Также большое спасибо Ali Ahmadi Kuzey, который помогал с тестированием задач.
На этом раунде вам по традиции будет предложено шесть задач.
Вкратце опишу задачи: A) Простая задача с немаленьким условием; B) Надеюсь вы не будете здесь писать ничего сложного; C) Интересная; D) Немного техническая, содержит очень полезную технику; E) Мне эта задача очень нравится; F) Супер клёвая задача, если не удастся сдать на контесте рекомендую дорешать.
Good luck and have fun!
UPD1: Первая фаза соревнования закончена. Начались взломы. Разбор задач готов.
Поскольку все задачи Errichto про медведей ниже находится иллюстрация к задаче C (Limak кажется первый слева):
Very intresting :) B problem creatad by three users :)
3 contests on 3 consecutive days (and then USACO right after them) :D
And Codechef Cook off and HackerRank 101 Hack on Sunday!
And today will be , Usaco Feb Third contest, and Hackerearth!!!
I liked it when i registered at two Educational rounds at the same time :)
I liked it when i registered at two Educational rounds at the same time :)
Hi It was a nice statement :) I hope problems like the statement be nice and short :) Ty man
nice
Limak returns :)
Bear, I think..marat.snowbear
Please extend the contest by at least 15 minutes. I couldn't access codeforces because of server problems. edit:I am serious.I could open all other sites!
По-моему, рекомендовать в 2016 году пользоваться функцией
gets— ужасно вредный совет (учитывая, что строки длины порядка 105 вводятся с помощью cin за вполне приемлемое время). Её, между прочим, нет в стандартах C11 и C++14, а man gets гласит: «Never use this function».Это все-таки олимпиадное программирование, здесь какая функция быстрее работает, такую и используй.
В man gets написано никогда не использовать эту функцию только из-за безопасности в программах, что для олимпиадных задач не играет никакой роли:)
Ну не знаю, получать сегфолты, когда их можно избежать, не очень приятно. Непонятно, зачем использовать устаревшую функцию только потому, что она вроде как быстрее, если хватает производительности стандартных методов IO.
Эту функцию я добавил скрепя сердце. Конечно, она не безопасная. Современные компиляторы даже выдают предупреждение при её использовании. Но она работает очень быстро и очень полезна на олимпиадах.
Edvard , I think that you love Problem E because of its game(Zbazi).
I dunno that game.
it's more like a band than a game :D
Как решить D?
Разбор появится непосредственно после соревнования.
Попытка не пытка:D
Now your task is to help tourist
Вроде бы придумал решение по Д, но потом полтора часа пытался в нём разобраться... Но так и не смог...
DAMN IT! My Geany crashed two times erasing completely my E both times and I just finished it for the third time, it's done, 5 seconds after it ended :/
UPD: Even worse, it now gets accepted... :@ :@ :@
changed cin from 16209365 to scanf in 16211539 and got accepted.
Image
Use cin or scanf, never use both. Update: Tried to use all cin/cout but still got WA. Now I get confused...
cin xor scanf? :D
i think we shouldnt use both cin and scanf when using sync_with_stdio link link
Why? It works for me.
Accepted
any ideas for D? How to make it efficiently despite the fact N is so big?
dynamic programming !
Dude... you're brilliant
I am using dynamic programming dp[i][index][remainder], i = 0,1,2, when i == 0 it means all previous digits[0..i -1] are the same with lowerbound string and when i == 2, all previous digits are the same with upperbound string, when i == 1, we can choose any number from 0 to 9. as for the remainder, the idea is very similar with problem B. So we should discuss cases when index is even or odd, I feel my solution is kind of troublesome and there are many corner cases, but at least it works right now :) You can refer to my code http://www.codeforces.com/contest/628/submission/16211896
You don't need to make that distinction (i = 0, 1, 2). First of all, subtract 1 from a, then just count the amount of nonnegative d-magic numbers less than or equal to a and subtract it from the amount of nonnegative d-magic numbers less than or equal to b.
Additionally, while you do need to keep track of the case where all digits are equal to the upperbound, there's no need to make an entire vector for it since there is always either 1 or 0 ways to do it (the latter happens when the upperbound is not d-magic).
Implementation: 16208100
Yea, I can avoid a lot of corner cases without i = 0,1,2 thank you :P
Incidentally, the idea for B is actually much simpler (due to M being 4). The blog says "I hope you will not write hard solution",
Thank you guys! With your help and the editorial I managed to code the solution :))
The most tricky part was how to deal with the modulo result because of course if the numbers length was of 2000, then you would need to add something like 10^2000 to the modulo value when you are testing different values for these numbers. The trick is awesome, to maintain all the modulo calculations in the 0-M range you don't need to power 10^1000, because although you start processing the i=0 that is the more significant digits you act like the other part of the number does not exist and every time you add one more digit, you just multiply by 10 the current modulo, add the new digit and make it modulo M. I am not sure why this modulo property applies, but it is brilliant
Problem A is like:
No hacking phase ?
Hacking phase is ON. You can view anybody's solution and proceed forward into hacking! :)
Thanks! Didn't know that
Thanks , Really amazing contest ,looking forward to the solutions. Good job
Very interesting!
in 2nd problem , changing from %lld to %I64d gave an ac.! why is that so ?
Are you sure about it? It looks weird.
Again let me thank authors for polar bear problems.
halyavin is using Energizer batteries, instead of Simple ones :)
Сейчас можно увидеть финальные результаты после добавления тестов и перетестирования? А то было бы очень странно, если бы перетестирование проходило прямо во время проведения другого раунда.