Educational Codeforces Round 22
By BledDest, history, 7 years ago, translation, In English

Hello Codeforces!

On June 05, 18:05 MSK Educational Codeforces Round 22 will start.

Series of Educational Rounds continue being held as Harbour.Space university initiative! You can read the details about the cooperation between Harbour.Space and Codeforces in the blog post.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them. We tried to design the problems in such a way that both beginners and experienced programmers can find something interesting in the contest.

The problems were prepared by Mikhail awoo Piklyaev, Vladimir vovuh Petrov and me. Huge thanks to Maxim HellKitsune Finutin and Alexey ashmelev Shmelev for testing the contest!

Good luck to all participants!

UPD: The editorial is published.

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

Comments Comments (78)
| Write comment?
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Hi every one.... is there any way to search problems by their tags? thanks

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

I'm new to codeforces and this is my first educational round! Excited! :P

→ Reply
»
7 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Too few comments! Isn't it weird?

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

Why is E not an interactive problem?

→ Reply
»
7 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Can someone solve me B?I have idea but can't implement.

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

    You can find all unlucky years in log(r)^2, then just sort them and find maximum length between all pairs of neighbours in sorted array. Also check for segments starting in l, and ending in r.

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

Stop killing the cute MO solutions xD.

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

How to solve F ?

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

    for each edge find when its in the graph, after that something like this

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

I should have copied my Persistent IT code instead of trying to re-invent it...

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

    Which problem did you plan to use Persistent IT on ?

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

      E. I thought I had to have extra O(sqrt(n)) complexity, so I thought I had to use persistent IT. Only realized it at the last minutes and it's too late.

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

    You can use SQRT decomposition to answer the queries rather than using complicated Persistent IT

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

      Persistent IT is not very complicated, in my opinion some SQRT methods are more tedious to implement.

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

    What is IT ? Interval Tree ?

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

Nice problems! What were your solutions for C?

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

    Calculate all the distances from Alice and Bob, and find the node where the distance from Alice is maximum and greater than the one from bob, multiply that distance by 2 to get the number of moves.

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

      why this solution is right ? can you give more details why we should do another dfs where from the position bob stands thanks in advance

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

        The best strategy for Alice is to always go down in the tree. Bob wants to survive for as long as possible so his best strategy is to go to the furthest node from Alice. As explained in the editorial, Bob needs to go up in the tree (by 0 or more nodes) to reach the branch that leads to the furthest node. Sometimes this cannot be achieved since Alice will be there before Bob. That's why you need to check both distances.
        I hope this helps. :)

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

    Notice that Alice will walk down the tree to wherever Bob is, and that the number of steps it will take is just the depth of that path in the tree. That means that Bob should try to get to a node that has the greatest depth.

    If the root node is at level 0, and Bob's node is a level x, the Bob can walk up at most nodes up before choosing to go down the path that has the greatest depth. We can find the depths of the paths using a dfs.

    My Submission: 27589077

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

Any hints on how to solve E?

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

    Solve SPOJ problem DQUERY first, online using persistent segment trees.

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

    For each i, compute bi the position of k - th number that equal to ai to the right (if there's no such position, bi = n + 1), then for each query, count from l to r how many number greater than r.

    PS: My solution

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

pls make a div1 contest :'(

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

when will we be able to hack???

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

How to solve problem-B?

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

    Find out all the possible value of x^a + y^b and then fond the max range between l and r.

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

Could one hack it :)

