Educational Codeforces Round 116 [Rated for Div. 2]
By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On Oct/29/2021 17:35 (Moscow time) Educational Codeforces Round 116 (Rated for Div. 2) 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 University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out.

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

Comments Comments (101)
| Write comment?
»
3 years ago, # |
  Vote: I like it +75 Vote: I do not like it
Lighthearted Meme
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Have you paid copyright to naman1601 for using that tag?

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

      Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to see their meme style being stolen by random people.

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

I wish if div 3's were more frequent...

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

Good luck to everyone on this educational :D

→ Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it
Non-related meme
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    my problem b just failed for longlong in this way...

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

I hope I can add 50 points

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

    sure you can! if there are any problems, just use calculator!

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

Glad to see no unusual time.

→ Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it
Normal timings be like:
→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey, I have few queries to ask about educational Rounds:

1) I heard that all problems have equal points, Is it so?

2) If every problem does have equal point, then, Is there any deduction of points after every minutes during contest? If yes, then does it vary for each problem?

Thanks in advance.

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

    It is ICPC style contest. There are no points. Only number of solved problems matters. And there is a penalty which breaks a tie between people with the same number of solved problems.

    Penalty is calculated like this. If you solve any problem, then the minute on which you solved it will be added to the penalty. For example if you solve problem after 1 hour and 23 minutes after the start, then 83(60+23) will be added to the penalty. Also if you had unsuccessful attempts on this problem previously, then each attempt will add 10 penalty points.

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

there are queue in codeforces it will be solved before the contest ??

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

How to solve E ??

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

    for dp[n][x], iterate over i = 0 ~ n but i != n — 1, which means i people died in the first round

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

      The condition to have no winner is to have at least two same max numbers and then the rest of the numbers can be anything less than that. Am I correct?

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

        Countercase: [1, 1, 2]

        There is only one maximum, but all heroes receive 2 damage in the first round and die, so there's no winner.

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

          Thank you for replying! Is this like an edge case? If no, then what was the intended solution?

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

            It's not an edge case, there's no way to eliminate these cases easily.

            We will post an official editorial in 24 hours after the contest.

            Shortly, the main idea is dynamic programming of the form $$$dp_{i,j}$$$ — suppose, after some round, all heroes received $$$i$$$ damage, and exactly $$$j$$$ of them died, what is the number of ways to make it happen?

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

              sorry but why wait 24 hours for editorial, when hacking ends in 12 hours? its almost as if educational rounds are notorious for slow editorials

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

          So maybe just handle such cases alone?

          My approach was adding all possible combinations with max value <= $$$min(n-1, k)$$$.

          Then for all $$$i$$$ bigger then or equal $$$k$$$, do what faraz said, at least two same max numbers and then the rest of the numbers can be anything less than that.

          I didn't implement in time though and unsure if even close to correct.

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

            This solution doesn’t cover all cases, and there is no easy way for that. And that’s why you have to do dp

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

Does problem D have an actual clean solution other than sorting the rows and prefix/suffix max/min on four sides?

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

:D In C Problem, complier 64bit wrong :D and 32bit AC :D -

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

    Most likely the pow function here is the culprit. Even if both of its arguments are integers, it still works with non-integer types, so it sometimes causes precision issues.

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

      tks, I think I need to use my pow function for the next contest.

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

      Took me 40 minutes to figure that out :')

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

      But i used the binary exponential as power still the error is there

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

    Can u please explain how u solved C problem?

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

      you can use n = 10^(a[i + 1] — a[i]) — 1 notes for each note. For the largest one, no maximum. Iterate each note from small to large. if k is more than or equal to n then use all the notes, minus n from k and move to next note. if you have k less than n, then use (k + 1) notes and done.

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

