### Edvard's blog

By Edvard, history, 5 years ago, translation,

Hi, Codeforces!

Educational Codeforces Round 4 will take place on 25 December 2015 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here. This time a little time has passed since the previous round. Although we planned this round at Monday, we forgot to include it to schedule, so it was appeared only now. So it is the fourth and the last educational round this year.

<Maybe this paragraph will not be changed ever>

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.

</Maybe this paragraph will not be changed ever>

This time the round was prepared only 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, when they will be ready :-)

I think this time the problems is simpler than usually, because at first we have too hard problemset and removed the hardest problem and added very simple problem. I hope you will enjoy the problems and solve all of them!

Also I want to wish you Happy New Year!!!

Good luck and have fun!

UPD 1: The first phase is ended, hack the solutions of your opponents!

UPD 2: The editorial is ready.

• +245

 » 5 years ago, # |   +11 Merry Christmas, friends!
 » 5 years ago, # | ← Rev. 2 →   -12 I think that Tests on the first day must be weaker to Increase the number of hacks... Last Educational Round had strong tests on first day...
•  » » 5 years ago, # ^ |   -16 I agree
•  » » 5 years ago, # ^ |   -16 number of hacks should be increase by weaker pretest.
•  » » 5 years ago, # ^ |   -12 correct
•  » » 5 years ago, # ^ | ← Rev. 2 →   +7 I think that hacking on educational rounds is meant to strengthen the test data, not to test your abilities with hacking. Otherwise the test data would have been called pretests.
 » 5 years ago, # | ← Rev. 2 →   0 I love the end of the year because it is full of contests :D
•  » » 5 years ago, # ^ |   -10 >end of the year>only because full of contests>sees usernameAlright, checks out.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 my friend annoying me.. :| sorry
•  » » » 5 years ago, # ^ |   +1 I didn't mean it to be offensive by the way :3
 » 5 years ago, # |   +14 happy new year!!!!! best wishes for you!!!! :D
 » 5 years ago, # |   +22 me at cf educational round
 » 5 years ago, # |   +21 ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ HAPPY NEW YEAR !!!!!!!!!!!!!!!!
 » 5 years ago, # | ← Rev. 2 →   +70 My whole life.*Christmas. I know, ok? :D
•  » » 5 years ago, # ^ |   +7
 » 5 years ago, # |   +3 Happy Halloween and Happy Solving!
•  » » 5 years ago, # ^ |   +63 Are you on internet explorer?
 » 5 years ago, # |   0 My first year of experience on codeforces.. the most lovely site ever ^_^
 » 5 years ago, # |   0 I am happy because Christmas on the way
 » 5 years ago, # |   -7
 » 5 years ago, # |   0 These Educational Rounds contain almost everything that I reminded myself to learn someday, but actually never did ! :D
 » 5 years ago, # |   +1 Problem A : WA on test 9 :(
 » 5 years ago, # |   +6 Very poor English.
•  » » 5 years ago, # ^ |   0 That's because ... Any Test Answer can Contain Several portion of both length i.e. P & Q
 » 5 years ago, # |   +10 I think problem B is easier than problem A .
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 Imo, its not easier to implement, but its easier to understand statement :)UPD: Actually, after checking my code, it seems B is easier in implementation too...
 » 5 years ago, # |   0 How is problem C solved? I think checking whether a given string is "good" is easy, but I was stumped with the actual problem.
•  » » 5 years ago, # ^ |   +3 just useing stack
•  » » 5 years ago, # ^ |   +3 It's just as easy. You can never change opening brackets and only change closing brackets to make them match. Then you just go as the regular check with a stack, if you get an opening bracket you push it in the stack, if you get a closing bracket you pop the top of the stack. If the closing bracket doesn't match the top of the stack then you increase your changes by 1.
•  » » » 5 years ago, # ^ |   0 Why is the answer of [{>} not 1?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +6 because [ { ] } is not an RBS . check the definition of an RBS in the problem statement .
•  » » » » » 5 years ago, # ^ |   +3 OMG thats tragic... :( Can't believe I missed this.
•  » » 5 years ago, # ^ |   0 Just being greedy. Since you can't make a bracket type correct string out of a bracket type mismatch string (with the limits in statement), the only thing you can do is fix the bracket kind mismatch. The absolutely correct ones shouldn't change, or you'll make the answer worse. As for the kind mismatch pairs, fix any one of them, that will work.
 » 5 years ago, # |   +8 I didn't notice that the round will start at 18:00 instead of 18:05 so I missed the first five minutes.
