Educational Codeforces Round 18
By BledDest, 8 years 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 awoo 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
  • +186
  • Vote: I do not like it

Comments Comments (80)
| Write comment?
»
8 years 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

→ Reply
  • »
    »
    8 years 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.

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

      Added this information to the announcement.

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

Unfortunately, it clashes with csacademy round 22.

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

    You can unregister 2 contests at the same time :D

    → Reply
»
8 years 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**

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

    OMG!!! Somebody is very angry...

    → Reply
    • »
      »
      »
      8 years 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

      → Reply
      • »
        »
        »
        »
        8 years 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 !!!!

        → Reply
      • »
        »
        »
        »
        8 years 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 :)

        → Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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.

→ Reply
  • »
    »
    8 years 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.

    → Reply
    • »
      »
      »
      8 years 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.

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

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

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

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

→ Reply
»
8 years 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

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

    they don't understand the true value of contest

    → Reply
    • »
      »
      »
      8 years 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

      → Reply
»
8 years 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.

→ Reply
  • »
    »
    8 years 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.

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

E is so beautiful and amazing! Thank you!

→ Reply
»
8 years 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?

→ Reply
  • »
    »
    8 years 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

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

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

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

    Try this case

    1
1000
    → Reply
    • »
      »
      »
      8 years 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....

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

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

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

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

→ Reply
»
8 years 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.

→ Reply
  • »
    »
    8 years 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.

    → Reply
  • »
    »
    8 years 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)

    → Reply
»
8 years 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.

→ Reply
»
8 years 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
→ Reply
»
8 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Why do I get Unexpected Verdict while hacking C?

→ Reply
»
8 years 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)).

→ Reply
»
8 years 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?

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

Why so many people hacking their own solution?

→ Reply
»
8 years 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?

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

How to solve D?

→ Reply
  • »
    »
    8 years 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.

    → Reply
    • »
      »
      »
      8 years 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

      → Reply
      • »
        »
        »
        »
        8 years 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.

        → Reply
        • »
          »
          »
          »
          »
          8 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years 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

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

      Can you explain the proof of the fact that the value of the current node is $$$(l+r)/2$$$? I think it is very easy to come up with this observation but I can't seem to prove it.

      → Reply
  • »
    »
    8 years 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.

    → Reply
  • »
    »
    8 years 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.

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

How do you solve E?

→ Reply
  • »
    »
    8 years 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.
    → Reply
    • »
      »
      »
      8 years 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

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

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

      → Reply
      • »
        »
        »
        »
        8 years 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.

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

How do I solve C?

→ Reply
  • »
    »
    8 years 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.

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

How to solve C ? Is this a greedy problem ?

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

    It can be solved by dynamic programming.

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

      isn't it able to solve with normal logic?

      → Reply
      • »
        »
        »
        »
        8 years 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 :)

        → Reply
»
8 years 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.

→ Reply
  • »
    »
    8 years 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

    → Reply
    • »
      »
      »
      8 years 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

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

When are the editorials scheduled?

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

Somebody please HACK this — http://codeforces.net/contest/792/submission/25851911

→ Reply
»
8 years 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.

→ Reply
»
8 years 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

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

    Maybe the stl is different.

    → Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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 ?

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

    In problem A, Anti-quicksort hack cases work.

    → Reply
  • »
    »
    8 years 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.

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

Could someone please explain this to me: In problem E, I used the solution to go from i to min in array a, and then check min/i and min/i + 1... I understand why and why we check these things ( for every element in a, x1 = a[j]/x, mod = a[j]%x, and if(!mod) just add x to ans, if not, check if(x1+mod<=x-1) add x+1... otherwise... return 0, it's not possible for this x). Now, my question is, is there a proof why this never exceeds the time limit (in fact, it doesn't seem to even get close to exceeding it)? Because the smallest element can be larger than 10^8?

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

    We don't iterate from i = 1 to , instead it's up to . When you want to divide some ai into k sets, each set will be of size . Therefore or . Thus, it's possible to check every case by checking up to the root. Since on each iteration we iterate over our array of size n, the time complexity of the solution is

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

      Thanks for your time, I get that but I submitted a code which goes until m and breaks when a correct solution is found. But I only check m/i and m/i+1, whereas for it to mathematically be correct, I have to check for i+1 and i as well, however I don't and it still works, what am I missing? Edit: This is my submission (28747357)

      → Reply