Edvard's blog

Educational Codeforces Round 4
By Edvard, history, 9 years ago, translation, In English

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.

  • Vote: I like it
  • +245
  • Vote: I do not like it

Comments Comments (79)
| Write comment?
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Merry Christmas, friends!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    number of hacks should be increase by weaker pretest.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    correct

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

At codeforces educational round

me at cf educational round

→ Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░████████░███░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░█████████░░███░░░░░░░░░░░░░░ ░░░░░░░░░░░░░███████████░░░██░░░░░░░░░░░░░ ░░░░░░░░░░░░██████████░░░░░░██░░░░░░░░░░░░ ░░░░░░░░░░██████████░░░░░░░░░██░░░░░░░░░░░ ░░░░░░░░░░█████████░░░░░░░░░░░██░░░░░░░░░░ ░░░░░░░░░█████░░░░░░░░░░░░░░░░░██░░░░░░░░░ ░░░░░░░░████████░░░░░░░░░█████░██░░░░░░░░░ ░░░░░░░░░░░███████████████████░░░░░░░░░░░░ ░░░░░░░░░░░████████████████████░░░░░░░░░░░ ░░░░░░░░░░██████████████████████░░░░░░░░░░ ░░░░░░░░░████████████████████░░██░░░░░░░░░ ░░░░░░░░████████████████████░░░░██░░░░░░░░ ░░░░░░░████████████████░░░░░░░░░░██░░░░░░░ ░░░░░░████████████░░░░░░░░░░░░░░░░██░░░░░░ ░░░░░████░░██░░░░░░░░░░░░░░░░░░░░░░██░░░░░ ░░░░███████░░░░░░█████░░░░░░█████████░░░░░ ░░░░██░░████████████████████████░░░░░░░░░░ ░░░░░░░█████████████████████░░░██░░░░░░░░░ ░░░░░░███████████████████░████░░░██░░░░░░░ ░░░░██████████████████████░░░░░░░░░██░░░░░ ░░██████████████████████░░░░░░░░░░░░███░░░ ░███████████████░█░░░░░░░░░░░░░░░░░░░░██░░ █████████░█░░░░░░░░░░░░░░░░░░░░░░░███████░ ░░░░░░░███░░░░░░░███████░░░░░░██████░░░░░░ ░░░░░░░░███████████████████████████░░░░░░░ ░░░░░░███████████████████████████░██░░░░░░ ░░░░██████████████████████████████░███░░░░ ░░░█████████████████████████████░░░░░██░░░ ░░█████████████████████████░░░░░░░░░░░██░░ ░█████████████████████░█░░░░░░░░░░░░░░░██░ █████████████████░█░░░░░░░░░░░░░░░░░░░████ ░░░░░███████████░░░░░░░░███░░░░████████░░░ ░░░░░░░░░░░░░░░░███░█████░█████░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░██████░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░█████░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████░░░█░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░░░░░░██░░██░░░░██░░██░░██░░░░░░░░░░░ ░░░░░░███████░░██░░░░██░░██░░███████░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░██░░░░░░░██░░░░██░░██░░██░░░██░░░░░░ ░░░░░░███████░░████████░░██░░███████░░░░░░ ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
HAPPY NEW YEAR !!!!!!!!!!!!!!!!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +70 Vote: I do not like it

My whole life.

*Christmas. I know, ok? :D

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Happy Halloween and Happy Solving!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am happy because Christmas on the way

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem A : WA on test 9 :(

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Very poor English.

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think problem B is easier than problem A .

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is problem C solved? I think checking whether a given string is "good" is easy, but I was stumped with the actual problem.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    just useing stack

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +6 Vote: I do not like it

        because [ { ] } is not an RBS .

        check the definition of an RBS in the problem statement .

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +12 Vote: I do not like it

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

            → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know that feel

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial will be available today or after hacks phase?

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any hints for E?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve problem E ?

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

Edit: I was wrong, I am sorry if I have misleaded any of you.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Maybe 3 hours will be better?

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      really people !!

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you point out that mistake please?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

            for(int c=0;c<n;c++)
    {
        i=arr[c].first;
        j=arr[c].second;
        i=mp[i];
        j=mp[j];
        for(int k=i;k<=j;k++)
            axis[k]++;
    }

        There you iterate over every segment, even after compression segments have length (in the worst case) of 2n, so that part of your code is O(n2), with n = 106 it's too slow

        → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

Hacker Hacks
halyavin 62
SlavaSSU 26
ahcl 12
Alex_2oo8 10
gepardo 9
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply