Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### awoo's blog

By awoo, history, 3 months ago, translation,

Привет, 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, Klyaksa, lankin.i, Fanarill, stAngel and DmitriyOwlet. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

• +180

 » 3 months ago, # |   +49 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.
 » 3 months ago, # |   0 fifa frfr :{
 » 3 months ago, # |   +40 Codeforces Round World Cup 2022 (Div. Final)
•  » » 3 months ago, # ^ |   +87
•  » » » 3 months ago, # ^ |   +3 I am thinking of doing both.
•  » » » » 3 months ago, # ^ |   0 Yeah, when I wirte half of the div3, the cheer of goal absorbed me gave up div3 but went for world final cub.:D
 » 3 months ago, # |   +22 FIFA WC Finals:( If possible can change the timings pls:(
•  » » 3 months ago, # ^ |   +20 look my name
•  » » » 3 months ago, # ^ |   +9 my man waited whole life for this
•  » » 3 months ago, # ^ |   0 YES (●'◡'●)
 » 3 months ago, # |   +9 Hope to become Blue now!
•  » » 3 months ago, # ^ |   0 UPD: Didn't :C
 » 3 months ago, # |   +11 Please change the contest starting time if possible. At the same time, the FIFA World Cup Final of 2022 will take place.
•  » » 3 months ago, # ^ |   +1 how about changing thw world cup timings:)
•  » » » 3 months ago, # ^ |   0 I think that 60 percent of the participants will choose football
 » 3 months ago, # |   +8 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
•  » » 3 months ago, # ^ |   0 yes me too
 » 3 months ago, # | ← Rev. 2 →   +2 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
 » 3 months ago, # |   +4 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).
•  » » 3 months ago, # ^ |   -8 Messi is gonna lose and cry
•  » » » 3 months ago, # ^ |   0 Hope it would not be No more heartbreak
•  » » » 3 months ago, # ^ |   -7 Shut up... Messi will win Tonight in his last world cup dance...
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 this didn't age well. Argentina ftw.
•  » » » 3 months ago, # ^ |   0 Sad bro
•  » » » 3 months ago, # ^ |   0 Nerd guy smiling emoji
 » 3 months ago, # |   +18 I think round #839 will be poorly attended
•  » » 3 months ago, # ^ |   +13 Just put your pics all into a spoiler so that they don't occupy much room :) .
•  » » 3 months ago, # ^ |   0 I'm not good at playing football.
•  » » 3 months ago, # ^ |   +1 quick delete :)
•  » » 3 months ago, # ^ |   0 small black son want to eat the prison rice ?
•  » » 3 months ago, # ^ |   0 eat not eat deep-fried dough cake？
 » 3 months ago, # | ← Rev. 2 →   +4 Surely going to miss the round(FIFA World Cup Final).
 » 3 months ago, # |   0 I hope that this will be easy for every one.
 » 3 months ago, # |   0 Going to miss the round for FIFA Final :). Best of luck guys. Will see you on tomorrow's DIV-2 :)
 » 3 months ago, # |   0 Reschedule it please.
 » 3 months ago, # |   0 Considering the FIFA World cup final, if possible, please reschedule this round.
 » 3 months ago, # |   0 Please reschedule the round.
•  » » 3 months ago, # ^ |   0 Please awoo at least listen to our superhero Shaktimaan.
 » 3 months ago, # |   0 Kinda excited for my first unrated Div 3 round !!
•  » » 3 months ago, # ^ |   +1 Bro really... You should watch FIFA World Cup Finals. (Messsssiiiiii)
 » 3 months ago, # | ← Rev. 2 →   +1 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.
 » 3 months ago, # |   0 Don't wanna miss the world cup nor the div 3 contest. Is there any possibility to change the start time to 2 hour earlier?
 » 3 months ago, # |   +33 The only way to watch the World Cup Final is AK this round in 25min.
 » 3 months ago, # |   +3 We need more Div 3 and possibly Div 4 rounds. I find Div 3 problems more interesting.
 » 3 months ago, # |   0 This contest is going the have the least submissions!
 » 3 months ago, # |   0 Div 3 > FIFA World Cup change my mind
•  » » 3 months ago, # ^ | ← Rev. 9 →   0 Yeah it depends upon ur rating
 » 3 months ago, # |   0 You can do anything, just don't give up!
 » 3 months ago, # |   0 Extra ratings to those who sacrifice World Cup finals for this round . Hehe
 » 3 months ago, # |   +7 Argentina!
•  » » 3 months ago, # ^ |   +2 Messiii!
•  » » 3 months ago, # ^ |   +1 vamos argentina
 » 3 months ago, # |   +1 Hoping for both +ve delta and Argentina win!!
 » 3 months ago, # | ← Rev. 2 →   0 How a bout the world cup final ?
 » 3 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 no