•  » » 5 years ago, # ^ |   +7 Well it's unrated and educational so 5 minutes shouldn't matter.
•  » » » 5 years ago, # ^ |   +5 yes, I'm just saying that it's better to mention that there's no +5 in the announcement next times
•  » » » » 5 years ago, # ^ |   +14 Each email has exact time when contest will start. Also there is countdown in sidebar and contests page.ICPC-style contests do not have rooms, so we do not need 5 minutes for delay between end of registration and contest start.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I don't rely on emails, and for the countdown I only used it to compute start hour but not the exact time, that's what happened with me.I'm not complaining since it's not big deal, I was just saying that such things might happen so in the future if you decided not to make the +5 delay in the rated rounds it's better to mention that in the announcement.
•  » » » » » » 5 years ago, # ^ |   +12 Codeforces team introduced contest time in local timezone. No more complaints :D
•  » » 5 years ago, # ^ |   0 I know that feel
 » 5 years ago, # |   0 Editorial will be available today or after hacks phase?
•  » » 5 years ago, # ^ |   0 It will be today.
•  » » 5 years ago, # ^ |   0 Russian editorial is already available here
 » 5 years ago, # |   +1 Any hints for E?
•  » » 5 years ago, # ^ |   0 D and E were completely new to me ... hints about D too would be appreciated
•  » » » 5 years ago, # ^ |   +1 D was somewhat simple. Just do a line sweep from right to left.
•  » » » » 5 years ago, # ^ |   0 The whole time i was thinking of a way to solve with segment tree, i think it's about time i read up on line sweep.. thank you
•  » » 5 years ago, # ^ |   0 Hint: convert a permutation into a graph or a cycle notation. (For example, if you have [1 3 2], write a graph with edges from 1 to 1, from 2 to 3, from 3 to 2) and before thinking about how to find a square root of permutation, observe what happens when you square a permutation. Another hint: it has something to do with the parity of the length.
 » 5 years ago, # |   0 It's possible to hack problems A B C? I mean it is possible to find test to hack? There was easy problems
 » 5 years ago, # | ← Rev. 2 →   0 How to solve problem E ?
•  » » 5 years ago, # ^ |   0 Consider some permutation q. Let's build by it the oriented graph with edges (i, qi). Easy to see (and easy to prove) that this graph is the set of disjoint cycles. Now let's see what would be with that graph when the permutation will be multiplied by itself: all the cycles of odd length would remain so (only the order of vertices will change, they will be alternated), but the cycles of even length will be split to the two cycles of the same length. So to get the square root from the permutation we should simply alternate (in reverse order) all cycles of the odd length, and group all the cycles of the same even length to pairs and merge cycles in each pair. If it's impossible to group all even cycles to pairs then the answer doesn't exist.Complexity: O(n).
 » 5 years ago, # | ← Rev. 4 →   +5 Edit: I was wrong, I am sorry if I have misleaded any of you.
 » 5 years ago, # |   0 My solution to problem D has the max complexity at sort but still get TLE test 19. 15018905 Is that because the memory is too large or sort sometimes can reach O(n^2) ? Can anyone help me ?
•  » » 5 years ago, # ^ |   +3 It's not the problem of sort(), it's the problem of your I/O method.Using cin/cout will lead to a dramatically long excution time when facing such huge test cases. scanf/printf is strongly recommanded here.15019648I made a change on your I/O method, and it's now WA on test 19 with ~600ms. Hope you can figure the problem out.
•  » » » 5 years ago, # ^ |   0 Thank you so much, I didn't know using cin/cout would slow down the program so much :((
•  » » 5 years ago, # ^ |   0 I also got TLE, on the same test case, see 15016054, i did it in Java. I noticed that Egor has custom input and output streams. How can i set these up with IntelliJ, CHelper plugin?
 » 5 years ago, # | ← Rev. 2 →   0 Can someone help me with D?Current idea that gave WA#20: if segment is given as (L, R), put (L, 0) to vector and (R, 1) as well. Then sort, and check when interval is opened and when is closed. Meanwhile checking if total number of opened intervals is >=k.UPD: I found out mistake.
