### Edvard's blog

By Edvard, history, 5 years ago, translation,

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 gritukan 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).

• +213

 » 5 years ago, # | ← Rev. 4 →   +16 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
 » 5 years ago, # |   +5 yes!New season,new beginning!With our passion unchanged!
 » 5 years ago, # |   0 I don't see any way to withdraw my registration from this round. Is it because the round is unrated?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +4 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.
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ |   +16 Correction: It apparently includes the contest time as well. My bad. You may ignore this comment.
 » 5 years ago, # |   -6 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
•  » » 5 years ago, # ^ |   +15
 » 5 years ago, # |   0 Auto comment: topic has been updated by Edvard (previous revision, new revision, compare).
 » 5 years ago, # |   +16 Nice problem E, thanks
•  » » 5 years ago, # ^ | ← Rev. 4 →   +19 Thanks. I'm sorry for the issue in this problem. My solution had overflow problem and I fixed it.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 I am getting TLE in E in algorithm. Can you help? http://codeforces.com/contest/616/submission/15301347
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Actually your solution is . Use the following in mul(a, b): ll mul(ll a, ll b) { a %= mod, b %= mod; a *= b; a %= mod; if (a < 0) a += mod; return a; } 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.
•  » » » » » 5 years ago, # ^ |   0 Thanks a lot. I used a for loop to do two things simultaneously. That was a bug.
•  » » » 5 years ago, # ^ | ← Rev. 5 →   +12 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 :'(
 » 5 years ago, # |   +15 Can we have the editorials pls? :)
•  » » 5 years ago, # ^ |   0 It is hacking time after contest with duration about 24 hours, only then we will have editorial
•  » » 5 years ago, # ^ |   0 I'm working on it. I've about finished the Russian version.
 » 5 years ago, # |   -29 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.
•  » » 5 years ago, # ^ |   +29 BigInteger and Python2 with input() get TL.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 hey i was constantly getting wrong answer in 3rd problem dnt knw why tried all cases. any hints since i dnt think editorials will be up in around a day..thanks
•  » » 5 years ago, # ^ |   +3 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. :)
•  » » » 5 years ago, # ^ |   0 Right.
 » 5 years ago, # |   0 In Problem 616C - The Labyrinth why my solution 15292451 gets WA?!
•  » » 5 years ago, # ^ |   0 Your solution gives no output with:12 1 ************
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 this is my solution with your case,Correct output.
•  » » » » 5 years ago, # ^ |   +1
 » 5 years ago, # |   0 Looks like A has quite a lot hacks. Will there be some statistics after finishing the hacking phase?
•  » » 5 years ago, # ^ |   0 After coding phase the number of correct solutions is greater than 1700. We will see how many solution will pass all tests tomorrow.
•  » » 5 years ago, # ^ |   0 there's already been close to 400 hacks . Most of them TLE I guess
 » 5 years ago, # |   -17 Why should someone Enjoy when a problem is rejudged?
 » 5 years ago, # |   0 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+
•  » » 5 years ago, # ^ |   0 use input generator!
 » 5 years ago, # |   +1 What is the idea behind E?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +6 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
•  » » » 5 years ago, # ^ |   0 I am confused from where can we conclude about sqrt(a) distinct values?
•  » » » » 5 years ago, # ^ |   0 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 :)
 » 5 years ago, # | ← Rev. 2 →   +18 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?
 » 5 years ago, # |   0 Edvard could i see the full data of test case #11 on problem 616C - The LabyrinthIt 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!!!
•  » » 5 years ago, # ^ |   0 Have same problem http://codeforces.com/contest/616/submission/15302835
•  » » 5 years ago, # ^ |   +1 Oh — int cnt[1010] should be cnt[1010*1010]...
•  » » 5 years ago, # ^ |   0 Generator and command line "gen 100 1000 10".
 » 5 years ago, # |   0 What's wrong with my solution for Problem C? http://codeforces.com/contest/616/submission/15297727Moreover, 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.
•  » » 5 years ago, # ^ |   0 I've posted generator with command line above.
•  » » » 5 years ago, # ^ |   0 Hi Edvard,Please How can I write test generator with Java 7 ? Is there a format I should follow ?
•  » » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   0 Here is the simple generator on Java 7.
 » 5 years ago, # |   0 saw someone using i
•  » » 5 years ago, # ^ |   +1 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.
•  » » » 5 years ago, # ^ |   0 that makes sense, I had no idea they had optimized the compiler so much here
 » 5 years ago, # |   0 Please what is the format for writing a Test generator for Java 7. The output file will be > 1mb. ?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 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
•  » » » 5 years ago, # ^ |   0 Yes you are right.
 » 5 years ago, # |   -14 I don't like a complicated C problem,but a easy d problem. :(
 » 5 years ago, # | ← Rev. 3 →   +20 UPD: hacked Thanks
•  » » 5 years ago, # ^ |   +44 Done.
 » 5 years ago, # |   +23 Is it bug or feature?
•  » » 5 years ago, # ^ |   +11 Russian version of the site says that it's feature. Didn't managed to find analogous information in English one.
•  » » 5 years ago, # ^ |   +18 Wow!
 » 5 years ago, # |   +1 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
•  » » 5 years ago, # ^ |   0 Thanks .
 » 5 years ago, # | ← Rev. 3 →   0 What am I getting wrong here? I get different output for N = M = 1e13 (it matches up to 1e8 or so) from math import sqrt def get_sum(x): return int(x*(x+1)/2) def range_sum(l,r): return get_sum(r) — get_sum(l-1) if __name__ == '__main__': # MOD = 1000000000 + 7 MOD = 1 mod = 1000000000 + 7 MOD = mod N = int(input()) M = int(input()) # N = 10000000000000 # M = 10000000000000 print(N) print(M) minMN = min(N, M) # lim = int(sqrt(minMN)) lim = int(sqrt(N)) # total = (M % MOD )*N % MOD total = M*N reduce = 0 for i in range(1, lim): if i > minMN: break a_pair = int(N / i ) b_pair = int(N / (i+1)) if b_pair+1 <= minMN: this_range = range_sum(b_pair+1, min(a_pair, minMN)) div = i # red = (this_range % MOD * div) % MOD red = int(this_range ) * div reduce += red # reduce %= MOD reduce += int(N/i)*i # % MOD # reduce %= MOD print("Reduce is " + str(reduce)) lim_pair = int(N/lim) for i in range(lim, lim_pair+1): if i > minMN: break reduce += int(N/i) * i # reduce %= MOD print(total % MOD) # total %= MOD print("Total is " + str(total)) print("Getting from " + str(lim) + " to " + str(lim_pair)) print("Reduce is now " + str(reduce)) ans = total - reduce print( (total % MOD) - (reduce % MOD) ) print( ((total % MOD) - (reduce % MOD) ) % MOD) print(ans) print(ans % mod)