Technocup 2022 — Elimination Round 2 and Codeforces Round #755 (Div. 1, Div. 2)
By isaf27, history, 3 years ago, translation, In English

Hi all!

This weekend, at Nov/14/2021 09:05 (Moscow time) we will hold Codeforces Round 755 (Div. 1, based on Technocup 2022 Elimination Round 2) and Codeforces Round 755 (Div. 2, based on Technocup 2022 Elimination Round 2). They are based on problems of Technocup 2022 Elimination Round 2 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

Have fun!

The scoring distribution:

  • Technocup: 500 — 500 — 1000 — 1500 — 2000 — 2500 — 3250
  • Div1: 500 — 1000 — 1500 — 2000 — 2750 — 3750
  • Div2: 500 — 500 — 1000 — 1500 — 2000 — 2500

The round is over. Congratulations to the winners:

Technocup

  1. Artyom123
  2. turmax
  3. Kirill22
  4. jiangbowen_
  5. Kapt

Div1

  1. ko_osaga
  2. maroonrk
  3. xay5421
  4. jiangly
  5. uwi

Div2

  1. 1443356159
  2. int65536
  3. strongerthanspeed
  4. DSair
  5. nunu03

Editorial

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

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

Note the unusual timings

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

My first contest with green color , I hope I will do well, good luck every one .

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

11.35 am I would love to give the round if I woke up by thenಥ_ಥ who keeps round so early in morning that too on Sunday ಥ_ಥ ಥ_ಥ

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

    "who keeps round so early in morning that too on Sunday"

    A lot of people around the world usually have to wake up wayyyy earlier than 11:35am for a contest. It is what it is.

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

      I do understand that its just my pov not meant to offend anyone.(^◡^ )

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

We have to postpone contest a bit. No way I can wake up that early

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

Which approach is better for practicing problems in problemset: topic-wise or difficulty-wise?

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

    Difficuty wise , because when you are filtering questions according to a topic then you would already have an idea before even looking at the problem that this question can be solved using this perticular logic and this is not good, why i am saying that because when you are giving a contest you are unaware of the approach which is being used thats why it is better to sort according to difficlty then solve.

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

Sleep vs contest. Ape choose sleep.

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

It overlaps with Grand Prix of EDG :'(

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

The contest is right after Google kick start, look forward to it. (Finally a good time for NA competitors

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

    Wish I had read your comment sooner. I didn't realize the time was in 24 hr format :_(

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

google kick start (or) codeforces div2

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

Dare to join this contest just after Google Kickstart Round-H;)

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

Google kick stat round H plus codeforces round 755 makes me 5 hours of marathon coding competition.

UPD: It's the third time I become candidate master.

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

Overlaps with AHC006. If you fully participate CFR755, only 2h40m will remained for AHC006.

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

Scoring distribution still not announced.

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

very few registrations this time.

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

How can someone hack a problem even after I locked it ?

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

    After locking, you cannot submit again and can hack other participant's solutions. If not locked, you can submit again but cannot hack other participant's solutions.

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

    Thanks to this comment I hacked 7 people.

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

Sorry for asking this, but I accidentally submitted a WA after an AC. So the AC solution done before will be counted for results right? Or is last submission for that problem considered regardless?

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

    Your AC solution counts, check standings :)

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

What is the hack for C?

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

    1

    1

    1

    0

    I used this

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

    Multiple solutions passed which weren't intended. So basically it wasn't just one particular hack or idea, but it was just weak pretests.

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

    input:

    1