•  » » 5 years ago, # ^ |   0 Was your implementation buggy or the algo?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +4 The algo passes the preliminary test cases. I used the same idea.
•  » » » » 5 years ago, # ^ |   0 I missed endpoints where segments == k
•  » » » 5 years ago, # ^ |   0 I checked =k instead of >= k
 » 5 years ago, # |   0 happy new year！ Although I am a Chinese.
 » 5 years ago, # |   0 good if the Educational round had (div.1) and (div.2) :-)
 » 5 years ago, # | ← Rev. 4 →   0 Maybe 3 hours will be better?
 » 5 years ago, # |   +4 Damn, get the idea in D, spent 1.5 hours implementing it and finished 5 mins before the end with correct algo, but TL.Contest over, got totally different idea and now it is AC. Spent 20 mins.Aggrhhh! First one was too complicated so I can't evaluate complexity for it, but felt like "good enough". Second one was obvious O(N * log(N)).
•  » » 5 years ago, # ^ |   0 BTW, got hacked with my new solution because of not perfect I/O. Fixed now :)
•  » » 5 years ago, # ^ |   0 mine was even worse .I thought towards the middle of the contest that I would not be able to do D so took a break.While there were 20 minutes left I came back and thought over the question for a while.An idea struck me 10 minutes prior to end of the contest and I frantically coded this and submitted with 40 odd seconds left .Result WA on case 1 (there was no time to run on local system). I was debugging the solution half an hour back and here is the correct one. If you compare the codes you'll see that there is a difference of a single character. I wrote '=' instead of '==' in an if condition.**FACEPALM**
 » 5 years ago, # |   +13 I don't know why some members like to enter the contest virtually and submit prepared solutions one after another just to get high rank. It is not competitive anyway.
•  » » 5 years ago, # ^ |   +1 What's even worse is that sometimes the solutions submitted are not even theirs.
•  » » » 5 years ago, # ^ |   +5 What's even worse is that some people add a false special test in their code and try to hack it later .really people !!
•  » » » » 5 years ago, # ^ |   0 mind=blown
 » 5 years ago, # | ← Rev. 2 →   0 I have a question about the problem D. For this test case: 2 1 1 3 3 5  The answer is 1 1 5  How so, if the point 3 is located on the two segments?
•  » » 5 years ago, # ^ |   +3 The acceptable condition is ">= k", not "== k".
•  » » » 5 years ago, # ^ |   +3 My bad, forgot about that. Must be because of the pressure from the possibility of my solution getting hacked. :P
 » 5 years ago, # |   0 For problem D, I used compression, but TLE on test #16, can anyone explain why? Code
•  » » 5 years ago, # ^ |   +3 I believe your solution is of complexity O(N^2), even after compression.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Can you point out that mistake please?
•  » » » » 5 years ago, # ^ |   0 I believe its just wrong approach. You have O(N^2) complexity when filling axis array — every segment could have the length of N. So with N segments, each one length of N you will get O(N^2) right away.
•  » » » » 5 years ago, # ^ |   0 Your algorithm is correct (I think) but it's too slow.  for(int c=0;c
•  » » » » » 5 years ago, # ^ |   0 that's right, I was so stupid. Thanks for replying :)
 » 5 years ago, # |   +4 Can anybody explain why this 15030396 got TLE, while this exactly same code 15030456 got AC?
•  » » 5 years ago, # ^ |   0 I guess its because software execution time isn't very precise value :) Just improve your code to execute 2-3 times faster and it should be ok.
 » 5 years ago, # |   +4 I would like to report a possible bug. If I go to standings -> div 2 and then click "friends standings" it doesn't do anything.
 » 5 years ago, # |   0 Is system testing planned? I thought it starts automatically once hacking phase is finished.
•  » » 5 years ago, # ^ |   +9 Done, great and terrible hacker.
»
5 years ago, # |
+3

The contest has been rejudged with all the successful hacks. Аpplause to the best hackers!

Hacker Hacks
halyavin 62
SlavaSSU 26
anhhungcolao 12
Alex_2oo8 10
alex256 9
•  » » 5 years ago, # ^ |   +3 I think here is a little bug, but I may be mistaking. After choosing "Division 2" I cannot get back to the standings for Both divisions. Also, as already mentioned, if one chooses "Division 1" or "Division 2", then clicking on "Friends standings" shows the "Common standings".
 » 5 years ago, # |   0 Thumbs up to "recursionishell" test in problem A created by alex256. Too bad it is not the first test where recursion solution will fail.