### Edvard's blog

By Edvard, history, 4 years ago, translation, ,

Hello, Codeforces!

Educational Codeforces Round 6 will take place on 21 January 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.

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.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

Thanks a lot to Aleksa Plavsic allllekssssa who suggested several problems, two of them you will see on the round (the problems D and F). Also thanks to Bayram Berdiyev Bayram, Allanur Shiriyev Allanur-98, Bekmyrat Atayev Bekmyrat-Atayev. They are together suggested five problems, two of them you will see on the round (the problems B and E).

As usual the round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov we invented the problems A and C together. Also thanks to Maria Belova Delinur who will check English statements and Aleksa Plavsic allllekssssa who help me with problem testing and have constantly been in touch.

The first problem is pretty simple, so I'm waiting fast accepteds from you. The last problem is pretty difficult, so respect to all particiants who will solve it. I hope you will enjoy the problems!

Good luck and have fun!

UPD 1: I forgot to thank all other users who already sent me the ideas for the problems. I'll try to give that problems to the next rounds.

UPD 2: The main part of the contest is finished. The phase of hacks is started.

UPD 3: The editorial is ready.

UPD 4: The round is over, the results is final.

• +258

 » 4 years ago, # |   -11 Good luck && Have fun everyone
 » 4 years ago, # | ← Rev. 2 →   +27 Thanks Edvard for mentioning my friends and me. I'll really tried to give good and interesting tasks for contest. Possible you will see more our tasks in future rounds, that doesn't depend on me :)Enjoy in contest, as always I am glad to hear comments and suggestions after round.
 » 4 years ago, # |   -20 Waiting for tourist with AC on last problem in 10 minutes.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +25 I think no man on the world who can solve last task in 10 minutes :PEDIT: Congratulation to tourist, he is incredible! But I am not counting his solution as regular :P I can promise that he won't solve the hardest task in 10 minutes on my next round ( normally if he works it :D ).
•  » » » 4 years ago, # ^ |   -16 no man can? then which one of the following can?
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +7 tourist isn't a man, he's a SuperMan
•  » » » 4 years ago, # ^ |   +21 Good tactic to invite tourist to contest :)
•  » » » 4 years ago, # ^ |   +14 It took only 7 minutes for tourist to solve the last problem(judging by his submissions)
•  » » 4 years ago, # ^ |   +56 Actually he was able to solve the last one (problem F) in 7 minute .
•  » » » 4 years ago, # ^ |   -12 We don't know it yet. It could be a hackable solution :)
 » 4 years ago, # |   -91 These contests are sucks.
•  » » 4 years ago, # ^ |   +59 You mean this
•  » » » 4 years ago, # ^ |   -31 these socks sucks?
 » 4 years ago, # | ← Rev. 2 →   0 I don't have any hoodies ;(
 » 4 years ago, # | ← Rev. 2 →   -21 I think it is first Turkmen contest.Good luck to everyone!And thanks to contest all problemsetters.
•  » » 4 years ago, # ^ |   -6 Ahahaha minus yagdyrayypdyrlaraooooow. allllekssssa-nam Turkmen edayipsina.
 » 4 years ago, # | ← Rev. 2 →   0 So, D is solvable by binary search right?
•  » » 4 years ago, # ^ |   +19 Maybe you can if instead of wasting time in writing comments , you make the changes :)
•  » » » 4 years ago, # ^ |   0 I am tired. Only the fact that I figured how to solve D kept me going. Now I'm watching youtube :) Commenting takes literally 1-2 minutes.
 » 4 years ago, # |   +7 Am I the only who have passed pretests in B using 7-dimensional array? :D
•  » » 4 years ago, # ^ |   0 This is one solution! But it's complicated :(!
 » 4 years ago, # |   +30 Unfortunately we gave bad constraints to the problem F. As a result some participants solved the problem in O(n2). In spite of this some participants solved the problem with better complexity. The author solution works in time.К сожалению в задаче F мы неудачно поставили ограничения и поэтому некоторые участники сдали решение за O(n2). Несмотря на это среди решений есть решения асимптотически более быстрые, но работающие примерно столько же. Авторское решение работает за .
