By BledDest, 5 weeks ago, In English,

Hello Codeforces!

Good news! Harbour.Space is supporting the return of a new series of educational rounds on Codeforces! You can read the details in the blog post.

On March 27, 17:35 MSK will be held Educational Codeforces Round 18.

You will be given 6 problems and 2 hours to solve them. We hope that everyone, both novices and experienced coders, will find something interesting in this contest. The contest will be unrated.

The round was prepared by Mikhail PikMike Piklyaev, Mikhail MikeMirzayanov Mirzayanov and me. We'd like to thank Maxim HellKitsune Finutin and Alexey ashmelev Shmelev for testing the round.

Wish you enjoy the contest! Good luck!

UPD: Editorial.

UPD2: All successful hacks have been added to the testsets, all submissions have been rejudged. Thank you for participating in the contest!

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone confirm to me that this contest won't be rated, because im not sure

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +54 Vote: I do not like it

    It is unrated like every previous educational round. Sorry that it isn't mentioned in the post.

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

      Added this information to the announcement.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, i hope that it will be a good contest so that i can improve my skills :D

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Unfortunately, it clashes with csacademy round 22.

»
5 weeks ago, # |
  Vote: I like it -135 Vote: I do not like it

MikeMirzayanov

** WHY TO ORGANIZE SUCH UNRATED CONTEST? IF ANYONE WANT TO LEARN HE CAN PARTICIPATE VIRTUALLY.AND IF ANYONE WANT TO SOLVE QUESTS LIKE THESE ROUNDS' THEN WE CAN USE TAG OF EDUCATIONAL ON PROBLEMS LIKE PTHER TAGS DS,DP ,GRAPHS ETC.SO,THERE IS NOTHING IN FAVOUR OF THESE KIND OF UNRATED ROUNDS**

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    OMG!!! Somebody is very angry...

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it -78 Vote: I do not like it

      Yes,Your Father is Here and He is very angry.Go inside

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it +23 Vote: I do not like it

        OOPS!!! Somebody is really really very angry. I think you got enough downvotes to cool down now...... Otherwise, go to Himalayas and do some Meditation !!!!

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

        Hey dude, say whatever u want but don't mess with people's parents, they didn't do anything to u, peace out :)

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

    If you don't like, you can unjoin and nobody force you to register it.

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Making educational round be rated, the number of participant will increase a lot. Sorry for my poor English.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I see a lot of people apologizing for their English here. Why ? It is not like English is your first language. Chill man.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      Generally speaking, only 25% of world population speaks English, rest of the people use google translate and add "Sorry for my poor English" at the end.:-D

      Sorry for my poor English.

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Thank you Harbour.Space for Supporting........

»
5 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

IS IT RATED!!?!?!?!?!?

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

It's interesting that some of my friends are more interested in participating when it's not rated haha

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    they don't understand the true value of contest

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Honestly I think having fun competing is more important than ratings so I'd say that's kinda true

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

The issue with problem C may have affected some contestants. The round should be unrated.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +94 Vote: I do not like it

    Yay. I totally agree with you :)

    The organizer must have predicted this issue would happen and announced the round to be unrated before the round had started.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    ARE YOU ON DRUGS?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E is so beautiful and amazing! Thank you!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did someone else keep getting WA15 on F? If yes how did he/she fix it?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I fixed, I found that i tried to maximize y/x, but actually we need to minimize it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

isn't E a binary search? get WA at test4!

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Try this case

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

      thanks, binary search seems not appropriate to this problem. I'm turning to learn with tutorial....

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the test data be published now or one day later?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone post code of first problem?

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Has "unused" hacked his own solution ?! Appears so to me !!

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

    Why on earth would he do that ?

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

Is F relative to Linear Programming? Using duality lead the problem to work with lines.

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

    i am not sure but i guess maintain an upper convex hull of points and checking if the query points are inside or not should work , something like this.

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

    It can be solved with geometry, we have to support two operations:

    1. add one point (mana cost, damage) and keep the convex hull of all the points so far.

    2. determine if after scaling the convex hull by t it intersects the rectangle (Maximum mana, Health)

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What does "unexpected verdict" mean when hacking a solution? I received it while hacking problem C.

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

I tried to hack C and the verdict was "Unexpected verdict". What does it mean?

**UPD**: It is now a successful hacking attempt
»
5 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Why do I get Unexpected Verdict while hacking C?

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

What was the expected complexity of problem E?I guess I had a solution in nsqrt(max(ai)).

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I hacked a friend on a solution he sent after the contest finished but still got -1 on hacks. Is this intended?

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

Why so many people hacking their own solution?

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

What was the issue with problem C? I am unaware of it.

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

Great contest! Are editorials for the problems going to be published? And when?

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

