awoo's blog

Codeforces Round #839 (Div. 3)
By awoo, history, 2 years ago, translation, In English

Привет, Codeforces!

On Dec/18/2022 17:35 (Moscow time), Codeforces Round 839 (Div. 3) will start. This is a usual round for the participants from the third division. The round will contain 7 problems, which are mostly suited for participants with rating below 1600 (or we hope so). Although, as usual, participants with rating of 1600 and greater can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them. The penalty for a wrong submission is equal to 10 minutes.

We remind you that only the trusted participants of the third division will be included in the official standings table. As it is written on the blog which you can access by this link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. We would like to thank the testers of the round: ermukanoff, soup, lankin.i, Fanarill, stAngel and senjougaharin. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

Comments Comments (108)
| Write comment?
»
2 years ago, # |
  Vote: I like it +49 Vote: I do not like it

Was this round supposed to be Educational round (Div.2) and then problems turned out to be too easy?

Asking because these authors usually make Educational Div.2 rounds and not Div.3 rounds.

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

Codeforces Round World Cup 2022 (Div. Final)

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

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

      I am thinking of doing both.

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

        Yeah, when I wirte half of the div3, the cheer of goal absorbed me gave up div3 but went for world final cub.:D

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

FIFA WC Finals:( If possible can change the timings pls:(

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

Hope to become Blue now!

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

Please change the contest starting time if possible. At the same time, the FIFA World Cup Final of 2022 will take place.

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

Can't It get shifted to some other day as tomorrow is world cup final and this round is DIV 3 which happen once in a while so don't want to miss this round

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

To everyone asking to postpone the contest, BledDest said in a comment on another blog that they can't do that because the contest is going to be based on some other contest. Here is the comment

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

Please change the time of the contest It's FIFA WC final match. It's also High-voltage match .Please change if u can. It's also the last chance of Messi (The GOAT).

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

I think round #839 will be poorly attended

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

Surely going to miss the round(FIFA World Cup Final).

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

Kinda excited for my first unrated Div 3 round !!

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

    Bro really... You should watch FIFA World Cup Finals. (Messsssiiiiii)

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

awoo, FIFA World Cup Finals: If possible can change the timings please. I don't want to miss Messi's final and Div 3 Round.

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

The only way to watch the World Cup Final is AK this round in 25min.

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

We need more Div 3 and possibly Div 4 rounds. I find Div 3 problems more interesting.

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

This contest is going the have the least submissions!

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

HAHAHAHAHAHAHAHA

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

Argentina!

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

Hoping for both +ve delta and Argentina win!!

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

I see, that people between 1600 and 1900 rating are trusted participants. But a little higher it is said that above 1600 people can register only unofficialy. Does this contest affect rating for people between 1600 and 1900?

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

    Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

    So if your rating was >= 1600 it wont get affected.

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

lol

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

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

Vamooos

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

Heart Says Argentina but Brain says France. Messi Deserves atleast one.

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

If that wasn't the last world cup of Messi, I surely would participate in the contest. Got to see the match. Best of luck for those who are attending. And best of luck for Team Argentina.

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

Thankyou awoo for keeping this at the same time of FIFA World Cup Final. I can't watch the match because of anxiety. So, it's good that I'll have something else to do. Vamos Argentina! Messi is the GOAT regardless of the outcome.

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

Contest during the world cup final? What a great idea. Now Messi and Mbappe won't be able to write this contest :(

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

    They are on such level that they even require to write it.

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

Nah bro, I thought the start time would be changed... Unfortunately I have to miss the contest, not gonna miss the wc final.

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

Excited!! As this would be my first unrated div.3 (～￣▽￣)～

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

This contest will have the least Argentinian participants of all time.

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

Argentina!!!

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

Solution for problem E:

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

    how to solve d?

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

      consider two adjacent elements. for a particular value of x the element will flip. by flip I mean their sorted-ness will reverse. find this flip value for all adjacent elements. there are two kinds of adjacent pairs — 1)ones that are v[i]<v[i+1] and 2) ones that are v[i]>v[i+1]. the max flip of all second kind of pairs should be less than min flip of all first kind of pairs thats what i did. also find x accordingly

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

    DID THE EXACT THING. I AM IMPROVING (´◡`)

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

How to solve D ?? I tried binary search but it did not work :( hints plz

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

    Find the valid range of $$$x$$$ s.t. $$$|a[i]-x| \leq |a[i+1]-x|$$$ when $$$a[i] < a[i+1]$$$ and when $$$a[i] > a[i+1]$$$

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

    Consider some index $$$i<n$$$.

    • If $$$a_i<a_{i+1}$$$, this pair will remain in sorted order for all $$$x\leq \lfloor \frac{a_i+a_{i+1}}{2}\rfloor$$$
    • If $$$a_i>a_{i+1}$$$, this pair will become sorted for all $$$x\geq \lceil \frac{a_i+a_{i+1}}{2}\rceil$$$

    By iterating over the whole array, we can generate a lower bound and an upper bound for $$$x$$$. If at any point we require $$$x$$$ greater than the upper bound or lower than the lower bound, it's impossible. Otherwise we can return any number within the range obtained.

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

      How to think about these tricky things? On some days/contests I am to find these but on other days/contests not. Due to this, I am struggling between specialist and pupil. How do you come up with these in every contest?

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

        Speaking from my experience, upsolving and lots of practice helps :)

        After doing a few similar problems you'll start to notice common methods of approach and get a feel for which of them is most effective in each type of problem. During the contest try to find the most suitable approach, or just try them all until you find one that works.

        For this particular question I was trying out simpler cases, my thought process went like this:

        • If the array is sorted in reverse, then any $$$x$$$ larger than the first value will work.

        • If we have an unsorted section like 4 2 6, we need to find a value between 2 and 4.

        • Instead of considering the whole array, can we consider parts of it and find bounds for $$$x$$$?

        Then I worked out the algorithm in my earlier comment. A more experienced contestant might be able to immediately see that we consider pieces of the array due to having solved similar problems with that approach earlier or having seen the technique mentioned in an editorial. Hope this helped you!

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

Solved A/B/C in 20 minutes, then misunderstood D and coded up a wrong solution, and then keep getting stuck with E with a solution I could've sworn was correct, and fixing it 1 minute after the contest. Sigh.

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

how solve 3rd problem I was unable to implement it, can anyone explain it?

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

    I can't prove my solution but I just printed 1, 2, 4, 7, 11, 16... <= n for each case and then inserted the k greatest leftover numbers at the end of the array and sorted. I figured I maximize the number of distinct differences this way and it's better to fill in the extra k with larger numbers than smaller numbers because they have less of a chance of messing the array up.

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

    Start from the last index and make it equal to n. Let's keep track of the last used difference and call it P. For each i such that 1<=i<k check if a[i+1]-P-i+2 is greater than 0. If it is true, then a[i]=a[i+1]-P+1. Else a[i]=a[i+1]-1

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

Hi! This is my first CodeForces contest, and I was expecting that this would result in some rating for me, as the notification email said rated for < 1600. I completed the contest, but it says unrated on my profile. Why is this?

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

Why it fails in D taking middle between our element and first unsorted element and checking

if(that works)good else cout-1

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

    You don't necessarily have to take the middle element it actually is the bound. For example if you have 3,11 middle element is 7 which implies any x<=7 can be the answer similarly if it is 11,3 any x>=7 can be the answer You can find out the final range of x which satisfy the condition by changing the upper and lower bound considering each pair of elements

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

    I Do it like checked if 5 x x x 5 Then between the two same , all have to be same since border is same on applying opeartion

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

    Try it for [2,6,0,6]. Answer for it would be 3. I wasted a lot of time finding this one.

    → Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it
This is fine...
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can i see test cases for D, it shows wrong answer but cant see on which test case is wrong answer?

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

Overtime specifically for Codeforces!

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

problems D was brilliant I am happy I was able to solve it
perfect Contest if any one needs help in it donot hesitate to contact me here is my solution;185847933

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

I think problem D was way better than problem E.

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

    I feel the same after seeing E I cannot figured out it in contest as got exhausted after solving D but E was way easy than D

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

Argentina WON!!!

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

THE MAGIC MESSI STRIKES AGAIN!!!!!!

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

Why did a lot of guys put

if(t==1) return 0;

in A, which actually gives a wrong answer if t = 1. Is it just a coincidence or is there some hidden technique that they tried to use and it failed?

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

How to solve F or G? Can someone help?

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

    For problem F: The first observation is that if we count the number of positions whose values can be flipped in each of the copies, the copy with the highest count will be the initial one and the count of subsequent copies will decrease. So we now know in which order the copies are taken (I used a max heap for that). Then for individual operations, we compare the current copy with the last copy and the positions where the value is different is the position where operation 1 was performed. And operation 2 is performed for each copy after all operation 1s.

    here is my solution 185868920

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

      Nice.

      My thoughts were that it is easy to determine for any two pictures whether one can be obtained from the other, so we can build a graph on all pictures and find the longest path, than figure out the transitions on the edges of the path...

      But it was too troublesome to implement, so I gave up

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

      Isn't it possible that when a value is flipped, it leads to the generation of more such values?

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

        No, because

        if a position is being flipped, then all its 4 neighbors are already the opposite value, So the position we are flipping will never be adjacent to the same value in that case it would be invalid to flip itself

        consider an example to understand what i am trying to say
        0 1 0
        1 0 1
        0 1 0

        By changing bolded 0 to 1 would never lead to a situation where it shares a side with a 0.

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

      For problem G: Firstly sort the array. now, let our cur_rating be rating when we just win the match with the ith element.In the beginning the value of cur_rating is x. If we are at ith position and a[i]>cur_rating, then we have to cross the barrier by gaining a[i]-cur_rating for move further.if we are at ith position, we can win all the games with all players having index less then i[(i-1) player] and we will lose all the games with all players having index greater then or equal to i [ (n-i-1) player] so total gain we can get in 1 loop is simply (i-(n-i)). now we can calculate total numbers of games for crossing a[i]-cur_rating.if our cur_rating will reach at y we will stop.At the end of loop we are at the stage when we can win with every element.

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

    Problem G: Let $$$bonus$$$ be the ratings of $$$x$$$ getting in all games.We can calculate $$$bonus$$$ by doing binary search until $$$bonus$$$ has no change.If $$$ x + bonus \geq y$$$, the game ends.If $$$bonus - (n - bonus) \leq 0$$$, we cannot win the game.Find $$$f$$$ that $$$x + bonus * f \geq a_{bonus+1}$$$ ($$$a$$$ is sorted), which means we need repeat $$$f$$$ rounds and gain same ratings until we can get ratings from a new game.Note that $$$y$$$ may in $$$[a_{bonus+1}, x + bonus * f]$$$, so just add $$$bonus * (f-1)$$$ to $$$x$$$.

    My Submission:https://codeforces.net/contest/1772/submission/185846915

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

Problem D Solution : Basically I checked the case of a[i] > a[i+!] => found out the maximum a[i] — ( a[i] — a[i+1]) / 2. Why this? Because this pair will become sorted for all x >= (a[i] + a[i + 1] + 1) / 2, came to this conclusion after testing it out on paper. And then iterated over the whole array and subtracted each element with this resultant value. At last, I just checked the sorting condition.

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

How to solve C and D ?

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

    For problem C:

    Spoiler

    For problem D:

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

problem F looks little scary by looking but it is very easy to solve.

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

In the first TC of Problem E If the second player chooses to change 1st and 2nd element then game will end in tie. Am I missing anything? 1 2 4 3 1st Player turn: 4->Blue 1 2 B 3 2nd Player: 1->B B 2 B 3 1st P: 3->B B 2 B B 2nd P: skip B 2 B B

Now whoever changes color will lose this game because in the next turn other player can rearrange it.

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

    Going by your operations, once the array becomes B 2 B B, its the first players turn who can swap 4 and 3 which are blue. Since the array is now sorted, 1st player wins and the 2nd player does not get to make any more operations.

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

my rating is less than 1600,why this contest unrated to me?

(sorry for my bad English)

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

Those who participated in this round please get life because it looks like it matched the world cup finals lol.

→ Reply
»
2 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
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I submitted this code. This work on my laptop but not in Codeforces. https://codeforces.net/contest/1772/submission/185900333

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

    This is because you don't know how to use STL functions.

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

I happily ruined my entire contest by watching the FIFA final, but that was worth it!

→ Reply