•  » » 4 years ago, # ^ |   +23 Even author solution runtime does not explain such strange difference between limits on n and m.
•  » » » 4 years ago, # ^ |   +10 Actually the hidden constants for m and n is different.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +9 Sorry, I didn't answer before I had some other obligations.I am setter of fourth and sixth task. The number of good submissions (till now) is great and I think this round is really good for education.. I only suggested tasks, with official solutions, so I didn't decide about final constrains for numbers and time limits. In my version(when I sent task) constrains were :n<=10^5 m<=10^4 Ai<=10^12And my estimation was that 5 seconds enough, but it is changed. Edvard is better programmer with more experience, so I beleive in his decision (and possible it is better to have more correct submissions — 8 good solutions in two hour aren't a lot of).I hope you enjoyed in tasks and spent 2 great hours. See you on some other round, any suggestion and opinion about tasks will be helpful.
•  » » 4 years ago, # ^ |   0 Так вот как её за 7 минут сдавать. Обидно :(
•  » » » 4 years ago, # ^ |   -13 Да мы тоже сильно расстроились. Мы рассмотрели такую возможность, но у меня было другое наивное решение и как раз его я смог завалить такими ограничениями.
 » 4 years ago, # |   0 Nice contest overall! Russian statements was very clear, except maybe a bit lack of comments on math, like that (+) operation in F is XOR :) I know that, but I also know a lot of people who wouldn't figure out what operation it is. And they can't google for it I guess — hard to write search engine request.The only flaw I see is difficulty gap between C and DEF. But it is probably very personal thing.
•  » » 4 years ago, # ^ |   +31 Problem title can help with this
•  » » » 4 years ago, # ^ |   0 Haha, nice. Well I haven't read problem title until this moment :DAnyway, I'm kinda used to get such comments in statement, because they are often presented in regular contests (even easily googled ones like what is tree, what is subtree, etc).
•  » » » » 4 years ago, # ^ |   +5 I actually get to the clarification writing interface just to be sure, but when I selected problem I had to read the title
 » 4 years ago, # | ← Rev. 2 →   +16 Everyone is trying so hard to hack tourist on problem A. well , my friendly advice to those desperate souls: "let it go, my fellow coders. Sad but truth is tourist can solve easy problems too beside hard ones"
 » 4 years ago, # |   0 I think i could not understand problem C properly. In the test case 5 2 2 3 3 3 will 3-5 be a good segment? if yes, then can a good segment contain more than two pearls of same kind, also two pearls each of two different kind?
•  » » 4 years ago, # ^ |   0 Yes, and yes, and yes.
•  » » » 4 years ago, # ^ |   0 uhh i totally misunderstood the question. Got it accepted easily now. thanks!
 » 4 years ago, # |   +1 Will the editorial be post after the end of hacking phase?
 » 4 years ago, # |   0 how to solve D?
•  » » 4 years ago, # ^ |   +3 I used the fact that after 1 change, answer is the minimum of absolute value of sumA-sumB-2*a[i]+2*b[i] to use binary search on b[] for closest value to (sumA-sumB-2*a[i])/2. Similarly, for making 2 swaps, you can make to arrays c[] and d[] where c has sum of pairs of elements of a[], and d has sum of pairs of b[]. Then, for each element in c[], binary search in d[]. This step has complexity n^2 log(m^2)
•  » » » 4 years ago, # ^ |   +3 Tried similar thing, looks like tle on test 13: http://codeforces.com/contest/620/submission/15485606
•  » » » » 4 years ago, # ^ |   +3 me too, and i don't know why...
•  » » » » » 4 years ago, # ^ |   0 I just read editorial. Instead of storing pairs for both arrays in a map, just store for one and directly use the other from the loop. This leads to AC now
•  » » » » 4 years ago, # ^ |   0 Maybe map has huge constants. Why not use a static array of size n^2 ?
•  » » 4 years ago, # ^ |   +3
•  » » » 4 years ago, # ^ |   +3 Hmm, my approach seems correct :)
 » 4 years ago, # |   0 The second problem is very annoying. Otherwise very good and interesting problemset.