:| How to solve Problem D? :( I can't think of solutions for it.

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

    If you sort the rows by the first element in increasing order, it turns out that blue rows is a prefix of the matrix.

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

I read D wrongly as

  • every red cell in the left matrix contains an integer greater than every red cell in the left matrix;
  • every blue cell in the right matrix contains an integer greater than every blue cell in the right matrix.
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too, initially. But after looking at the figure, I corrected my understanding.

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

I want to ask all of you, honestly, pls tell me which problem was good for you and why? For me, it was so nonalgorithmic problems :(

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

    All are quite good problems. If you talk about algorithmic, D — F of course are.

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

Hi Folks, need help, how can we approach problem A? I tried few ways but my approach is wrong.

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

    first and last symbols must be the same of the string to achieve AB's = BA's

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

      Yes. I spent 19 minutes to realize this simple result...

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

        Me too got confused and after 5-6 WA i realized the simple solution :(.

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

Why Math.ceil() in java is giving wa on testcase 6 Wa But calculating ceil manually gives ac AC

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

    coz I think Math.ceil() will give some precision error while manual ceil gives correct answer. See below: ~~~~~ Input: 1000000000000000000 2 Checker Log wrong answer 2nd numbers differ - expected: '500000000000000000', found: '500000000000000002' ~~~~~

    . Using Math.ceil(), we will get above error . !!

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

Well that was embarrassing

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

How to solve E?

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

    Think about how to kill a fighter. His health should be lower than n. So, no winner means all fighters have health less than number of fighters at some time. Pick k players and assign them any health lower than n. C(n, k) * POW(n — 1, k) choices. For the other n — k fighters, health of each of them is decreased by n — 1. So, here is a sub problem: the number of choices when we have n — k fighters with maximum x — n + 1 health point.

    dp(n, x) = sigma(k = 0 to n, k!=n-1, C(n, k) * POW(n — 1, k) * dp(n — k, x — n + 1))

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

where is the editorial?

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

Damn , I solve problem after contest ended by menuties

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

Today I got a lot of WA on third as I was using gnu c++ 64 bit

Spoiler

but after contest friend suggested me to use gnu c++ 17

Spoiler

anyone know why this happen?

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

No idea how but I just ACed F using $$$O(n^{\frac{5}{3}})$$$, actually its $$$O(nk^2+\frac{n^2}{k})$$$ with $$$k=150$$$. Posting this here hoping someone can hack it somehow. 133531014

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

    I don't know whether or not it's hackable, but you can very easily improve the $$$O(nk^2)$$$ DP part of your solution to $$$O(nk)$$$ by simply not visiting useless DP states. Specifically, notice that you can't remove more nodes than you've currently processed, so if you've processed the first $$$m$$$ children of some node, and you're about to process ($$$m+1$$$)-th, then you have $$$\min(\sum_{i=1}^m sz_{ch_i},k)$$$ useful DP states. Proof for how this then becomes $$$O(nk)$$$ is here.

    With this, setting $$$k=\sqrt{n}$$$, the complexity becomes $$$O(n\sqrt{n})$$$, which comfortably passes in 1s, my code: 133546415

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

So many hacks on problem B. Can anyone give me the edge case?

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

can someone tell me whats wrong in my code? https://mirror.codeforces.com/contest/1606/submission/133515590

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

    Because 10000 iterations isn’t enough. Answer can be very large and you can’t loop.

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

      thanks but i thought it grow fast like fibancci sequence so i thought 54 is enough can you explain why this conclousion wrong

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

        After copied computers reaches k, each round could only add k more computers.

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

        For example n=10^18 and k=1. You can copy to 1 computer at a time

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

How to solve F? I assume quadratic DP is trivial? Can it be improved or something?

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

It is really an educational contest thanks for writers

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

can someone help me with my code https://mirror.codeforces.com/contest/1606/submission/133548731. It is giving wrong answer and I don't know why.

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

    Overflow. Change dp[i+go][k]+=dp[i][j]*(power(go,j-k,mod)*ncr(j,k,mod))%mod; to: dp[i+go][k]+=(dp[i][j]*((power(go,j-k,mod)*ncr(j,k,mod))%mod))%mod.

    This will solve the WA, but you will get TLE.

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

      thanks a lot. i think the tle can be fixed by precomputing some stuff.

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

How to solve problem E? I'm stuck.

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

It's been more than 8 contests and haven't improved yet, feeling very low and disappointed not able to solve even a single question in this round. Also doing upsolving but not improving any suggestions please

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

    Create a mashup of 4 A(1000 level) problems + 4 B problems(1200 level) and solve them in the virtual contest.

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

Can someone please explain their approach for Problem D?

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

    let mnl[i][j] be min(a[i][k] for 1<=k<=j), mxl[i][j] be max(a[i][k] for 1<=k<=j), mnr be min(a[i][j] for j<=k<=m) and mxr be max(a[i][j] for j<=k<=m). Iterate from column number 1 to column number m-1. Let the current column number be j, let array t contains all the row indices i in ascending order of mxl[i][j]. Now, if we can cut the column into two pieces at column j (j being in the left part), there must be some prefix of t such that max(mxl[k][j] for k belongs to prefix of t)<min(mnl[k][j] for k belongs to suffix of t) and min(mnr[k][j+1] for k belongs to prefix of t)>max(mxr[k][j+1] for k belongs to suffix of t). Here, all the indices in prefix are coloured blue and the rest are coloured red.

    Here is my code. (Ignore the segment tree templates. I initially thought of implementing using segment trees but, later used multisets).

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

Can anyone tell me what's wrong with my solution? 133471460 For example on this test case : 576460752303423488 288230376151711743

Jury's answer is 60 but according to me it should be 59. As, first 59 powers of 2 will give the sum of n-1 and 2 ^ 58 < k here.

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

    Even I got it wrong. The issue is with log2. Instead divide by 2 repeatedly.

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

How to solve F using segment tree or treap?

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

Hi , i was checking my final standing and i saw i just got wrong answer after the contest and even hack session was over while before that i have got accepted in problem B. So i don't know if they changed the test cases or what but i think it's not fair to change the test cases when the contest is over and changing the test cases should just be allowed while the contest is running.(and i didn't get hacked , i just suddenly got wrong answer on test 30 in problem B).

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

    This a rule in contest which have hacking phase in them. They collect all hack cases and insert them as new tests.

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

When will the editorials and the ratings get updated?

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

This is my hack case which kills more than 100 submissions.
The issue is numerical error of log or pow in 1e18.
see also the editorial of this problem : ABC215-B

13
576460752303423486 576460752303423486
576460752303423487 576460752303423487
576460752303423488 576460752303423488
576460752303423489 576460752303423489
576460752303423490 576460752303423490
576460752303423488 288230376151711743
576460752303423488 288230376151711744
576460752303423488 288230376151711745
576460752303423486 576460752303423485
576460752303423487 576460752303423486
576460752303423488 576460752303423487
576460752303423489 576460752303423488
576460752303423490 576460752303423489
correct output
→ Reply
»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Hi, awoo, and other round coordinatrs. Please check this issue that my solution for problem C is skipped, reason stated that it was coincided with others solution. The solution to the problem is quite intuitive, may be, that's the reason. Please check it. Not this time again.

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

    can you tell us the number of submission that coindieded with yours??

    if you can't, you are just another cheater from India -the country of cheaters-.

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

    The solution to the problem is quite intuitive, maybe, that's the reason, Yes it is so intuitive that you changed your template and coding style on C.

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

Can someone help me explaining why this solution for E problem is not correct?
In my solution winner must have >= n health to win(others n — 1 heroes can have < winner health)
Then I subtract from all possibilities win possibilities
https://mirror.codeforces.com/contest/1606/submission/133586943

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

    I did the same thing but it wasn't working for the fourth sample case. If someone can point out the error in the approach, it would be really helpful.

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

MikeMirzayanov In the Educational round that was conducted yesterday, I have been wrongly flagged for plagiarism. The solution for question C was fairly straightforward in terms of logic and coincidence should have been expected by the problem setters. I assure you I have not indulged in unfair practices. I participated after a fairly long time and was really happy that I performed well. Please return my rating delta. Thanks in advance.

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

Was waiting for an educational round for a long time.... Finally had a great contest today and was ranked 858(my first ever under 1000 rank :-) and got a rating boost of +105 :-)

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

I haven't been seeing them publishing top 5 winners and top 5 hackers and 1st one to solve the each problem for a while..

→ Reply