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.

Merry Christmas, friends!

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

I agree

number of hacks should be increase by weaker pretest.

correct

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.

I love the end of the year because it is full of contests :D

>end of the year

>only because full of contests

>sees username

Alright, checks out.

my friend annoying me.. :| sorry

I didn't mean it to be offensive by the way :3

happy new year!!!!! best wishes for you!!!! :D

me at cf educational round

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░

HAPPY NEW YEAR !!!!!!!!!!!!!!!!

My whole life.

*Christmas. I know, ok? :D

Chrismas?

Happy Halloween and Happy Solving!

Are you on internet explorer?

My first year of experience on codeforces.. the most lovely site ever ^_^

I am happy because Christmas on the way

These Educational Rounds contain almost everything that I reminded myself to learn someday, but actually never did ! :D

Problem A : WA on test 9 :(

Very poor English.

That's because ... Any Test Answer can Contain Several portion of both length i.e. P & Q

I think problem B is easier than problem A .

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...How is problem C solved? I think checking whether a given string is "good" is easy, but I was stumped with the actual problem.

just useing stack

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.

Why is the answer of [{>} not 1?

because [ { ] } is not an RBS .

check the definition of an RBS in the problem statement .

OMG thats tragic... :( Can't believe I missed this.

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.

I didn't notice that the round will start at 18:00 instead of 18:05 so I missed the first five minutes.

Well it's unrated and educational so 5 minutes shouldn't matter.

yes, I'm just saying that it's better to mention that there's no +5 in the announcement next times

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.

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.

Codeforces team introduced contest time in local timezone. No more complaints :D

I know that feel

Editorial will be available today or after hacks phase?

It will be today.

Russian editorial is already available here

Any hints for E?

D and E were completely new to me ... hints about D too would be appreciated

D was somewhat simple. Just do a line sweep from right to left.

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

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.

It's possible to hack problems A B C? I mean it is possible to find test to hack? There was easy problems

How to solve problem E ?

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

Edit: I was wrong, I am sorry if I have misleaded any of you.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 ?

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.

15019648

I 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.

Thank you so much, I didn't know using cin/cout would slow down the program so much :((

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?

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.Was your implementation buggy or the algo?

The algo passes the preliminary test cases. I used the same idea.

I missed endpoints where segments == k

I checked =k instead of >= k

happy new year！ Although I am a Chinese.

good if the Educational round had (div.1) and (div.2) :-)

Maybe 3 hours will be better?

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

BTW, got hacked with my new solution because of not perfect I/O. Fixed now :)

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**

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.

What's even worse is that sometimes the solutions submitted are not even theirs.

What's even worse is that some people add a false special test in their code and try to hack it later .

really people !!

mind=blown

I have a question about the problem D.

For this test case:

The answer is

How so, if the point 3 is located on the two segments?

The acceptable condition is ">= k", not "== k".

My bad, forgot about that. Must be because of the pressure from the possibility of my solution getting hacked. :P

For problem D, I used compression, but TLE on test #16, can anyone explain why?

Code

I believe your solution is of complexity O(N^2), even after compression.

Can you point out that mistake please?

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.

Your algorithm is correct (I think) but it's too slow.

There you iterate over every segment, even after compression segments have length (in the worst case) of 2

n, so that part of your code isO(n^{2}), withn= 10^{6}it's too slowthat's right, I was so stupid. Thanks for replying :)

Can anybody explain why this 15030396 got TLE, while this exactly same code 15030456 got AC?

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.

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.

Is system testing planned? I thought it starts automatically once hacking phase is finished.

Done, great and terrible hacker.

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

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".

Thumbs up to "recursionishell" test in problem A created by gepardo. Too bad it is not the first test where recursion solution will fail.