Hi, Codeforces!
Happy New Year! Holidays and 2015 year have passed and year 2016 is ahead. I wish you good luck in programming competitions and achieving all of your goals this year.
Educational Codeforces Round 5 will take place on 11 January 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.
<A year has passed, but paragraph remains unchanged.>
The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.
</A year has passed, but paragraph remains unchanged.>
Thanks a lot to Grigory Reznikow vintage_Vlad_Makeev who prepared a good problem (the problem F in ER 5). You can send to me some ideas of problems or maybe already prepared problems that you can't use in rounds or official competitions.
As usual the round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov for helping to invent the problems. Also thanks in advance to Maria Belova Delinur who will check English statements.
I think the problems is not difficult (except maybe for problem F). I hope you will enjoy the problems and solve all of them!
Good luck and have fun!
UPD 1: Coding phase is finished. You can hack other solutions for 24 hours.
UPD 2: The editorial is ready.
UPD 3: During the phase of hacks we found the following: the same solutions on Python2 and Python3 works differently on different large tests. For example, some of Python3 solutions works very slow on tests with only zeros, but Python2 works very slow on tests with nines. Some of solutions works in around one second so we decided to increase the time limit for the problem A to 2 seconds. All the solutions will be rejudged soon on the complete testset.
UPD 4: The round is over. All solutions will be rejudged soon on the complete testset (includes the hacks).
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 :Dyes!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.
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.
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)