It failed :(

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

can some one tell me the answer for the following test case for problem C 16 12 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 3 11 11 12 12 13 13 14 14 15 15 16

i think the answer is 14. but seems its wrong please help!

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

    You can copy the code of a couple of high-rating coders, run this case and, if their answer is the same, it is very likely that they are correct. My program outputs 16, but it might have a bug.

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

    Answer is 16. Bob will walk down to node 16 and wait there. It will take Alice 8 moves to get there, so the total number of moves is 2 * 8 = 16.

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

    The answer is 16 according to my code.

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

Nice problems, Why the rated rounds are not like this round? :"D

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

Can anyone give me a simplified version of test 8 in problem C?

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

    Something like:

    5 3
1 2
2 3
2 4
4 5

    Answer should be 4.

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

      When you realized that you at got WA because of 2 character in the code...

      (Change db[u] < da[v] to db[u]+1 < da[v])

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

    I also got WA at test 8. I found one possible test case below.

    10 2 7 1 8 2 1 3 10 4 7 5 3 6 5 8 6 9 7 10

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

FeelsBadMan

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

    FeelsBadMan

    (Got E accepted 10 minutes after the contest).

    PS: Btw, is there a fast way to insert image from computer?

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

Had any One Solve problem C using dp ?!

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

    I think it was a simple greedy type solution,using DP probably wont help at all,also the constraint were not DP type,I may be wrong though..

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

I am getting WA on problem C for a case which is not valid and the case is also showing valid for hack input. But in the problem it is stated that "Bob starts at vertex x (x ≠ 1)." But in this case x = 1. Please check it.

Here is my code: 27597100

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

    yes same problem.

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

    Sorry, this test is removed now. It was added after contest ended but it was wrong.

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

Is there any way to get the hacking tests so that I can verify my solutions?

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

    It was possible if u resubmit until education round 19/20. Now not possible

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

      All unique hacking tests are added to testset after the end of hacking phase. It holds for every round.

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

Any idea how to solve D?

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

I got a wrong evaluation from Codeforces on Problem B. After the contest, When i checked the test case where i got Wrong answer. The output computed by Codeforces was wrong. I was getting a different output (the correct one) on all the other IDEs. Kindly look into this. 27593531 [Test #10]

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

    I submitted your code using GNU C++11, and it was accepted. I don't use C++ normally so I'm not sure why. I hope this helps you discover the problem.

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

      Thanks. Thats certainly a bug then. Because, whatever gets executed in C++11 can get executed in C++14 in the very same manner.

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

can some one help me with this? There is an array of integers,we need to answer queries in this form. given L,R and A,B need to count number of numbers in range [A,B] in the subarray [L,R].each query should be solved in logn time.what is the best datastructure to use here?

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

    Segment Tree.

    (AFAIK) You can get log(n) time per query with offline processing and segment tree. See SPOJ KQUERY problem for reference. (not giving details as you asked only the name of the data structure :P)

    You can do it easily with merge sort tree, a variation of segment tree, but time per query there will be (log(n))^2

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

      In the problem KQUERY we put all the queries and the array elements and sort it.Then we process each element.if it is an array element we update the segment tree, if it is a query we find numbers in range [L,R].here we are exploiting the fact that all the numbers(elements) which came before A query are greater than k.But in my question the numbers should be in a range between [A,B].so how do we do that using offline approach? On the other hand the merge sort tree approach seems good.

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

        Simple. Answer for range [A,B] = number of elements larger than A — number of elements larger than (B+1).

        So, for each range [A, B], you can find answer with 2 queries. kquery(L, R, A) — kquery(L, R, B+1) where kquery(x, y, z) returns number of elements greater than z in the subarray [x, y].

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

Some of the successful hacks for problem C had incorrect tests in it (there was a bug in validator).

We are really sorry about the issue! These hacks are now rolled back, all the solutions which were hacked now seem to be accepted.

We should have worked harder on checking the correctness of all the checkers, validators and solutions. We will do our best to avoid further contests to have such major issues.

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

The editorial is published.

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

What's the recommended order for solving problems in a contest? Do we start with the easiest problem A first or is there a smarter strategy?

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

    Start with the easier ones first. You anyway have to do them at some point in the contest. So why not to finish them up asap and then devote your time in the tougher questions.

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

Test case 5 of prob D:

10

9 6 8 5 5 2 8 9 2 2

Answer given is 9. But shldn't it be 10? {6,5,5} forming one subsequence and rest all nums for the other.

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

    The rest will be {9, 8, 2, ...} and you can't take 2 after 8.

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

      Ok got it thanks... i thought differ by 1 meant in terms of mod 7

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

      WHat is the simplified version of test case 10 of problem C ? awoo

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

        No idea. It's just a random tree.

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

I try to hack and all the website says is this: http://i.imgur.com/aoSKkAM.png

Anything I Should do?

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

    Happens to me a lot too, I just refresh the page over and over until it works lol

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

Please ignore this. Doubt was resolved.

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

F isn't original. In fact, I've used the same idea in a contest in our school around three years ago. Also, it can be solved by link/cut tree in time, which is better than the solution in the editorial.

But since it's an Educational round I don't think the tasks have to be original. I've seen other tasks in ECR that are obviously not original as well.

My code can be found here. You can see my poor coding style back then(therefore I had lots of trouble getting the input format fitted, even though there's only a little to be modified).

→ Reply