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

Hello Codeforces!

On Dec/18/2021 18:35 (Moscow time) Educational Codeforces Round 119 (Rated for Div. 2) will start. Please, note the unusual start time.

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!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hello once again, Codeforces!

Almost 5 months have passed since we organized the Harbour.Space Scholarship Contest 2021-2022. It’s been quite a tough challenge with more than 15,000 participants. However, we were able to select the ones who were ready to take the opportunity and join Harbour.Space this year. In addition to the contest, we carefully reviewed all scholarship applications and awarded a total of 11 students.

We would like to introduce you our Competitive Programming Scholarship Winners who have already arrived to Barcelona:

aniervs, MaksymOboznyi, 244mhq, Meijer, bthero,amanbol, DimmyT, 998kover

We are looking forward to achieving incredible results with our new ICPC teams. One of them, Harbour.Backspace (MaksymOboznyi, 244mhq, 998kover), has already finished in 3rd place during Moscow Workshops. We wish them the best in the upcoming contests.

Codeforces and Harbour.Space

As usual, we are always excited to see Codeforces participants as our students here at Harbour.Space

UPD: Editorial is out

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

Comments Comments (169)
| Write comment?
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Excited for the contest, Wishing everyone high ratings in last Educational Round of 2021.

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

forward Kazakhstan

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

Always love educational round.

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

Please, note the unusual start time.
ok at this point I got lost, what's the actual usual time!?

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

unusual unusual time(you know,usual unusual time means before 17:35)

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

The start time in China is too unusual!

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

Shouldn't it be BYE BYE educational 2021 XD...

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

cheaters who registered in this round: nitin_05 ashokesen02

  1. will they cheat again in this round?
  2. if so, will they not be caught and be rated again?!
  3. who will cheat better and drain more ratings from other innocent users?!?
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Why you just keep on posting same thing again and again in every contest's announcement.My advice to you is not to focus on others whether they are cheating or not rather you should practice more and more to surpass those cheaters. And for cheaters they can become expert or CM by cheating but ratings without having knowledge is of no use they can't use it anywhere be it in Online tests,interviews.

    So just focus on developing skill and you can see positive outcomes after sometime :D.

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

SIUUU

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

Wasn't this time the usual one now it became unusual

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

Why so negative?

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

I hope this round will be excellent! (as usual <3)

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

Hope this time my rating will increase and my contribution rating will not go more negative.

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

C should not exist

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

    A was harder than C, change my mind lmao

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

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

I m not able to understand the 3rd test case of the C problem we can at max replace all '*' with 'bbb' and then also the rank will be 16 but it is asking for 20? Help me understand it. Be merciful on me.

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

    If I am not wrong for the third test case of C 6 3 20 **a*** output -- babbbbbbbbb The strings are -- 

    - a
- ab
- abb
- abbb
- abbbb
- abbbbb
- abbbbbb
- abbbbbbb
- abbbbbbbb
- abbbbbbbbb
- ba
- bab
- babb
- babbb
- babbbb
- babbbbb
- babbbbbb
- babbbbbbb
- babbbbbbbb
- babbbbbbbbb

    btw was not able to solve it.. RIP

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

    The number of possibilities is not 16. In the first group of asterisks, we can have at most 6 'b'. In the second group of asterisks, we can have at most 9 'b'. So, the total number of possibilities is (6 + 1) * (9 + 1) = 70.

    You can fix the first group of asterisks with some number of 'b'. Then, you can have 10 different strings as you can adjust the number of 'b' in the second group of asterisks.

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

C is in a difference lever :v