•  » » 3 months ago, # ^ |   0 I think it means that if you achieved CM or higher it will be unrated for you even if you are currently a Pupil for example.
 » 3 months ago, # |   0 lol
 » 3 months ago, # |   0 This is fourth of five Rated Contests in a row.
 » 3 months ago, # |   0
 » 3 months ago, # |   +5 Vamooos
 » 3 months ago, # |   0 The World Cup final is once every four years, but this round will be back soon, though I am sad -_-
 » 3 months ago, # |   0 Messi,Messi,Messi!!!!!
 » 3 months ago, # | ← Rev. 2 →   0 Heart Says Argentina but Brain says France. Messi Deserves atleast one.
 » 3 months ago, # |   0 can you change the time please... FIFA world cup final is happening..
 » 3 months ago, # |   0 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.
 » 3 months ago, # |   0 Skipping this one. Messi better be winning today.
 » 3 months ago, # |   +5 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.
•  » » 3 months ago, # ^ |   0 why do you consider yourself a failure ? You seem to do pretty good!
 » 3 months ago, # |   +16 Contest during the world cup final? What a great idea. Now Messi and Mbappe won't be able to write this contest :(
•  » » 3 months ago, # ^ |   0 They are on such level that they even require to write it.
 » 3 months ago, # |   0 ancara Messi
 » 3 months ago, # | ← Rev. 2 →   0 Nah bro, I thought the start time would be changed... Unfortunately I have to miss the contest, not gonna miss the wc final.
 » 3 months ago, # |   +3 Excited!! As this would be my first unrated div.3 (～￣▽￣)～
 » 3 months ago, # | ← Rev. 2 →   +1 This contest will have the least Argentinian participants of all time.
 » 3 months ago, # |   +10 Argentina!!!
 » 3 months ago, # | ← Rev. 2 →   +3 Solution for problem E: СпойлерLook 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 element only if 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 typeThere 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 before your opponent. In case there is only one element left and both opponents have to paint it, it is a stalemate and a draw. So if there are left elements only of third type, it is a draw.That leads to the solution:To any player to win, he needs to paint exclusively his and third 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<=2 First player wins2+3<1 Second player winsOtherwise draw.
•  » » 3 months ago, # ^ |   0 how to solve d?
•  » » » 3 months ago, # ^ |   0 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]. 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
•  » » 3 months ago, # ^ |   0 DID THE EXACT THING. I AM IMPROVING (´◡)
•  » » 3 months ago, # ^ |   0 Nice bro
 » 3 months ago, # |   0 I loved the problems this time around. Great contest!
 » 3 months ago, # | ← Rev. 2 →   0 How to solve D ?? I tried binary search but it did not work :( hints plz
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 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]$
•  » » 3 months ago, # ^ |   +14 Consider some index $ia_{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.
•  » » » 3 months ago, # ^ |   0 orz
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 3 months ago, # ^ |   +1 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!
•  » » » 3 months ago, # ^ |   0 my code for D hey bro i have applied a similar logic but it saying that jury has found answer but participant has not. can you please check my code where it is failing. thanks in advance.
•  » » 3 months ago, # ^ |   0 int main(){ int t; cin >> t; while(t--){ int n; cin >> n; vector a(n); for(auto &u : a){ cin >> u; } int l = 0, r = 1e9; for(int i = 1; i < n; i ++){ if(a[i] < a[i — 1]){ l = max(l, (a[i — 1] + a[i] + 1) / 2); } if(a[i] > a[i — 1]){ r = min(r, (a[i — 1] + a[i]) / 2); } } if(r < l){cout << -1;}else cout << l << ' '; cout << endl; }}
•  » » » 3 months ago, # ^ |   0 thank you bro.
•  » » » » 3 months ago, # ^ |   0 My pleasure
 » 3 months ago, # | ← Rev. 2 →   0 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.
•  » » 3 months ago, # ^ |   +13 skill issues tbh
 » 3 months ago, # |   0 how solve 3rd problem I was unable to implement it, can anyone explain it?
•  » » 3 months ago, # ^ |   +5 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.
•  » » » 3 months ago, # ^ |   0 Yes I also did the same
•  » » » » 3 months ago, # ^ |   0 Actually I was trying to print in one loop without use of any space, that's why it becomes too messy that I was unable to solve it.....
•  » » » 3 months ago, # ^ |   0 yeah!! got it, thankuu
•  » » 3 months ago, # ^ |   0 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
•  » » » 3 months ago, # ^ |   0 got it, thank you, can you help me to printing it in one loop without extra space
 » 3 months ago, # |   0 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?
