Привет, 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

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.

Codeforces Round World Cup 2022 (Div. Final)

I am thinking of doing both.

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

look my name

my man waited whole life for this

Hope to become Blue now!

UPD: Didn't :C

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

how about changing thw world cup timings:)

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

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

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).

Messi is gonna lose and cry

Shut up... Messi will win Tonight in his last world cup dance...

this didn't age well. Argentina ftw.

Sad bro

I think round #839 will be poorly attended

Just put your pics all into a spoiler so that they don't occupy much room :) .

quick delete :)

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

Kinda excited for my first

unratedDiv 3 round !!Bro really... You should watch FIFA World Cup Finals. (Messsssiiiiii)

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.

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

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

This contest is going the have the least submissions!

HAHAHAHAHAHAHAHA

Yeah it depends upon ur rating

Argentina!

Messiii!

vamos argentina

Hoping for both +ve delta and Argentina win!!

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?

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 beratedfor you.So if your rating was >= 1600 it wont get affected.

lol

Vamooos

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

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.

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.

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

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

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

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

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

Argentina!!!

Solution for problem E:

SpoilerLook at the problem more like a race between two opponents.

At first let's mention that:

first operation must be applied only when we can make the array sorted and instantly win, otherwise it's just a waste of time. Also we have to paint elementonlyif it isn't on the right position for us.Secondly divide elements of the array that have to be painted in 3 types:

Only first person needs to paint this element to win.

Only second person needs to paint this element to win.

Both players need to paint this element to win.

For example for the first sample array: 1 2 4 3:

There are 0 elements of first type

There are 2 elements of second type (1,2)

There are 2 elements of third type (4,3)

So to win the game you should paint all the elements that you have

beforeyour opponent.In case there is only

oneelement left andbothopponents have to paint it, it is a stalemate and a draw. So if there are left elements only ofthirdtype, it is a draw.That leads to the

solution:To any player to win, he needs to paint exclusively his

andthird type elements before his opponent finishes exclusively his elements. That corresponds to the formula where I used numbers to represent the types of elements.1+3<=2First player wins2+3<1Second player winsOtherwise draw.

how to solve d?

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

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

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

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]$$$

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

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.

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?

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!

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.

skill issues tbh

how solve 3rd problem I was unable to implement it, can anyone explain 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.

Yes I also did the same

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

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?

Your rating will update in few days.

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

if(that works)good else cout-1

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

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

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

This is fine...Same lol. Back to green

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

Overtime specifically for Codeforces!

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

I too solved it but 5 minutes after the contest ;(

ooh

I think problem D was way better than problem E.

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

Argentina WON!!!

THE MAGIC MESSI STRIKES AGAIN!!!!!!

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?

Hack them

How to solve F or G? Can someone help?

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

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

Run simple topsort in your graph, where edges contain information about which positions are changed. https://codeforces.com/contest/1772/submission/185841864 Constructing answer is a bit troublesome yeah.

Also, finding longest path in general graph is NP-Hard, but in this graph topological sort is also the longest path.

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

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

010 1 0

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

Got it thanks man

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.

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.com/contest/1772/submission/185846915

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.

How to solveCandD?For problem C:

SpoilerThe most important observation is: When $$$ k = n $$$ we can print all the numbers exactly once, so the only consecutive difference can be $$$1$$$. For an array $$$arr$$$ let's define it's characteristic to be $$$ x $$$ now when $$$ k = n $$$, $$$ x = 1 $$$.

Now we decrease $$$k$$$, when $$$k<n$$$ it means that there is some numbers that we can skip.

1: If there is $$$1$$$ number, then we can skip a number and have a gap of 1 and 2, obtaining a $$$ x = 2 $$$

2: If there is $$$2$$$ numbers, we can either skip $$$1$$$ number twice or $$$2$$$ numbers once. $$$x$$$ is still $$$2$$$

3: If there is $$$3$$$ numbers, we can choose to skip $$$2$$$ numbers once and $$$1$$$ number once, $$$x$$$ is now $$$3$$$

We can define the difference between $$$k,n$$$ to be $$$y$$$

To obtain the number of different gaps, the best way is to find the least $$$num$$$ where $$$ \sum_1^{num} \leq y$$$

The elements of this summation is the gaps that you can use, simply skip a head by their magnitudes and print the rest of the numbers consecutively until you reach $$$ k $$$ integers.

For problem D:

SpoilerWe can maintain a range of $$$high = 1e9, low = 0$$$ and in each index we can check with the element ahead:

1- If the elements are equal we can skip

2- If the $$$a[i] < a[i+1]$$$, then we need to find the maximum number that when subtracted will make them be at the worst case equal.

3- Otherwise, we need to find the minimum number that flips $$$a[i]$$$ to be less than or equal to $$$a[i+1]$$$

We do that for each two elements calculate the required sum, if it is the high we need to calculate, take the minimum between it and the previous high, if it is the low that we need to calculate, take the maximum between the calculated low and the previous low.

If at some points $$$low > high$$$ is true then we have reached a contradiction. If the element we seek is higher than the $$$low$$$, then it is also higher than the $$$high$$$, if it is lower than the $$$high$$$ then it is also lower than the $$$low$$$, otherwise we can print any number in the range $$$[low,high]$$$

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

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

(sorry for my bad English)

the rating change is not coming,but it will coming soon

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

not everyone enjoys watching football

yeah dumbs probably don't watch world cup finals

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).I submitted this code. This work on my laptop but not in Codeforces. https://codeforces.com/contest/1772/submission/185900333

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

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