•  » » 4 years ago, # ^ |   +1 I like how you wrote while (x) ans += ar[x%10], x /= 10; Didn't knew we could do that!
 » 4 years ago, # | ← Rev. 2 →   +16 Hm, interesting. I've submitted two AC solutions to D. Second one was a bit more optimized. And now first one got hacked. And I got penalty as if I made one WA submission before.Feels fair, but didn't expected such thing :)So basically I can submit as many AC as I want, and the first one which won't be hacked will be considered as accepted solution, right? And how about hacked ones? Will I get penalty for every one or how else it works?
 » 4 years ago, # |   0 In problem E , Why am I getting a RTE on test 51 . I am using Segment Tree on Time Stamps 15485066 Moreover what is the stack limit on Code Forces? Might be recursion is causing stack overflow ..
•  » » 4 years ago, # ^ |   0 I got that problem too. You might use 2d arrays for the trees (i guess). Try using 1d arrays. I tried then time limited :D
 » 4 years ago, # | ← Rev. 2 →   +6 During the contest i solved B casting every integer in the range [a, b] into a string (using std::to_string()) and then iterating the string with a range based for, and I got TLE (code here).Then I removed the std::string conversion and did the same thing extracting every digit from the number, using the same complexity [ O(b — a) ], and got AC in 15 ms (code here).Now on my pc the first solution, with the 1 1000000 tc, works in 130ms while the second one takes 40ms (I haven't got any kind of supercomputer or quantum computer and I compile with the same flags of Codeforces (C++11)). Now the question is: does codeforces hate std::string? is std::to_string() very very slow?I got 3 TLEs for this :(
 » 4 years ago, # |   +36 I wish to say few more things about tasks and whole contest till now.First I hope you find something interesting in problemset or at least you don't hate tasks :)This was my help to codeforces, I do this only because of the passion for programming ( and I don't have girlfriend to spend time on it :D ). I hope to see your problems on the following educational rounds, Edvard is great guy he finished good part of preparation and certainly he would help to new problemsetters. Also I'm always here for any help and question for anything needed.
•  » » 4 years ago, # ^ |   +3 I liked the contest, F was a though one :)
 » 4 years ago, # |   +14 In problem C: a submission with unordered_map fails with TL: 15496737 a submission with map gets AC (only one line of code changed!): 15496747 a submission with unordered_map and custom hash function: AC again! 15497036. Bit slower compared to map, anyway. What exactly is test 42? Looks like someone went through the trouble to generated an extremely bad test case input that causes huge number of collisions in that specific G++ implementation of unordered map. In my opinion, it's a bit against the spirit of the competition ;)
•  » » 4 years ago, # ^ |   +11 Against the spirit of the competition? Come on, it's just an unrated competition and also it's called an educational round ;) how so?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Hi kfx and sgtlaugh,Can you please explain how having huge number of collisions give TLE? Shouldn't it give a Wrong Answer instead? And also can you please explain how would one generate such a test case programmatically.(My solution also got hacked due to the same reason)Thanks a lot! :)
 » 4 years ago, # | ← Rev. 5 →   0 Now when the hacking is finished I want to ask something. On the A problem I found a solution with O(n) complexity, e.g. there was iterating from 10^9 to -10^9. I tried to hack it using x1=10^9 and x2=-10^9 and the hacking attempt was unsuccessful. However, on my laptop it run more than 2s and the limit is 0.5s. Is the limit actually higher or am I missing something?Thanks.
•  » » 4 years ago, # ^ |   0 Codeforces servers are very fast. Did you compile with optimization options like -o2 etc.?
•  » » » 4 years ago, # ^ |   0 No, I didn't. Is there some page where we may read the specifications of the Codeforces server?
 » 4 years ago, # |   -27 The problems are the ball, I am Ronaldo!
•  » » 4 years ago, # ^ |   -27 Does it mean that they are easy for you?
•  » » » 4 years ago, # ^ |   -27 Yes, exactly!