1
1
0

    This will hack the code that only judges the case of no solution is $$$b_i-a_i>1$$$.

    But sadly I found this after I locked my solution :(

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

    I noticed two.

    1. Not considering index '0'.
    2. Taking absolute difference of a[i] and b[i].
    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Div1B/2D is a really nice problem, bricked for a really long time trying to figure out how to solve the problem in just 1 pass of binary search, but the observation needed to solve it is cool af.

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

    How do you solve it in one pass?

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

      Difference between $$$query(1, k) - query(1, k-1)$$$ is equal to the $$$k-j+1$$$.

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

        Thanks :) Couldn't figure out during contest but the idea is actually very beautiful nonetheless.

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

      Binary search on ranges of the form $$$[1, x]$$$ to find $$$k$$$ (smallest index with same number of inversions as range [1, n]).

      Now lets realize that since all elements in $$$[i, j - 1]$$$ are smaller than those in $$$[j, k]$$$, the number of inversions is exactly $$$\frac{y \cdot (y - 1)}{2} + \frac{z \cdot (z - 1)}{2}$$$ where $$$y = (j - i)$$$ and $$$z = k - j + 1$$$.

      Now if we query the range $$$[1, k - 1]$$$, the number of inversions is $$$\frac{y \cdot (y - 1)}{2} + \frac{(z - 1) \cdot (z - 2)}{2}$$$, or exactly $$$z - 1$$$ less than the previous value.

      So we now have $$$z$$$ and can get $$$j$$$ from it.

      We also have the total, so we can just binary search to find $$$y$$$ that satisfies $$$\frac{y \cdot (y - 1)}{2} = total - \frac{z \cdot (z - 1)}{2}$$$. So we can also get $$$i$$$.

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

        Also the part of binary searching y can be eliminated using the main observation by querying [1, j-1] and [1, j-2] and subtracting the second from the first to know length of [i, j-1].

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

        If you binary search two times then won't the total number of queries be $$$2 \log_2(N) \approx 60$$$ ?

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

          The second binary search in his comment is to solve an equation not to query.

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

          The second binary search is finding the largest $$$y$$$ such that $$$y \cdot (y - 1) \leq total - \frac{z \cdot (z - 1)}{2}$$$. Just a local calculation, no queries or anything.

          You can just do $$$\sqrt{total - \frac{z \cdot (z - 1)}$$$ and check close by values if you aren't paranoid that will somehow make you FST lol.

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

Fragile pretests on C lol. Hacked 8 submissions

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

    ape hack . ape happy

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

    I hacked 3 using following test:

    1

    3

    4 4 4

    3 3 3

    Anc I jumped from rk~150 to rk~50 lol

    Is that weakppforces?

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

The pretests in C were reasonably weak. I hacked my way from ~1000 rank to ~350 (And so did a lot of other people).

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

hackfor C es!

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

Is div-2 D some sort of ternary search?

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

ko_osaga did it again!

Where is E from?

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

    Hi, it's NEERC 2015 Northern Subregional K. It is not very equivalent, but the main observation for that problem can be applied directly. Shoutout to ainta for recommending me this problem.

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

    Also, at least one problem in CF and a recent WF problem related to "distance to line", the only difference is to handle case when distance to segment is to one of two ends, it is easy by sweeping and two pointers.

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

Hi,

Even though I probably didn't have the right algorithm on the E, the statement was a bit ambiguous on the issue of size 1 segments and other details (e.g. can we increase the ends without increasing the only values adjacent in the subsegment). I rather liked this exercise even if my performance on this competition does not exemplify me :)

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

Problem C and D are easy to come up with . But really hard to implement and debug ...

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

    Agreed, on problem C it took me:

    • 5 mins to get rough idea
    • 10-15 mins to work out all technical details
    • 40-45 mins to implement and debug till it passed samples
    • 10 mins to write brute and stress test when I got WA2.

    The basic idea of parity sums and prefix not becoming negative is fairly standard. I'm pretty sure there was Div2 problem a while ago that required exactly those two observations.

    Edit: Apparently Div1C is extremely easy to code if you use k-th order statistics. See this submission — 135379742.

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

      Thanks , I know few about pd_ds. I think I need to learn more about it .

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

    Could you please share any hints about problem div1 C, thank you very much.

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

      Hint: you can perform the operations from left to right , and find out when the array is possible to clear . Use some data structure to maintain it !

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

I'm interested in what happened to antontrygubO_o

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

Today I did my first hack on Codeforces. Felt a little too good to be evil, lol.

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

    Can you please explain the logic behind solution of problem B??

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

      First thing to figure out is that when you make rectangles of dimension 3*1 you need minimum possible colourings. So, we divide the base rectangle into as any 3*1 rectangles possible and we will be left with (n%3)*(m%3) sized rectangle, now, the possible rectangles will be 2*2, 2*1 and 1*1 . First 2 cases will have half tiles coloured and the last case is prohibited so what we do here is we spare 4 tiles in one line and divide the rest all in rectangles of size 3. The remaining 4 will have 2 tiles coloured.

      If I was difficult to understand. Here is my solution- 135359905

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

Cries to death

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

Ready to get FSTd Solution to C cannot be so simple

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

I didn't manage to remove cheaters in previous rounds yet. I will do it soon, but as a result, it is likely outcome that someone will change their division of participation in round 755. Regardless of the new division (after removing the cheaters), your participation will be rated in the exact division that you actually participated in round 755. That is, even if after removing the cheaters you change the division, then round 755 will remain rated for you.

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

I am not upset that pretests of C were weak ,I am upset that I didn't attempt to hack

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

    I have the same feeling, I found the hack very soon but I was so scared to try because it was my first time trying to hack, by the time by I gathered the courage 3 hackable solutions were hacked in my room so I had only 1 solution to hack.

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

      Yeah I also would have felt little nervous as I never hacked before ( It always feels nervy in an unknown territory )

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

I wonder if Div2.C(Div1.A)'spretest is SO WEAK Because I add abs() and go through pretest as well

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

am disappointed because weak test cases in problem C

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

Hello All, just needed your attention here. I submitted C once and it showed me an accepted verdict again after a few minutes I again submitted with a slight different approach and it showed a passed verdict.Just when the contest got over I saw a skipped Verdict and queued verdict. May I know why it is happening so.

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

Is fact what solve with complexity O(n**2) getting AC in Div1C OK? 135376136

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

    Hacked. It seems that the test cases are too weak.

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

weakpretest :(

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

I never wanted be hacked more than now

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

Video Editorial for A

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -83 Vote: I do not like it
some downvoted words
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    A is difficult only if you failed your algebra class in school

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

      My point is not on A.I decided to solve it after D.

      now found it the worst decision ever.

      More,only 5000/9000 participants submitted A.It's not a good thing for cf.

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

A. Math, Was quite tough to me
B. It could just as well be A
C. It can be solved with one-liner, why is it C and why there are so many hacks and fst?
D. Nice problem, enjoyed solving it

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

    A. I still enjoy solving problems related to algebra, interesting for me.

    B. Problem was meh, div 3 type.

    C. Really bad C. This problem is meant for div 3A. How did this even...

    D. This problem looks interesting

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

For problem B, I realized we need to take as much as 1*3 as possible so my solution was based on that. I see some solutions like cout << (n*m+2)/3 << '\n'; how the solution got reduced to that !?

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

    Hi ! In fact the answer is ceil(n*m/3), and with few attempts, you can realise that this is equal to floor(n*m + 2/3).

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

    In total we have $$$n * m$$$ little squares. You mentioned right, that we need to take as much $$$1 * 3$$$ rectangle pieces as we can. Now $$$(n * m + 2) / 3$$$ is a way to find how much $$$1 * 3$$$ pieces we will have plus check if there is something left, so basically it is [ $$$(n * m) / 3$$$ + remainder ], where remainder is one if $$$n * m$$$ is not divisible by 3. That means that we are left with $$$1*2$$$ or $$$1*1$$$ rectangle and in both cases we will need to paint exactly $$$1$$$ more sell with blue

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

Thank this contest let me become a candidate master.

I think problems are good.

But the pretest of C was terrible and there were so many hacks.

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

I think D1D is just this problem with much harder implementation.

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

So weak pretests on problem C !!!

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

Huge difference between no of accepted solution div2 C and D. There should have another problem in middle difficulty.

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

Here are the video Solutions to the first 4 problems of Div-2 in Case you are interested.

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

Finally turned green..WohooooOOo

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

    Finally turned green after being specialist and expert. Wooohoooo

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

Why such a huge gap in the difficulties of (ABC) and D in div2..A newbie could also solve upto C and D was very tough for a specialist(maybe for an expert too)

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

    D was pretty much as always
    The gap is because C was easier than it should have been. In general C is intended for cyans

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

how come no editorials?

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

This has to be the most unbalanced div 2 round till date

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

Weak pretests for problem C :(

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

waiting for editorial.

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

My solution

Can anyone please tell me why this is wrong ?

It passed the pretest but now it is showing WA

I cannot even understand the test case it failed 

1
1
2
1

like why it is failing why its o/p is NO it should be YES isn't? Am i missing anything or my understanding of the problem is flawed?

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

Could anyone tell me what's wrong with my C code? I can not find out and I am wondering whether it is necessary to sort. 135383484

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

    try this TC and you'll realize why is it not working
    1
    2
    1 2
    2 1

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

Since editorial is late and for some reason no one is discussing solutions, could someone tell me what is the idea on how to optimize D2E(D1C) from O(n^2)?

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

I’ve always thought that rounds based on technocup are difficult and need a good knowledge of advanced algorithms, but i think this contest is a bit different , problems A,B,C are the same as a div3

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

    Any hints on how to solve B of div 2 :)

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

      Think of rectangles of rectangles of area 3

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

as a Python user, this contest was pretty disappointing. The tutorial Div1D and E solutions have essentially no hope of running in the given time limits in Python because of the absurdly large constraint allotments.

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

Pretty good contest, I like this type of style, only on suggestion, the gap between some problems might be a little too big.

→ Reply