→ Reply
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it
Back at it again :')
→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Please any one give me a hint to solve E ??

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

    linked list

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

    its actually just basic implementation [too easy for position E, I think].

    For each query of type-1, find the nearest to the right query of type 2 which has the same $$$x$$$ and add an edge between these two indices. For each query of type 2, find the nearest to the right query of type 2 which has $$$x$$$ as the $$$y$$$ of current query and add an edge.

    this structure forms a forest.

    Then the value of each type 1 query in the final array is just the value of the root of the tree this index is a part of.

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

    Try to build array by performing actions given in input in reverse order and store some useful information.

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

    You can store for each x, all indices that have value equal to x in a vector, let's call it v[x].

    For the queries: set all elements equal to x to y, you can move all the elements from v[x] to v[y], use small to large to do this.

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

      So it will be O(n^(3/2))?

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

        No, it will be $$$O(N\cdot\log{N})$$$, each time you merge two vectors, the resulting vector will be at least two times the size of the small vector, so each element will be moved from a vector to another at most $$$\log{N}$$$ times.

        Note that you swap the vectors if needed to move always from the smaller to the bigger, just using swap is $$$O(1)$$$ for most stl containers, like vectors, sets, maps.

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

          Wow, interesting, thanks. And in this problem we could kinda do it in O(n) using deque instead of vectors, right? Since merge of deque is O(1).

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

            Are you sure that deque's merge is O(1)? cppreference doesn't mention it, and considering how deques work, I think it is complicated to do it in O(1), I am not sure tough.

            With a conventional double linked list you can do that, but I think deques are something more complex.

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

              Crap, I thought deque in c++ IS a conventional double linked list. Thanks for pointing out. Now I need to go and check if deque id double-LL at list in my python... :)

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

    I think simplest solution is to iterate the queryies from last to first. We maintain a transision table, no tree or something complecated needed.

    see 139792544

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

    My solution uses array of linked lists.

    For query of the form 1 x, we add index of x (which is equal to current number of appended elements so far) to the end of the linked list located at array[x].
    For query of the form 2 x y we move all elements of the linked list located at array[x] to array[y].

    At any given point, array[val] stores all the original indices which ended up holding the value of val. https://codeforces.net/contest/1620/submission/139814623

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

    If you execute the operations from the last going backwards you can keep&update a mapping for each number quite easily. At the start, mapping[x] = x for every x. Then:

    • type 1, append mapping[x] to the result
    • type 2, update mapping[x] = mapping[y]

    then print reversed(result)

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

I didn't have time but I think problem G can be solved using inclusion-exclusion for each mask of subsequence [where the value of each mask represents the number of strings which are subsequences of all strings which have bit set in the mask]. Is it the right idea?

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

Can E be solved with some modification to dsu?

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

      thamks so much. what does this mean: if(~qr[i].second) what does '~' do?

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

        if (~qr[i].second) is equivalent to if (qr[i].second != -1)

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

Can I improve my delta by hacking someone else's solution?

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

I eagerly wait to know the author of problem D

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

    I just needed one more minute to submit my solution.. ://///

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

I didn't get AC for B until there was exactly 1 minute left because I used int instead of long

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

    It's because Base*Height may exceed int range.

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

HELP nitin_05 cheated again!!!!!

139758679 139767791 139800928 139812299

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

    The attempt was so blatant lol, Dude commented the block of code and then wrote the same code and thought that he wouldn't be caught by the CF plag system.

    The first thing any plag tool does is to wipe off all the comments, spaces and indents and read the code as one single line.

    How dumb can one be.

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

Was I the only one who found E much easier than both C and D.

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

12 wrong submissoins on C. I just want to die

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

    please don't die

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

    metoo.. still don't know why the 4th test case doesn't work out -.-

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

    I learned that lesson ones or twice (or more?) and now I try to avoid the guess game — today (again) I had to write a tests with brute force function that generates all possible strings for a small templates, that can be easily understood. Sorted them and compared to my solution for every X. 15 extra minutes was enough to find I had >= instead of > in some place. Some times I search for this 30 — 45 — 60, but it is definitely giving me more than wild guessing.

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

My approach for Problem E: Replace the Numbers

The idea is pretty similar to 365A: Knight Tournament

Suppose an element $$$x$$$ is appended to the end of the array at the $$$j^{th}$$$ query. We can make the following 2 observations:

  1. The final value of this element would not depend on any Type-1 or Type-2 query strictly to the left of the $$$j^{th}$$$ query.
  2. If we have two Type-2 queries strictly to the right of the $$$j^{th}$$$ query, say at indices $$$k_1$$$ and $$$k_2$$$, (such that $$$k_1 < k_2$$$), and they both operate on $$$x$$$, i.e they both instruct to change the value of $$$x$$$ to $$$y$$$ or $$$z$$$ respectively, then the first query takes precedence.

So, if we process the queries in reverse order, then by the time we reached the $$$j^{th}$$$ query (counting from zero), we would have all the information to restore the value of $$$x$$$, if we keep overwriting the values of $$$x$$$ in case of overlapping Type-2 queries.

So, if we define $$$sink[x]$$$ as the value that $$$x$$$ should be currently converted to, we can process the queries as follows:

  • Type-1 Queries: Just append $$$sink[x]$$$ to the result.
  • Type-2 Queries: Update $$$sink[x] = sink[y]$$$.

Finally, reverse the $$$result$$$ vector.

Implementation

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

How to solve E?? is there any way to pass test case 5??

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

    no, there is no way to pass test case 5

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

I took more than an hour to solve C but only 7 minutes for E.

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

Please, help me. Why I get WA on C: https://codeforces.net/contest/1620/submission/139816488 ?

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

