By BledDest, history, 4 months 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 PikMike Piklyaev, Vladimir 0n25 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  

»
4 months 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

»
4 months 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

»
4 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Too few comments! Isn't it weird?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is E not an interactive problem?

»
4 months ago, # |
  Vote: I like it -19 Vote: I do not like it

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

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Stop killing the cute MO solutions xD.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?

  • »
    »
    4 months 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

»
4 months 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...

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which problem did you plan to use Persistent IT on ?

    • »
      »
      »
      4 months 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.

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is IT ? Interval Tree ?

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice problems! What were your solutions for C?

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But that won't work for all cases right? For your solution to be correct you must ensure that Alice won't reach Bob on all nodes in the path...rt?

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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. :)

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thanks, now i understand it , thank you for your detailed explain !!

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Any hints on how to solve E?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it +60 Vote: I do not like it

pls make a div1 contest :'(

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

when will we be able to hack???

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve problem-B?

  • »
    »
    4 months 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.

»
4 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

Could one hack it :)

It failed :(

»
4 months 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!

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The answer is 16 according to my code.

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A small doubt-: For problem B, test-case 13 is 14 2 732028847861235713 732028847861235713 if both the start and end years are same and my computation gives it as unlucky no, won't the ans be 0? Or is my computation of unlucky nos wrong?

»
4 months 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?

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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])

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it

FeelsBadMan

  • »
    »
    4 months 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?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Had any One Solve problem C using dp ?!

  • »
    »
    4 months 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..

»
4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    yes same problem.

  • »
    »
    4 months 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.

»
4 months 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?

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any idea how to solve D?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Spoiler
»
4 months 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]

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

»
4 months 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?

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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].

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          got it :D.Thanks for your time.love this community

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Now you seem happy after asking question from live contest.

            Cheater

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              well it is not the exact same question,I simplified it a lot and dont tell me you came up with the working of segment trees on your own.you had to learn it somewhere right? Long contests are meant to make you learn about new data structures and algorithms.I could have googled it anyway and got the same results.but i asked here to know different possible solutions and efficient ones.A lot of people copy paste some hard datastructures form internet.do you consider that cheating?I dont consider this cheating, it is a learning process

»
4 months 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.

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

The editorial is published.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Lots of hacks in problem B ..

»
4 months 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?

  • »
    »
    4 months 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.

»
4 months 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.

»
4 months ago, # |
  Vote: I like it -38 Vote: I do not like it

best joke ever

»
4 months 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?

  • »
    »
    4 months 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

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem C , My this submission getting WA on test 10 : 27605306 , what is the bug in my code ?

»
4 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Hi, very nice post.

Microsoft Phone Number UK

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please ignore this. Doubt was resolved.

»
4 months 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).

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem C, my submission: http://codeforces.com/contest/813/submission/27662850) is giving correct answer on Ideone for the 1st sample test case but the same submission is giving WA on Codeforces. Can you help me please? Test case: 4 3 1 2 2 3 2 4