By awoo, history, 6 months 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, mhq, Meijer, bthero,windazz, DimmyT, Batrr

We are looking forward to achieving incredible results with our new ICPC teams. One of them, Harbour.Backspace (MaksymOboznyi, mhq, Batrr), 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

»
6 months 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.

»
6 months ago, # |
  Vote: I like it -18 Vote: I do not like it

forward Kazakhstan

»
6 months ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

I just hope that I do not become Pupil again after this contest.

»
6 months ago, # |
  Vote: I like it -45 Vote: I do not like it

why edu round

»
6 months ago, # |
  Vote: I like it -42 Vote: I do not like it

Ready for badam badam kaca badam ;)

»
6 months ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

hope everyone has a good contest

»
6 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Always love educational round.

»
6 months 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!?

»
6 months ago, # |
  Vote: I like it -20 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

The start time in China is too unusual!

»
6 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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

»
6 months 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?!?
  • »
    »
    6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There are so many educational rounds! I wonder how to create problems so fast like this.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

best

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

SIUUU

»
6 months ago, # |
  Vote: I like it -22 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Why so negative?

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

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

»
6 months 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.

»
6 months ago, # |
  Vote: I like it -34 Vote: I do not like it

the round is shit

»
6 months ago, # |
  Vote: I like it -26 Vote: I do not like it

speedforces

»
6 months ago, # |
  Vote: I like it -26 Vote: I do not like it

C should not exist

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

    A was harder than C, change my mind lmao

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

      I was out of my mind watching people soved A within 5 min and i was still grinding on it at 45.

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

»
6 months 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.

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

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

      Thanks for the help i realized it when 2 minutes where left. and was not able to solve.

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

      Why is the ordering not like this? What am I missing?

      a ab ba abb bab bba abbb babb bbab bbba abbbb babbb bbabb bbbab bbbba abbbbb babbbb bbabbb bbbabb bbbbab bbbbba abbbbbb babbbbb

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

        take the strings in a vector, sort it, the string will be lexicographically arranged.

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C is in a difference lever :v

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

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

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

    linked list

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

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

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

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

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

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

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

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

            • »
              »
              »
              »
              »
              »
              »
              6 months 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... :)

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

  • »
    »
    6 months 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.com/contest/1620/submission/139814623

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

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

»
6 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Can E be solved with some modification to dsu?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
    • »
      »
      »
      6 months 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?

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

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    No

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

    Actually, you can , if you hack someone else's solution whose ranking above yours.

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

      OK... If predictor is right I need 5-7 more delta to become expert. Roughly, how many solutions should I hack to get it?

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I eagerly wait to know the author of problem D

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

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

»
6 months 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

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

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

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it
  • »
    »
    6 months 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.

»
6 months 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.

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

12 wrong submissoins on C. I just want to die

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    please don't die

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

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

»
6 months 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

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +75 Vote: I do not like it

    no, there is no way to pass test case 5

»
6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

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

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

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

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          6 months 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.

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

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

            thnku very much

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Getting ready for a -100 LOL :p

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand the gap

»
6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve A?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Please don't ask me :((

  • »
    »
    6 months 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
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so tight constraints! :/

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

solved D after contest ended 3min :D

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No greedy,that I cannot solve any problems.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell how to solve c?

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

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

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

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

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

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Because your complexity is not good?

    • »
      »
      »
      6 months 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?

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

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

          Ok I understand now, Thanks for such a clear explanation

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    never use unordered_map anti-hashing testcases exist

    still your complexity is bad as -is-this-fft said

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

      Bad advice... If you want to pass anti-hash tests -> use your own hash function, genius

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it -11 Vote: I do not like it

        or just use map instead of implementing your own hash functions(in this problem array is better)

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it -90 Vote: I do not like it

WORST round EVER!

Emplemetionforces and speedforces combined

bruh

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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

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

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

»
6 months 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

»
6 months 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

  • »
    »
    6 months 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 :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D drove me mad...qwq

»
6 months 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.com/contest/1620/submission/139812356

»
6 months 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.

»
6 months 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.
»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I misread problem A and wasted 2 hours thinking about completely different problem :)

»
6 months 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.

»
6 months 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

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

  • »
    »
    6 months 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!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help with this submission?

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

»
6 months 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

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

    • »
      »
      »
      6 months 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)."

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

    • »
      »
      »
      6 months 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 ;_;

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

This "hack" is borderline hilarious.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

C >> D

»
6 months 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:

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

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

»
6 months 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

»
6 months 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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me with this code :

139843473

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F?

»
6 months 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

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you, too good to goodbye for 2021.

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

»
6 months ago, # |
  Vote: I like it -16 Vote: I do not like it
»
6 months 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?

»
6 months 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

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

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

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

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The Rating Result?

»
6 months 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).

»
6 months 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

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

»
6 months 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).

»
6 months 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

»
6 months ago, # |
  Vote: I like it -24 Vote: I do not like it

I am not able to log in to my account ushmitadutta but I am able to view it. Whenever I am wishing to log in it is showing the user disabled by the administrators. Whereas, I can see points have been added to the educational round. MikeMirzayanov Please Help.

»
6 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Hello awoo and MikeMirzayanov. This side ushmitadutta. I could see my account is there but I am not able to log in. It is showing disabled by the admins. Whereas, I can see my points getting added to the round. Please help.

»
6 months ago, # |
  Vote: I like it -24 Vote: I do not like it

MikeMirzayanov Please reply to our queries. I am not able to login into my account even though I am able to see the page. My account is ushmitadutta

»
6 months 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.com/contest/1620/submission/139826532

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