I think many people passed G with $$$O(26*n*2^{n})$$$, but it wasn't intended right?

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

    Unfortunately, it was hard to cut all of them off. The model solution works in $$$O(2^n \cdot (n + A))$$$, but its constant factor is kinda big so I couldn't set $$$n = 24$$$. In retrospect, perhaps it would be better to swap F and G and set something like $$$n = 20$$$ instead of $$$23$$$.

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

      Yeah, my complexity is the same. Yes, swapping F and G could have been better.

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

    How do you do it with that complexity? Is it even easier than $$$O((n + 26) 2^n)$$$? I can't imagine a solution where it is not immediately clear how to optimize.

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

      Lol me too, but I think what some people did was to calculate for each mask, the contribution of each alphabet by iterating on all set bits instead of using the precomputed values and taking the low bit of mask.

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

      One of the approaches I tried to cut off was based on the following dynamic programming:

      $$$dp[i][mask]$$$ — the number of different strings consisting of the first $$$i$$$ characters of the alphabet such that they are subsequences of every $$$s_i$$$ from the mask, and are not subsequences of any other $$$s_i$$$, with $$$O(A \cdot 2^n)$$$ states and $$$O(n)$$$ transitions from each of them.

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

      I used dsu like you in E but m getting mle and I have no idea why

      can anyone look into this .This would be a great help I encountered such thing first time my submission

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

        For starters, you can look at this testcase

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

          thts ok but I was getting mle constantly , I dost know its reason

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

        same here. my solution. https://codeforces.net/contest/1620/submission/139812356

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

          Not entirely sure about the reason for MLE, but your code does produce SIGKILL runtime error on the following input.

          Input

          I see a lot of contestants getting MLE on TC4, I wonder if they are making a similar mistake or it's the nature of the test-case. Do let me know if you figure out the reason.

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

            infinite recursion in happening which is leading to stack overflow which is the reason for mle ig

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

            thnku very much

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

Getting ready for a -100 LOL :p

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

I don't understand the gap

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

I'm curious what's test 2 here that's causing WA.

https://pastebin.com/41BJXM9H

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

how to solve A?

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

    Please don't ask me :((

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

    Let $$$cnt$$$ is the number of $$$N$$$ between $$$s_i$$$ and $$$s_{n-1}$$$.

    • $$$cnt = 0$$$ means $$$a_1 = a_n$$$ or $$$s_n = E$$$.
    • $$$cnt = 1$$$ means $$$a_1 \neq a_n$$$ or $$$s_n = N$$$.
    • Otherwise, there always exists a solution.
    Spoiler
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so tight constraints! :/

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

solved D after contest ended 3min :D

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

    Same dude, 1 minor mistake let maxx be the biggest element in array i didnt check if there were any maxx-1 — s elements in the array if maxx%1=3

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

No greedy,that I cannot solve any problems.

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

One Doubt , I submitted 1st Accepted Solution to C at 1:08 and second at 1:18 if the first one gets hacked or FST , the second one's final verdict will decide my rank ?

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

    The second one will contribute, the first one is kind of nullified by your second submission.

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

      Thanks , In non educational Div 2 Rounds , Penalty for multiple submission (correct or incorrect ) is added in the standings while here no additional penalty is showing currently .

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

        I would have expected 10 minutes penalty per submission, the first one is free. But not sure.

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

Why is there TL on 5 test? Submission: https://codeforces.net/contest/1620/submission/139803575

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

    Because your complexity is not good?

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

      can you tell me what is the time complexity link of this solution, according to the constraints shouldn't this give solution gives tle?

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

        It's $$$O(q \log q)$$$.

        It uses small-to-large merging, unlike the person I replied to. Basically this line is very important: if (y.size() > z.size()). It can sound unintuitive but in total, every element gets copied from one vector to another only $$$O(\log q)$$$ times (it's similar in the idea to HLD and union-by-size in DSU).

        Proof sketch

        So in total it's $$$O(q \log q)$$$. Also y.swap(z) takes constant time (I didn't know this) so no worries there.

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