How to solve D?

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

    notice that all values in left subtree < value at current node and all values in right subtree > current node and all values in this subtree are in some range [l , r] and the value at current node is (l + r) / 2. Using this you can find the node u in log(N) the same way as you find stuff in a binary search tree and then continue the traversal there while mainting the list of ancestors of a node.

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

      I did that solution during the contest, but i keep getting WA on test 10, do you have an idea why that happens 25855671

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

        I also got a WA on test 10, then I removed all the pow() operations and computed the values on my own, and this got me an AC. I think it's due to the inaccuracy of pow(), that you are getting a WA.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          Yup, the problem turned out to be bitwise operations, i simply changed the line root=1<<(levels-1); to root=(n+1)/2 and it got accepted.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It should be 1LL << (levels - 1) — shift amount doesn't promote the type of expression to long long.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              ohh so that was the problem. Thank you ^^ I will keep that in mind from now on

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

    I used two variables l and r to mark the leftmost (smallest) number and rightmost (largest) number of the subtree of current node.

    For 'L' and 'R' operations:

    When l = r, it means that the current node is at the deepest layer, so we should ignore these operations. Otherwise, shrink the range by making l = mid+1 for 'R' operations, or r = mid-1 for 'L' operations, where mid = (l+r)/2 (the current node).

    For 'U' operations:

    When l = 1 and r = n, it means that the current node is the root, and we should ignore this operation. Otherwise, check the (x+1)th bit where xth bit is the lowest bit containing 1. If that bit is 1, the current node is in the right subtree of its parent. If that bit is 0, the current node is in the left subtree of its parent. Expand the range by moving l and r pointers.

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

    I made a function that receives a number x and returns info = {value, level, left/right, difference with parent} about it in log(n).
    You can observe that for node x, value of left child is x-dif, value of right child is x+dif. dif reduces by 2 on each level.
    Using this, it becomes easy to process up, left and right queries.
    Here is AC code.
    Here is same code with comments.

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

How do you solve E?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    1. Let the number of ball in box noted a1 a2 ... an;
    2. First you will find the minimum ai in this array (marked as ak).
    3. Then, let's enumerate all size as (ak/1, ak/2, ... ak/ak), let pki = ak/i, if (ak%i == 0) we will try that (pki, pki+1) and (pki, pki-1), otherwise, we wil try (pki, pki+1);
    4. If we discover a pair (pkj, pkj+1) can combinate all box(a1,a2,...an), then we find the maximum size of set is (pkj, pkj+1);
    5. Output the sum of Pi = ai/(pkj+1) (PS: if (ai%(pkj+1)) != 0 then Pi = Pi + 1) for answer.
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And here is my poor code... I'm sorry about I forgot it.25873907

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why we are treating the case when a[0]%k==0 differently?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If ak%i == 0 then we don't know if (pki,pki+1) can combinate all box, If it can make it, they will be the maximum size. If not, then(pki-1,pki) also can combinate this box ak, so I think we should try this case.

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

Hi,

Thanks to the organizers for these problems.

Just to be sure : I get an error on the C, it's said my output is not "0", it's "0" followed by a random character. I think there is an error in the evaluation test. In fact, my string is obtained this way :

string s; s=""; s+='0';

The result must be : s=="0" (cast of '0' in a string format), don't you think ?

Thanks, Regards.

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

    Sorry, my mistake. I've just found a bug in my source code. CodeForces forever !

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

How do I solve C?

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

    Find K = sum%3. If its 0, you are done.
    Otherwise, you have to remove at max 2 elements to make it a multiple of 3.
    So there are few cases only that you have. I maintained a vector of pair for both cases, when K is 0 and when its 1. Find for each case the resultant string and take the one with minimum deletions. (Also for more optimization you won't remove digits like 3,6,9 anyway.) Here is the code.

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

    It can be solved with DP

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

How to solve C ? Is this a greedy problem ?

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

    It can be solved by dynamic programming.

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

      isn't it able to solve with normal logic?

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

        You can, but probably you will have many bugs in code (like me :P). So, you can try :)

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

What is wrong with this approach of D ?

IF str[i] = 'R' do curr_node = curr_node + 2^(tree_height-curr_height -1 ).

IF str[i] = 'L' do curr_node = curr_node - 2^(tree_height-curr_height -1 ).

IF str[i] = 'U' , I divide curr_node by 2 until it becomes an odd number. If obtained_number+1 is divisible by 4, this implies curr_node is right child of it's parent. currr_node = curr_node - 2^(tree_height-curr_height).

Else currr_node = curr_node + 2^(tree_height-curr_height).

I am maintaing curr_height accordingly at each step and also checking for the bounds.

Getting WA at test case 6.

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

    I think the method you decide if a node is a left child or right child is wrong, because everything else that you said is like mine solution. Instead of checking if current_node is a right child or left child by some formula, I simply keep a stack on the moves I have made. You can look at my solution if you want 25872554

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

      Actually, the solution worked.

      I had error in implementation. The algorithm is passing all the test cases.

      My AC Solution: Link

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

When are the editorials scheduled?

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

the problem C's datas are too strong,,,I had WA many times.

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Someone pls help me with this. this program runs pretty well on my own computer. But it does not work in the test. It got wa on test 3, where the output should be all YES (and it is on my computer)

25863026

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

    Maybe the stl is different.

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

    Well, when I switch to c++14 from c++11 I got more YES, but still wa on test 3. I feel quite confused.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

for problem A, there are more than 150 hacks in java.what's wrong with java ?

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

    In problem A, Anti-quicksort hack cases work.

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

    Java has a method called Arrays.sort(); that uses a quick sort method to sort an array. Quick sort's average run time is O(nlogn), but it's worst case scenario sort is O(n^2). People used a worst case scenario input/generator to hack many java solutions.

    P.S. To fix this just use Integer instead of int for your array since to sort objects, java uses a merge sort instead, which runs in time.