atodo's blog

Codeforces Round #771 (Div. 2)
By atodo, 3 years ago, In English

Hello, Codeforces!

I am happy to invite you to Codeforces Round 771 (Div. 2), which will take place on 14.02.2022 17:35 (Московское время). The round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 6 problems. The problems were authored and prepared by me.

I would like to thank the following people who made the round possible:

I hope you have no plans for Valentine's Day find the problems interesting and enjoy the round. See you in the standings! ❤

Scoring distribution: $$$500-750-1250-1750-2500-3250$$$

UPD: Thanks to ak2006, video editorials for some of the problems will be available on his channel after the round.

UPD: Editorial is out!

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

Comments Comments (138)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +137 Vote: I do not like it

I hope you have no plans for Valentine's Day

are you cursing us

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

Sorry but I have plans for Valentine's Day — participating in your round! ❤

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

Do Programmers celebrate valentine's day? :)

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

Looks like the Codeforces Round 771 will be my Valentine this time:)

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

As a tester, good luck and enjoy problems!

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

    My plans for valentines day were to take this contest.

    Now that I got the notification that I tested it, I no longer have plans :(

    Good luck and have fun to the rest of you.

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

I hope you have no plans for Valentine's Day .

Now Codeforces is also playing with my emotions :(

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

sorry losers, I have plans for Valentine's Day :>>

→ Reply
»
3 years ago, # |
  Vote: I like it +90 Vote: I do not like it
meme;)
→ Reply
»
3 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Wait, What's Valentine's Day?

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

Expert (my ex) ,i hereby propose you to be mine again .❤

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

    Hopefully ,i won't FST on some problem and regain my love (expert) back. Probably a happy valentines for me.

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

Sorry but I have plans for Valentine's Day

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

Valentine's day is for Div 1 only.

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

No Valentine's day -- lets write codeforces contest!

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

Codeforces Single's Round.

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

This contest may be easy than previous contest

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

She left me because I'm still newbie. :))

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

PinkieRabbit pls stop participate div.2 round to enjoy Valentine's Day with me because it's unrated for you but I'm important for you!

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

Hopefully, I can get back to specialist :)

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

Will it contain any interactive problem?

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

Goodluck at Valentine's Round #1

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

I hope I won't need my registration for this round and will enjoy the date with my gf...

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

I rather prefer cf rounds than a piece of chocolate! This round's a such nice present for me

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

I'm having a plan on Valentine and will also participate in the round.

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

Petition to rename contest to:- Singles Counting contest for cf

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

This round is like my Valentine's Day now see my Valentine goes good or bad

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

I have plans, it's my birthday!!

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

I have no plans for Valentine's Day hope problems are interesting! ^_*

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

Will AI participate in this round?I guess AI dose not have a girlfriend.

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

    Considering that AlphaCode is pre-trained on natural language processing models, I guess we could find a way to ask AlphaCode whether they have a girlfriend and it's likely their answer would be true :|

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

      Maybe he will be hanging out with google assistant on the google cloud :)

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

On February 14, 1946, the world's first general-purpose computer was born at the University of Pennsylvania in the U.S. Please spend more time with your computer on this special holiday!

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

