Привет, Codeforces!
В Dec/18/2022 17:35 (Moscow time) состоится Codeforces Round 839 (Div. 3) — очередной раунд для третьего дивизиона. В этом раунде будет 7 задач, по сложности подходящих для участников с рейтингом до 1600 (во всяком случае, мы надеемся на это). Но, конечно же, участники с рейтингом 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов.
Вам будет предложено 7 задач на 2 часа и 15 минут. Мы надеемся, что вам они покажутся интересными.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Раунд основан на задачах муниципального этапа Всероссийской олимпиады школьников в Саратове и Саратовской области, поэтому если вы участвуете в нем — пожалуйста, воздержитесь от официального участия в этом раунде.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Максим Neon Мещеряков. Выражаем свои благодарности тестерам раунда: ermukanoff, soup, lankin.i, Fanarill, stAngel и senjougaharin. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
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.
Yeah, when I wirte half of the div3, the cheer of goal absorbed me gave up div3 but went for world final cub.:D
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 :)
eat not eat deep-fried dough cake？
Surely going to miss the round(FIFA World Cup Final).
Kinda excited for my first unrated Div 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!
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 be rated for 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!!!
Wow, i am so impressed. Haven't seen such decent problems in a while, great work!
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 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 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 wins
2+3<1 Second player wins
Otherwise 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 (´◡`)
loved the problems. Solved 5, max till now in div3. Hoping to be Specialist
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.
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://mirror.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 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.
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://mirror.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 solve C and D ?
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<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:
We 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.
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.
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.
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://mirror.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!