•  » » 3 months ago, # ^ |   0 Your rating will update in few days.
 » 3 months ago, # | ← Rev. 2 →   +1 Why it fails in D taking middle between our element and first unsorted element and checkingif(that works)good else cout-1
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 3 months ago, # ^ |   0 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
•  » » 3 months ago, # ^ |   +2 Try it for [2,6,0,6]. Answer for it would be 3. I wasted a lot of time finding this one.
 » 3 months ago, # |   +4 This is fine...
•  » » 3 months ago, # ^ |   0 *Will benefit from the problems
•  » » 3 months ago, # ^ |   0 Same lol. Back to green
 » 3 months ago, # | ← Rev. 2 →   0 .
 » 3 months ago, # |   0 Where can i see test cases for D, it shows wrong answer but cant see on which test case is wrong answer?
 » 3 months ago, # |   +18 Overtime specifically for Codeforces!
 » 3 months ago, # |   0 Hacking Phase open in FIFA TOO ( ARG vs FRA) !! (30 min) extraaa... lesgoooo!!
 » 3 months ago, # |   0 Could anybody explain to me why and how char in my A problem solution(185801559) turn into integer?
•  » » 3 months ago, # ^ |   0 Actually You did minus of S[0]'s (ASCII VALUE) with the 0's ASCII value. it converted it into number.
•  » » 3 months ago, # ^ |   0
 » 3 months ago, # |   0 problems D was brilliant I am happy I was able to solve itperfect Contest if any one needs help in it donot hesitate to contact me here is my solution;185847933
•  » » 3 months ago, # ^ |   0 I too solved it but 5 minutes after the contest ;(
•  » » » 4 weeks ago, # ^ |   0 ooh
 » 3 months ago, # |   +2 I think problem D was way better than problem E.
•  » » 3 months ago, # ^ |   +1 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
 » 3 months ago, # |   0 D was neat (and kinda set up by the idea of differences in C). Too bad I inexplicably decided to go off on a ternary-search-for-zero-inversions safari... woof.
 » 3 months ago, # |   +4 Argentina WON!!!
 » 3 months ago, # |   +3 THE MAGIC MESSI STRIKES AGAIN!!!!!!
 » 3 months ago, # | ← Rev. 5 →   +5 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?
•  » » 3 months ago, # ^ |   0 Hack them
•  » » 3 months ago, # ^ |   0 Alts/bots for bonus hacks.
 » 3 months ago, # |   0 Congratulations Argentina for winning FIFA World Cup 2022...
 » 3 months ago, # |   0 How to solve F or G? Can someone help?
•  » » 3 months ago, # ^ |   +7 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
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 3 months ago, # ^ |   0 Isn't it possible that when a value is flipped, it leads to the generation of more such values?
•  » » » » 3 months ago, # ^ |   +9 No, becauseif 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 itselfconsider 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.
•  » » » » » 3 months ago, # ^ |   0 Got it thanks man
•  » » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 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
 » 3 months ago, # |   0 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.
 » 3 months ago, # |   0 How to solve C and D ?
•  » » 3 months ago, # ^ |   +1 For problem C: СпойлерThe 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 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]$
 » 3 months ago, # |   0 problem F looks little scary by looking but it is very easy to solve.
 » 3 months ago, # |   0 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 BNow whoever changes color will lose this game because in the next turn other player can rearrange it.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Player 1 > Change 3Player 2 > Change 2Player 1 > Change 4Player 2 > Nothing to do/Change 1/Reorder, it won't matterPlayer 1 > Sort and Win
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   0 I chose to code instead of watching... hope you know what I am talking about :)
 » 3 months ago, # |   0 my rating is less than 1600,why this contest unrated to me?(sorry for my bad English)
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 the rating change is not coming,but it will coming soon
•  » » » 3 months ago, # ^ |   0 but i can't see myself in the ranklist without "show unoffical"
 » 3 months ago, # |   0 when will ratings update???
 » 3 months ago, # |   0 Still how much time for the ratings to get updated
 » 3 months ago, # |   0 Would my rating change or not?
 » 3 months ago, # |   -10 Those who participated in this round please get life because it looks like it matched the world cup finals lol.
•  » » 3 months ago, # ^ |   +10 not everyone enjoys watching football
•  » » » 3 months ago, # ^ |   -8 yeah dumbs probably don't watch world cup finals
 » 3 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 3 months ago, # |   0 I submitted this code. This work on my laptop but not in Codeforces. https://codeforces.com/contest/1772/submission/185900333
•  » » 3 months ago, # ^ |   0 This is because you don't know how to use STL functions.
 » 3 months ago, # |   +3 I happily ruined my entire contest by watching the FIFA final, but that was worth it!
 » 3 months ago, # |   0 I remember that my rating increasesd by 100 in Codeforces Round #839 (Div. 3) . But now it shows that it has only increased by 99 . Why did it decreased by 1