As previous contests shows: [](https://codeforces.me/blog/entry/57721) [](https://codeforces.me/blog/entry/50404) [](https://codeforces.me/blog/entry/23515) [](https://codeforces.me/blog/entry/6677) Programmers usually don't remember the festival unless the announcement notices it...

So plz don't mention it next time(

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

Happy Valentine's Contest Day !

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

Yeah yeah you are right. I dont have any plan tonight except for the contest because no girls will like an anime-fan boy. : (

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

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

    thx, am on the cliff of leaving problem solving, but i will keep going forward now

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

    When your kid from the future comes back in time and threatens you to work hard, so that he can have a better life.

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

AIs have plans for Valentine's Day, so they won't participate in this round

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

In fact, my girlfriend's name is codeforces.

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

    Sorry to say, But I spent my most of time with codeforces only. (:

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

Let's see if Valentine brings some good fortune for us.

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

Thanks for arranging the contest on valentine's day. Single me at least find something to have some fun and make my day memorable.

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

Recently i came across the problem "Long Comparison" . Since i am new to competitive programming , i am solving more new questions to build my problem solving ability . Now when i submitted solution to this problem with my own approach , it gave "Run Time Error" with "Exit Code 3" . Can anybody tell me what is going wrong with the approach which i have submitted .

Problem : 1613A - Long Comparison My Submission : 146344211

Please give your precious advice .

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

    Hi, next time you can check the editorial of the contest, there is a tutorial button in the downright of problem page.

    About your submission, since $$$p$$$ can be really large, you cannot represent two numbers with type int (int only has $$$\le$$$ 10 digits).

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

POV — You have solved A B C and you are randomly roaming in the site and waiting for the contest to end.

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

Wtf problem E is not about segment tree(((

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

Is D long implementation or i am wrong :/

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

    Not particularly. I wrote a relatively lengthy bfs idea and even then its below 100 lines incl template.

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

    Came up with a solution literally 1 min after the contest ended. Now have to wait till system testing to see if it works lol.

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

Unfortunately, I found a hackable submission 146415862 of krishnagskr983 but when I clicked on the Hack button, the web started to load and never charged, so I couldn't hack it. I had 10 minutes before the contest ends, the time when I discovered the submission. I have sent the code before the contest ends to one clarification, proof that I could submit the hack. What can we do now? atodo MikeMirzayanov

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

    And another thing, a lot of times, when I open a link with ctrl+click for example, the page doesn't charge and stays white forever (ends to reloading). Anyone is experiencing the same?

    I'm experiencing the same:

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

How to solve C?

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

    Hint — if there is any $$$i \lt j$$$ such that $$$p_i \gt p_j$$$, $$$p_j$$$ will be part of some previously created component.

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

Hint for E?

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

    Hint for D?

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

      Think in reverse direction. Which squares were painted in the end? How does this help you to determine other squares?

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

Is there any solution faster than $$$O((N+Q) \log (N+Q))$$$ in E?

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

    I guess no. But seems you need to be careful with your constant. I had to optimize a lot and use fast input methods to squeeze my segment tree solution through.

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

My comments for each problem:

A. Not bad, but quite implementation-based problem. Unfortunately, I got FST. XD

B. Fine. It seems there are some hack on this problem.

C. Today I became second-solver of C. Yay!

D. Quite interesting.

E. How to solve it?

F. Read, but didn't thought deeply about it.

Also, I think the gap between C-D-E is a bit large.

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

    E: maintain the set intervals of contiguous same colored indices. When you are about to color a sub-array [l, r]:

    1. two intervals (one on left side and one on right side of the sub-array) each might get broken into two intervals
    2. intervals which are strictly inside the sub-array from our set will be gone
    3. one interval indicating the sub-array will be added to the set

    Suppose we have a BIT built on the values of the array. Whenever we "touch" an interval [L, R] of current color C in step 1 or 2, we will make sure this interval's values are up to date. Suppose, X = the sum of all updates happened to C after the last update on this interval. Then, we will add X to L and -X to R+1 on our BIT. So, basically we are keeping only the intervals which we are accessing up to date.

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

Took me like 30 min to solve C, but couldn't solve B. :(

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

    Frankly, I feel the idea used in B is very standard. I've heard $$$n + 1$$$ "is it sortable" problems that use this trick. If you don't know it, its probably tougher to think of.

    B - Hint 1
    B - Hint 2
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what are the hacks for problem B.

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

    Ig many solutions are gonna give TLE, because some peeps have manually swapped each element of the array, with a time complexity of O(N^2)

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

      Now I think I should have tried hacking instead of trying to solve D.

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

solved c, connected component will always be a subsegment. not sure if it's totally correct.

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

When processing operations in backwards order in D, how to avoid bfs / dfs? I see some participants have solved it with simple loops and I don't get how there is a guaranteed order with that.

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

How to solve D ? I noticed that for correct painting there must be consecutive 2 equal elements in every row & column. So I built a graph such that if consecutive element is to the right, I add edge to the (j+1)th element else to the (j-1)th element. Similarly for column. Then do topological sort. I also kept two arrays right and down stating if for the particular cell, the consecutive element for the row is to the right & for column to the down. And if not right, then while printing i will reduce the column number & similarly if not down, i will reduce row number. But this doesn't work. Could you help me where I got wrong ?

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

    My idea was a BFS backwards through the painting operations. Starting at the end, your 'next' (previous) operation must be a 2 by 2 square either of equal numbers, or of equal numbers which are unpainted (and any already painted numbers, since these are fixed now). Start with all the 'good' squares in a BFS queue, paint them, then paint any 'nearby' 2 by 2 squares which are now fine to be painted, and so on.

    If you reach the end of the queue and there are cells as yet not fixed, it's impossible. Otherwise print the operations back to front.

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

    lets say you have a $$$2 \times 2$$$ square of following configuration somewhere in your canvas...

     1 2
 3 3

    lets say your code pointed both cells to $$$(1,1) \to (2,1)$$$ and $$$(1,2) \to (2,2)$$$.

    but i guess in reality it should have been $$$(1,1) \to (1,2)$$$ and $$$(1,2) \to (2,2)$$$ or something but not the first case.

    how do you deal with such cases ?

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

    I was thinking along these lines for some time, I suspect very complex cases can occur for single cells or L shapes areas.

    As for the actual solution:

    • Suppose we're processing operations in backward order.

    • Lets call a "fixable" cell one that is coloured by a later operation.

    • We can colour a square without affecting later operation if all non-fixable cells in it are of the same colour.

    • It never makes sense to colour the same square twice since the later operation on the square will make the earlier one irrelevant.

    • Colouring a square can make at most the $$$9$$$ squares adjacent to it colourable now when they weren't before, so we can use a bfs to do this in $$$O(n ^ 2)$$$.

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

F is actually a nice problem, thanks! E is not bad too.

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

Quick idea of Problem D, but bad and buggy long code implementation due to my debugging ability

(UPD: The bottleneck is that I used scanf & printf instead of cin & cout with ios::tied which gets AC after the contest, that's really a lesson when I met the scale of input or output more than $$$1e6$$$.

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

Although I liked most problems Problem C was very very similar to this. I just copy pasted my code with one line modification. https://www.codechef.com/COOK137A/problems/ERASE/

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

I think it's insane to get TLE like that on problem B just because I am using python

146366116

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

the pretest cases for problem 2 are not at all good they can be a lot better-got tle while system testing if it would be during the contest, at least I would have tried fixing that at the time of the contest

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

Did someone leak a hackeable solution on B?

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

very disappointed by the problemset... Problem C was easier than B... Took me 15 min to solve C but even after hours can't figure out B... Setters should verify the difficulty level of any problem before rendering it....

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

    Problemset was godlike, only problem that wasn't that good was D, because it was heavy implementation based.

    But other problems? Really nice.

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

problem B...

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

146420483 Can someone please help me figure out why am i getting tle

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

Can anyone please tell me why my solution 146399384 takes so much memory, while similar implementations have very less memory. According to me, total array and vectors size included will be at max $$$2*n*m$$$ integers,which should not consume so much memory (242 MB).

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

Bad pretest (:

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

    You failing systests doesn't mean pretests are bad

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

      But they are bad. Quadratic solutions were passing on B, while the case (n, n-1, n-2,....), that have quadratic edges, was not on the pretests of C.

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

    Your code used a lot of memory indeed ! Pretest were fine . You are the first one i heard saying pretest are bad on problem C though . Yeah for B they allowed O(N^2) which later got fst

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

I guess pretests for problem B aren't that strong, for there is few test case containing duplicate.(Especially for sort based algorithms)

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

Actually I'd rather celebrate ENIAC Day than celebrate Valentine's Day as a competitive programmer.

P.S. though ENIAC Day is celebrated on Feb.15, ENIAC was announced to the public on exactly Feb.14, 1946.

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

Can anyone tell me how to optimise this one to avoid TLE I tried using DSU and to avoid O(n^2) complexities thought of a[I]>I and parent[I] is not =-1 i.r it isn't yet included in any of the connected components https://codeforces.me/contest/1638/submission/146477193

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

If we tweak problem A as : Given array is not always a permutation. I was wondering if is there any better ideas then N^2.

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

can someone explain to me how (https://codeforces.me/contest/1638/submission/146492255) these types of implementation for problem B works?

Sorry complete beginner here

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

    a way to solve problem B is to check whether the odd number sequence appeared in the origin array is non-decreasing, also the even number sequence.

    so lst[0] means the last number appeared in the even number sequence, as lst[1] means the odd number sequence.

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

    When you see a "x&1" operation you can see it as the same as "x%2". While bitwise AND operator (&) and MODULO (%) is a very different concepts, both expression above produces the same result

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

      Yep. People should just write x%2, the modern compilers don't need that extra hint. They can figure out using bitwise operator themselves.

      But sometimes we are just too used to the arcane versions.

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

I hope you have no plans for Valentine's Day

In fact, I did have plans: participating in another CP contest which overlapped with this one

... Why does everyone hold competitions on the same day ;-;

→ Reply