Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By BledDest, 21 month(s) 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  
  • +186
  • Vote: I do not like it  

»
21 month(s) 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

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Added this information to the announcement.

    • »
      »
      »
      21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Unfortunately, it clashes with csacademy round 22.

»
21 month(s) 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**

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    OMG!!! Somebody is very angry...

    • »
      »
      »
      21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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 !!!!

      • »
        »
        »
        »
        21 month(s) 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 :)

  • »
    »
    21 month(s) 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.

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it -22 Vote: I do not like it

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

»
21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    they don't understand the true value of contest

    • »
      »
      »
      21 month(s) 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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    ARE YOU ON DRUGS?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

E is so beautiful and amazing! Thank you!

»
21 month(s) 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?

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Try this case

    1
    1000
    
    • »
      »
      »
      21 month(s) 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....

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone post code of first problem?

»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why on earth would he do that ?

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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)

»
21 month(s) 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.

»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

Why do I get Unexpected Verdict while hacking C?

»
21 month(s) 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)).

»
21 month(s) 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?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many people hacking their own solution?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) 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?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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.

        • »
          »
          »
          »
          »
          21 month(s) 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.

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

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

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

How do you solve E?

  • »
    »
    21 month(s) 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.
    • »
      »
      »
      21 month(s) 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

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

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

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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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 !

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I solve C?

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It can be solved with DP

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ? Is this a greedy problem ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be solved by dynamic programming.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      isn't it able to solve with normal logic?

      • »
        »
        »
        »
        21 month(s) 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 :)

»
21 month(s) 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.

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When are the editorials scheduled?

»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it
»
21 month(s) 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.

»
21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Maybe the stl is different.

  • »
    »
    21 month(s) 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.

»
21 month(s) 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 ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    In problem A, Anti-quicksort hack cases work.

  • »
    »
    21 month(s) 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.

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

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

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