Привет, Codeforces!
Поздравляю вас с наступившим новым годом! Позади остались праздники и 2015-й год, а впереди 2016-й. Желаю вам достижения всех поставленных целей и конечно удачных выступлений на соревнованиях по программированию.
11 января 2015 года в 18:00 MSK состоится пятый учебный раунд Educational Codeforces Round 5 для участников из первого и второго дивизионов.
<Год прошёл два абзаца остались>
О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.
Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.
</Год прошёл два абзаца остались>
Большое спасибо Григорию Резникову vintage_Vlad_Makeev, который предложил и подготовил хорошую задачу (она будет под буквой F). Если у вас есть идеи каких-то задач, которые вам кажутся интересными, или может есть уже что-то почти готовое, что вы по каким-то причинам не можете дать на раунд (злой координатор сказал, что задача БАЯН), официальное соревнование (жюри не хочет переграбливать соревнование), можете писать мне.
Подготовкой задач как всегда занимался я (Эдвард Давтян). Благодарю MikeMirzayanov мы вместе придумывали задачи (в этот раз по телефону). Также заранее благодарю Машу Белову Delinur, которая скоро вычитает английские тексты условий.
На этом раунде вам по традиции будет предложено шесть задач. На мой взгляд в этот раз задачи проще, чем в прошлый. Исключением можно считать лишь последнюю задачу. Надеюсь комплект вам понравится и вы хорошо порешаете задачи!
Good luck and have fun!
UPD 1: Первая фаза соревнования закончена. Открыта фаза взломов.
UPD 2: Разбор задач на русском языке готов.
UPD 3: На этапе открытых взломов был обнаружен следующий спецэффект: решения на языках Python2 и Python3 имеют значительную разницу во времени выполнения в разных максимальных тестах. Например, решение на Python3 работает очень медленно на тесте из всех нулей, а на Python2 на тесте из всех девяток. Некоторые решения работают чуть больше или чуть меньше секунды, поэтому было принято решение поднять ограничение по времени в задаче А до двух секунд. Вскоре закончится фаза открытых взломов и все решения будут перетестированы.
UPD 4: Соревнование завершено. Вскоре все решения будут перетестированы на полном наборе тестов, включающем в себя взломы.
Каждый раз проще чем предыдущий :)
В прошлом году все educational round были по Пятницам. В этом году они будут только по понедельникам? Или это только один раз?
I am
Due to "some Apple magic" I noticed such a letter in inbox instead of normal one...
The first idea was that CF made
The First Holy Round For Hackers
, but it's just Educational :DЭ-эх, пропало волшебство(
Yes!New season,new beginning!With our passion unchanged
Шутка про Internet Explorer?
yes!New season,new beginning!With our passion unchanged!
I don't see any way to withdraw my registration from this round. Is it because the round is unrated?
It's no problem if you register and don't participate.So if you want to withdraw your registration from this round, click on the number of the registered participants for the contest, click on friends and now you can withdraw your registration from this round by click on the X.
Ждём взломов. :D
Though it is not particularly relevant to this round, I wanted to point out a rather tiny glitch with the website. It is cool that we see the local time of the contests in Contests page, and not having to check it on timeanddate. However, the live countdown in the rightmost column of the table named "Current or upcoming contests" is probably still based on Moscow time. It currently shows there is 4.49hrs until the registration is closed, and it appears it will hit 0 at 18.00(Moscow time) which is the starting time of the contest.
Correction: It apparently includes the contest time as well. My bad. You may ignore this comment.
we can not search a problem with the caregory name. Like if i search problems with category name dfs, then blog result shows us. is it possible to search problems with category?? This will be very helpful. Thanks
Problem Tags: http://codeforces.me/problemset/tags/dfs%20and%20similar
Auto comment: topic has been updated by Edvard (previous revision, new revision, compare).
Nice problem E, thanks
Thanks. I'm sorry for the issue in this problem. My solution had overflow problem and I fixed it.
I am getting TLE in E in algorithm. Can you help? http://codeforces.me/contest/616/submission/15301347
Actually your solution is . Use the following in mul(a, b):
UPD: I see that it's . My solution uses a lot of mod operations and works in 530ms. So I think 2s TL should be sufficient.
Thanks a lot. I used a for loop to do two things simultaneously. That was a bug.
when I read problem E I recognized it to be a general case of a which is equal to ... I tried to follow that line and arrived at
writing it as a convolution equation
leading to an solution unfortunately in the mist of my triumph I didn't notice that we need to print % 1e9 + 7 or the possibility of overflow until the end of the contest ,poor me :'(
Can we have the editorials pls? :)
It is hacking time after contest with duration about 24 hours, only then we will have editorial
I'm working on it. I've about finished the Russian version.
First problem was too easy for those who use Java, Python or have a BigInt class template in C++.
Third problem was a duplicate from USACO contest.
Fifth one's solution appears first when you google "Sigma(n mod i)"
Good thing this round is unrated.
BigInteger and Python2 with input() get TL.
This round was supposed to be educative. So I guess it is okay to use already published but educative problems from where we can learn things. :)
Right.
На Java у многих не проходила первая задача? Просто для интереса пробовал на java, потом забил и сдал на C++
При использовании BigInteger решение на Java не должно проходить. Если же всё делать в строках, то никаких проблем нет. У меня было даже два решения на Python2 и Python3, которые работают 30ms.
In Problem 616C - The Labyrinth why my solution 15292451 gets WA?!
Your solution gives no output with:
12 1 ************
this is my solution with your case,
Correct output.
http://codeforces.me/blog/entry/22691?#comment-272050
Looks like A has quite a lot hacks. Will there be some statistics after finishing the hacking phase?
After coding phase the number of correct solutions is greater than 1700. We will see how many solution will pass all tests tomorrow.
there's already been close to 400 hacks . Most of them TLE I guess
Why should someone Enjoy when a problem is rejudged?
How come the input file for the hacks are only up to some 200+ KB? I tried an array with 5*10^5 integers, and it led to 3MB+
use input generator!
What is the idea behind E?
can also be written as a - (a / b) * b (Integer Division)
now a / b only has distinct values ranging from [1 to and also all values of the form a / i where . Just use this fact. Code
I am confused from where can we conclude about sqrt(a) distinct values?
a/b is either less than sqrt(a) (if b is greater than sqrt(a), there are O(sqrt(a)) distinct values) or greater than sqrt(a) (if b is less than sqrt(a) but since there are O(sqrt(a)) values for b, the same holds for a/b) which means there are O(sqrt(a))+O(sqrt(a))=O(sqrt(a)) distinct values for a/b :)
At problem f I used suffix arrays with lcp precalculations,then just a stack and that's all. I still can't figure why I get wa on test 12.Is anybody who had the same problem? Can you help me fix this?
Edvard could i see the full data of test case #11 on problem 616C - The Labyrinth
It gives me WA and the Checker comment says that i wrong in the 1st line which i run this part in my machine and give the correct output!!!
Have same problem http://codeforces.me/contest/616/submission/15302835
Oh — int cnt[1010] should be cnt[1010*1010]...
Generator and command line "gen 100 1000 10".
What's wrong with my solution for Problem C? http://codeforces.me/contest/616/submission/15297727
Moreover, at test case 11, where it says my code fails- Here, my answer matches with the jury's answer(at least the part which we can see), however, it doesn't match with expected value. Isn't it strange? The expected value does not match with jury's solution.
I've posted generator with command line above.
Hi Edvard,
Please How can I write test generator with Java 7 ? Is there a format I should follow ?
You should only print your test to standard output (screen) considering the format of output from the problem statement. See my generator on C++. Of course you can't use testlib.h in Java, but you don't need it.
Here is the simple generator on Java 7.
saw someone using i<strlen(str) in for loop and ran it in my machine. gets TLE but when I ran it here it runs ok . No idea what's going on :v
Compiler Optimizations -O2 flag when you execute code here. Maybe you have not enabled it. strlen would be about O(n) complexity everytime you call it.
that makes sense, I had no idea they had optimized the compiler so much here
Please what is the format for writing a Test generator for Java 7. The output file will be > 1mb. ?
as far as i know, u just have to write a program that prints the test case in the output stream and make sure to give a newline at the end
Yes you are right.
I don't like a complicated C problem,but a easy d problem. :(
UPD: hacked Thanks
Done.
Is it bug or feature?
Russian version of the site says that it's feature. Didn't managed to find analogous information in English one.
Wow!
Почему показатели количества решивших задачу в меню раунда "задачи" и в его таблице "положение" различаются?
I find so hard to read code (example http://pastebin.com/AdDQDtWy) with all these defines forn, sz, pb, etc why can't the code be just as is / simple with no defines
What am I getting wrong here? I get different output for N = M = 1e13 (it matches up to 1e8 or so)