Really hard test case 3 in problem C for my small brain :(

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

WORST round EVER!

Emplemetionforces and speedforces combined

bruh

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

    Actually this is more or less the defintion of educational rounds. If you do not like this you should not participate in them.

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

      lmaoo, no bad comments today because you performed well, sucker!

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

      bruh

      that was my third educational round for the last year or so

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

I didn't get D... Somebody please explain the third and fourth case

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

C has an overflow issue.. I got too many WAs because of overflow issue

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

    Same :( I spend like an hour trying to find what to issue was, only to realize after the contest that it was overflow :(

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

D drove me mad...qwq

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

Why my solution got Memory Limit error? I couldn't see what is the problem. https://codeforces.net/contest/1620/submission/139812356

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

very cool problems! managed to solve A,B and C, and it somehow felt like A stumped me the most. thank you for a good round.

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

I'm surprised nobody mentioned a solution using DSU for E yet. It's the first thing I thought of, could there be something wrong?

  • Initialize DSU to size equal to number of final array elements.
  • Maintain two mappings: (DSU leader -> value) and (value -> DSU leader)
  • Processing the queries seems straightforward..? The only things to be wary of are that when you need to merge values, the DSU leader of a component may change, and you need to make sure that only leaders are present in the mappings.
  • In the end, the value for index i, processed in increasing order, is the value of its leader.
→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think D and E should have been swapped. E was as simple as simulating the process backwards.

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

Is there an etalon solution for problem E in Python3? My solution is O(n) but it exceeds time either on test 13 or sometimes on test 17 sometimes, even with fast IO

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

    Tried it in Python first too, got 2 TLEs, wrote the same code in C++, got AC.

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

    There is a lot — check out submission stats for a problem — and you can just switch to pypy3 sometimes it helps. is yours code AC in pypy3.

    PS. And to add: you are creating a lot of objects (lists) to encode input. Try to simplify it and get rid of them.

    P.P.S. Or maybe not and I am wrong (about creating a lot of objects) — cause your solution is faster than my when I run it on PyPy :)

    PPPS. Oh, no, I was right, but you have reall-really-really good "fast-input". My solution become twice faster with it — thank you very much!

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

Can someone help with this submission?

https://codeforces.net/contest/1620/submission/139828156

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

Why is my code for C TLEing? 139829242

I think my complexity is O(n*k), where n<=2000, k<=2000

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

    A given string may have b, but your program did not consider it.

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

      "...that consists only of characters 'a' (a lowercase Latin letter) and '*' (an asterisk)."

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

    You are overflowing LLONG_MAX (9e18) on the line temp *= (v[i]*k)+1;. This is undefined behaviour and you are TLEing because of this. Be sure to make sure that temp is not overflowed.

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

      Thanks, took care of it and it passed. My dumb ass wasted too much time on this foolish mistake during the contest ;_;

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

This "hack" is borderline hilarious.

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

C >> D

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

I don't know if the intended time complexity of the solution for D is $$$\mathcal{O}(N)$$$, but checking only 7 possible patterns for cost of each bag receives AC verdict.

The patterns are:

Can anyone hack this solution? Submission:

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

    That is correct, in the optimal answer you get at most one 1-token and at most two 2-tokens.
    That is because you can always break two 1-tokens into one 2-token and break three 2-tokens into two 3-tokens thus getting a better answer always:
    1) (1+1) -> (2)
    2) (2+2+2) -> (3+3)

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

      Also, whenever cost of any bag is 1, we need to ensure atleast one 1-token is present.

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

Can anybody tell what I am doing wrong in C. solution link — c

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

Can someone explain why my memory limit is exceeding in my solution for C 139817111

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

How to solve problem F?

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

I passed C after the contest when i used unsigned long long rather than long long. Codeforces doesnt support cry emojis

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

Thank you, too good to goodbye for 2021.

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

Am I the only one who found C much easier than D and E?

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

Why are contestants with ratings greater than 2100 being shown as official participants? will they be removed from the official list and then acc. our rating change will be calculated?

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

E can be simply solved by small to big technique. just merge. here is my submission 139852514

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

    Oh great i didn't knew that it is some technique. Well i discovered already discovered technique.

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

      Well, it only becomes "technique" when you prove it's complexity.

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

The Rating Result?

→ 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 +3 Vote: I do not like it

looks like problem A was the only problem nitin_05 could solve without buying solutions. XD

he got skipped except A

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

    That problem not being skipped has worked to his disadvantage.

    If all the solutions would have been skipped then he would have no valid submission and the round would become unrated for him. However the solution for problem A not skipping means that the round is rated for him and due to only 1 correct submission , there's a huge negative delta.

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

Hello

I was suspected to cheat on the problem A with Shanto65 and atau004.

As you can see in this problem, it is very probable the everyone use this idea(and use a variable called cnt).

Dear codeforces please review this again(by the way i didnt use ideone or something like that).

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

Fake Plagiarism check to ban me from my own account. TheThinker_08. This has now happened several times. What you cant even write your own code now. And The other guy @Paul_Liao_1457 got no penalty just cause his score is greater than mine. please just look into this I didn't do anything wrong or copy from anywhere still got a plagiarism check and got banned just what is this

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

    Why I didn’t get penalty is because I solved the problem earlier than you.

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

I have a question about E. in my opinion i have O(n) solution, but it gets TL at 5th test, can someone tell me what's wrong? Is it solution or it's just Python can't make it.

https://codeforces.net/contest/1620/submission/139826532

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

    You are right about time complexity of your solution. What you are missing is that using input() for 500_000 of entries is too long. Look into other solutions to see "fast input" for python. Here is your solution with 1 variant of fast input: 139998877

    PS. And this fast-input: 139999694 I have just found in sur's solution is even better — it just made my solution twice faster. Thought, you should be careful with what you get — there will be unprintable symbols in your input.

    → Reply