Hi!
On 04.07.2020 17:45 (Московское время) we will host Codeforces Global Round 9.
It is the third round of a 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.
The prizes for this round:
- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.
The prizes for the 6-round series in 2020:
- In each round top-100 participants get points according to the table.
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over all series get sweatshirts and place certificates.
Thanks to XTX, which in 2020 supported the global rounds initiative!
The problems of this round were prepared by a team of authors: adamant, antontrygubO_o, Ari, dengyaotriangle, hugopm, Kuroni, enoone, and Ynoi. We would like to thank the following people:
Our fantastic army of testers: aryanc403, abhayps, DeadlyCritic, Priyank, benson1029, 300iq, Guendabiaani, Arayi, thenymphsofdelphi, Monogon, ainta, Elegia, prabowo, spacewalker, ko_osaga, 244mhq, tranquility, EvenImage, Aaeria, teekteek, manjpatel, Almypa, tfg, and tzuyu_chou for helping greatly in improving this round's balance and quality!
gamegame and dorijanlendvaj, for their help in improving the humor of the round.
MikeMirzayanov for the Codeforces and Polygon platforms.
You will be given 2 hours and 30 minutes to solve 9 problems, and we highly encourage you to read all of them :)
To save testers the work of writing their opinion in the comments, we have compiled some of their opinions for them!
Good luck!
UPD: Score distribution:
500 — 750 — 1500 — 1750 — 2000 — 2000 — 2250 — 2750 — 4000
UPD2: Editorial
UPD3: System tests have finished, congratulations to the winners!
As a tester, give me contribution.
You are so honest. Otherwise, most of time tester tries to gain contributions by just commenting something shit....
Now, this is the most upvoted comment after Is it rated?
Full List
so let's make it the most upvoted comment.
Now it became the most upvoted one. :)
I'm so jealous =P.
U should be happy about it that the testers are getting more attention than the problem setters. :=)
Everything is good and all but
what's up with your handle 055D
It is now the most upvoted comment !!1!!1!
The only thing I remember about Monogon is that his first ever contest after being such a beauty was ruined due to long queues and finally the round became unrated. Awaiting another round from you.
He tested the last round too.
ok
Sorry for that..
You are now in top 10 contributors. Cong!!
may be for the first time a tester is going to get more contribution than the setter xd
need 247 more only :P
Sorry for that.
The most upvoted comment ever?
If only herd immunity was as easy as herd behaviour...... P.S. you have my vote.....
I hope Monogon prepares a round after gaining such support from the community. We will try to make the contest announcement blog the most upvoted blog on CF.
You have it, >2000 upvotes :D.
As the most upvoted comment in history, I think this proves that the greedy works.
Damn! Even, most of the "contest announcement" blogs have less upvotes.
Would it break the tourist's global round 5 record?
This has to be a record of some kind.
Can monogon's comment beat tourist's rating someday? =O
AC Round #3
What is AC Round ?
AC is a discord server for competitive programmers. Most of the authors/testers of this round are members of the server. This is the third round made by AC members, here and here are the first two rounds.
how do u get the link for the server?
this is the link.
Thanks for the link :)
This has to be one of the best contest announcement.
I am not tester, but i strictly reccomend you to participate in this contest!
yes yes of course of course
I'm a tester, and this round is very good.
Why am I getting downvoted? I'm stating my opinions as a tester.
Cause everyone saw that, you are not in the tester list :v
As a participant, I need more time to recover from the previous contest.
They stole my contribution =(.
Thanks for giving me contribution =).
Ok then
very comedically humorous Ari
Is feedback meant for frightening us?
As a participant, I am already scared
Finally this day has came, a round with adamant as an author.
Oh god I was planning to join this round :(
Anal is short for analytic, right? ;)
Yeah. He has given a lecture on this subject at mwj.
you saved my mind from burning
and oral is for oralytic
Bruh, obviously ORAL stands for Outstanding Requisition Analysis Report.
thanks for the meme!
The announcement just ensured that one more time we are gonna miss MiFaFaOvO vs tourist match.
Tbh, it looks more like ecnerwala vs tourist to me. Just an opinion tho.
I don't get why you guys are more interested in tourist than yourself.
Is that why you are green/cyan?
I find inspirations seeing the success of some great coders so that i am interested about them.You better focus on your own success (as you are a colorless or a fake account).
I hope notgonnalie is a human, not a colorless or a fake account...
Glad a real CF round is coming,last round killed my spirit...
Hope this doesn't happen
...
.
Do you want to say anthing about this
Yes I wasted a lot of time and truly it sucks . Moreover it made me realized that I should focus on solving problems instead of making memes. I had no intention of disrespecting you but only making letting you know about my mistake.
Thanks for letting me know. I had no intention of disrespecting you too.
As a participant, I am eager for tourist vs Um-Nik
That's rather as a spectator. You don't need to participate for that.
tags: "doomsday" oof
People trying to be sarcastic in comment section Problem Setters And Testers : Say No More
Ps : Is it best announcement ever? :P
EvenImage : " I'm happy sitting atop the CF rankings. You guys give the contest."
Is this statement meaningful or is this general good advice for any round?
A :) in the end says it all.
I guess I should have read F earlier than I did!
Looking your shirt more good now!!
Thanks!
Congrats on becoming Red.
But man, by the time I understand 9 problem statements, 2,5 hour is already gone, and I already forgot 8 of them...
Plus!
As a russian guy, I don't understand tester's feedback.
Joke
Looks like it's going to be a difficult contest.
"As a problemsetter, I am sorry"
As a contestant,
...
...
As a participant, I will participate.
Looking forward to the problems. The announcement is hilarious and I hope the problems will be as well.
Never participated in Global Rounds. Are problem sorted by difficulty?
You can check Here all global rounds By yourself.
Website moving soon
Now more helpful..Thanks..Is it your website brother ?
Better rightly write right.
Don't worry, you guys are gonna enjoy the round :)
I also think that we will enjoy.
You didn't add "as a tester". That's suspicious...
[deleted]
Learn how to determine the parent comment.
Sorry for that..
unrate :aaeria:
Probably, one of the best contest announcements.
As a contestant, I quit.
mmkay bye!
i'm confused, should we be playing or not?
I see that I'm going to love this round...
No, you'll say that there is another platform for such contests
To be honest, adamant and antontrygubO_o together as problemsetters give hope that we'll finally see some balance.
But also the opposite is possible: that every problemsetter has just a position (A-I) assigned and all the problems will be chosen completely independently from the others and we'll finish having a 100% "another platform" contest.
Hoping to become an Expert after this round :)
Good luck for you <3
Do you want to get fewer participants with this anti-advertising of the problem set? If the goal is to avoid the server load, just say that there will be a lot of math in div2 problems.
LOL ! People will still try out of courage and for rating ! If it goes well they will be commenting like Best ProblemSet ever ! and if not they have their cliche MathForces
There are a lot of math in div2 problems.
Errichto It's been a long time since we saw you setting problems ! Come Back ! Soon ! :)
Even better, just say the whole round is Geometry
the whole round is Geometry
I see what you did there
When you khow people scared with math then do you do something like tutorial on how to get well in math? Errichto
I doubt that abundance of tutorials is going to cure aversion to "math".
I think. they r going for reverse psychology here....!!
First time, I see meme in contest announcement.There must be a reason behind it. We should be aware of that.Good luck to everyone. :p
How pupils become tester? :D
Racist
no u
As a contestent, I want rating.
xd
Same story, again and again, my smoll pp skills and big pp problems.
Best CF Round invitation ever =P
as a participant, i am also scared and i don't want to participate!)
GL&HF to everyone!!!
....
As a tester, My advice is to think 1 more day, because problems are more scarier than you are thinking...XD
I don't know why but it is giving me vibes of an amazing round.
.
****
9 Problems with an army of testers and 8 writers. Excited
IT IS TAGGED DOOMSDAY!!!
New here, it is going be my first Global Round and the comments already scare me. Is it a good idea for a new guy to take part in it? or will it be discouraging?
If you are new dont think of rating from the beginning try giving as many contest as you can. Thats what i learnt
9 problem that's huge. I appreciate the hard work to make a contest.
Yes appreciate problem setters for these kind of contests
"You will be given 2 hours and 30 minutes to read all of them."I think that's what he is trying to say.Links of previous global rounds:
Codeforces Global Round 5
Codeforces Global Round 6
Codeforces Global Round 7
Codeforces Global Round 8
Hope this helps!
Appreciate your work but we can directly search any round and go to contest link in the announcement.
The reason why it is not useful is probably not that "we can find it ourselves" but that this list was also shared in the previous global round. In fact, link to a web app was shared which can do this right away.
This global round seems to be very special among all previous global rounds because of its awesome announcement!!
I was going to make a century of losing rating in last contest...I think,this is another opportunity to complete the century...Shouldn't I be happy!!! SENTY_EMO
how is global round different from other rounds???
[Deleted]
you looks like topcoder
thanks
As a contestant, I will take part in the contest. :)
Can someone tell me what happened to static a2oj? I used to solve problems from there difficulty wise and now, instead of that a different website with that names comes and all the problems of the ladder are locked there.
Hey ,use this site .Works fine for me a2oj has been closed for some reason (https://earthshakira.github.io/a2oj-clientside/server/Categories.html) (https://earthshakira.github.io/a2oj-clientside/server/Ladders.html)
yeah it's working fine thanks a lot brother
:)
Finally, memes are on Contest announcement blog post :v
Explain me the difference between Educational round and Global round in div 2 like contest there is time penalty what about Codeforces Global Round .Thank you.
In Global round also every problem score decrease with time . It's almost like Div-2.
Global round is rated for everyone, educational round is rated for people who have rating less than 2100
Global round has some fixed points for each problem which reduces slowly as time goes on, all problem has equal points on educational rounds.
Hacking runs parallel with contest in global round, there is hacking phase in educational rounds after contest finished.
Wrong submission on finally accepted solutions will cost you 20 points in global round, in educational rounds it will cost you additional 10 minutes time penalty.
On global round last pretest passed solution will be judged and resubmission will cost you 50 point and in educational rounds all pretest passed(accepted) solution will be judged and 1st solution that passed system test will be considered.
How do you compare 20 points vs 10 minutes of penalty? What is the exact relation (if there exists one)?
I compare in sense of what will happen one submit a wrong solution.
thanks to all of them for frequent rounds
Next round after the global round is one week later.Are we not going to have any round before that?
There are almost 2 educational and div3 rounds in every month.So probably we will be having both also if a contest is added for date x it does not mean mike can not add a contest which has date strictly lesser than x.
A meme in the announcement .. you got my upvote
Hey Boss how to get like your meme idea.. I want to make my contribution 0.
the idea just flashes in my mind and I search for photos that can present the meme and edit it on paint
I can give you an advice some of my memes goes this way you just compare 2 completely opposite situations like this one
it's how I used to be when I started and how I'm like now this meme is actually sad for me XD
or like this one
it starts with someone asking them to be quite while it ends up with a party so there should be an element of surprise if it's something expected or usual then this is a bad boring meme and it should be about codeforces and competitive programming not jokes about html that's out of the context
Problem I.
You are given two integers a and b. Print a+b.
Don't spoil before the contest
I am excited for the round..hope for the best
dude that feedback gave me chill more than any meme xD xD
WTH to me. i was going to attend the contest today at 20:35..
I like this meme!
I love the announcement """""D
In problem B,can anyone explain this formula => a+(a+1)+(a+2)+...+b=(a+b)∗(b−a+1)/2 and what is it called
Just subtract sum of first b natural no. From first a-1 numbers. Like b*(b+1)/2 — (a-1)*a/2
Last contest B ??
https://en.wikipedia.org/wiki/Arithmetic_progression#Sum
I hope there are a few or no problems based only on observation
I hope a problemset like that of the previous round doesn't happen again. Problems A-D: Observation. A-C are 1 liners. D is two nested for loops which can be written with 3 lines. Problem F: Think for half a second, implement for half an hour.
In China, there is a well-known serie of huge datastructure problems called Ynoi.... Is it gonna have huge datastructures like ctholly tree?
As a stupid American, I don't get the testers' jokes.
rotavirus OTZ
As a participant, I have a hunch that I should hide my brain during the contest
Excuse me. Can someone tell me how the round is rated? I mean: is it rated like div.1, div.2, or div.3? I'm not very familiar with the contests of CodeForces (as you can see I'm a Newbie). Thanks for helping!
Alright. Actually I thought that it is rated in a way like div... but it seems that it's different. Thanks anyway.
Yes different .. See this
so here comes the DOOMSday
For the first time, I am feeling nervous that something bad is going to happen with me in this round :(
and what are the good things that happened to you in any round till now
Codeforces contests are like a sport for me . I enjoy the problem mostly without noticing my rating .
is this one as easy as div 2?
tourist after reading round feedback
As a participant, I am scared.
As a scared, I am a participant.
May the (code)force be with you friend XD
how the contribution is calculated.
It works like the hippos, you have to effectively shed your territory.
Ari Hey, I understand that you want to make a point, but don't you think tagging them is unnecessary? I believe noone likes to be tagged just to see themself being thanked every week.
GOOD LUCK TO EVERYONE!!!
Out of curiosity, What's the record for the most downvotes? (Can this comment break that record? xD)
This might help.
gamegame and dorijanlendvaj, for their help in improving the humor of the round.During round :
During round:
knock knock
Honestly, Is this contest suitable for a newbie????
Don't.
tbh tho A and B solvable.
Need to learn a lot. Couldn't solve even 1 ques. :(
If you want easier problems to try on, i personally think the first few problems on AtCoder Beginner Contests are quite suitable. Have fun!
Yes, AB should be easy enough. Go do it!
10 minutes delay, sorry. I'm trying to fix Ruby installation.
No problem sir. Codeforces is such a good platform that these types of delays doesn't hurt if contest go on smoothly
Contest smoothness >>>>> 10-15 minutes delay
My adrenalin just got wasted
Delayed by 10 minutes :/
What the fuck? Why is CF so bad in punctuality? -_-
you should write the words carefully.They are doing hardwork for us
Agreed but they can't just play with our time? Can they? :)
They don't force you to play this.. are they ?
Did someone force you to comment here? XD
No hard feelings brother!
Did someone force you to reply here?
Did someone force you to make an entry? :3
Try to compete in virtual contest then.
Did codeforces questioned you ever ? or did they ever ask you to pay for such an amazing platform? Be patient.
Tell me the day you need to pay to codechef or topcoder or any other site that exists!
True, but be patient at the same time.
Yeah bro absolutely! All the best to you for the round! Have a large delta!
Someone is talking about codechef , LOL. Can you please deactivate your codeforces account? And enjoy codechef. All the best :)
Can we deactivate it ? :/
Do we need to state the difference in the quality of Codeforces and Codechef?
A delay of 10 minutes is much better than an unrated contest or queueforces!
Calm Down,man. We all are human, we all make mistakes.
Don't thank MikeMirzayanov if you can't, But please don't hurt the sentiments of the fellow codeforces users.
Oh shit! Now I'll have to listen to Twice once again.
Oh shit! You had to listen Twice twice, it's two squared)
That's the number of problems I wanna solve today.
This ten minute extension is ruining the moment :(
my precious time....22:35->22:45
Just solve all the problems 10m faster :)
Delayed??
RIP all my excitement.
Is today's contest suitable for newbie and lower pupil?
Yes...I think by solve a,b we can increase our rating easily !!
A and B should be solvable by everyone, I think. But even if they weren't, participating in a contest is always suitable.
Hope I can make A and B
Even if you couldn't solve any problem during the contest, you will learn something from the editorial afterward.
What the fuck! Another 10 minute wasted. 10 min wasted before starting by waiting.
Codeforces is doing hardwork for free. You should not say these 10min wasted. Its way much better than an unrated contest due to long queues.
sorry bro
Ok, all set, 5.4.3.2.1 let's start..........not now, come again after 10 min xd
[deleted]
An interesting observation: all the people complaining about adrenaline being washed out etc. are below blue and below.
Interesting observation: all the people always having problem about something and not taking a joke as a joke are purple and above
Codeforces Global Round Exists:
As a contestant, I just read the questions
This was the Hardest A i have seen till now.
Not at all :| Hard but not hardest !!
How can you tell me on my behalf.i said i have seen till now,read the comment again.
Cause you attend 62 more contest..it is not so hard.
I think i got horrified from the contest announcement.XD
For me A was harder than B and C. Took me a while to reach the solution
Same here solved A in total 1:30 hrs and C in 10 minutes. xD
But C's logic was beautiful though, i was scared that am i missing some case here.
As a tester, I am very happy that I can enjoy others suffering in the contest.This line become true lol. But really awesome problemseti should have taken those feedbacks seriously :(
Your graph is really inspiring
No, it's not rather it shows how dumb i'm :(
Very good contest nice problemset
hope mifafaovo gets dethroned by umnik this time!
[*] rating
As a participant, this round gave me PTSD. XD
I gave this contest in the hope for specialist but it seems that still specialist is far away from me...
BTW logic for 3rd one is
"NO" if(a[0] > a[n-1] ) , else "YES"
Permutation Forces...
I think I need more IQ to solve problem like these, not algorithm knowledge. :)
Arggg. Tough round. Great problems, though!
Ari: how many constructive problems do we need?
Other setters: Yes
Great round with difficult problems. Hoping for a fast editorial.
Your memes are so good always bro !!
I wonder who did created problem D.
how to solved D ?
Never again.
Thus, hocky went and made a catfish farm instead. He is now known as the catfish farmer.
Is there anyone else who could solve D in like 10-15 minutes and has no idea about solving C? Bad day!
Anyways how to solve C?
The last element must be greater than the first
how to solved D ?
arr[0] < arr[n-1] => YES else NO
if(a[n-1]>a[0]) cout<<"YES\n"; else cout<<"NO\n";
if $$$a[0] \lt a[n - 1]$$$ then "YES" else "NO"
Consider this example
5 6 7 4 8 9 10 13 11 12
This can be visiualize as
$$$[increasing] [increasing] [increasing]$$$
5 6 74 8 9 10 1311 12But How we are breaking this sequence ?
We are considering $$$first$$$ and $$$last$$$ will remain in the end of the process. So our focus is to remove all the element in between.
See,
4$$$ \lt $$$5$$$(first element)$$$, this will insert break in our sequence, from this index we will start making new increasing sequence.Similarly observe,
13<12$$$(last element)$$$, this will insert a breaking point.Now, if you think a little about it, you will see we can merging first increasing sequence and last increasing sequence like this
5 6 74 8 9 10 1311 12==>5 6 74 11 12==>5 6 7 11 12So the sufficient condition would be $$$a[0] \lt a[n - 1]$$$ for answer to be exists.
34 people (and 2 in under the next such question) have replied to this comment but no one has even slightly explained why this is true. What's the use of such responses?Many of them don't know. :p
I proved it first before solving it. PLease Correct me If I go wrong any where. Let me explain the proof very clearly. if the minimum element of permutation that is '1' is last element of the array then plainly answer is No because no matter which ever operation you performed.the last 2 elements after operation will have minimum element that is '1' on RHS which means it is not possible to satisfy the condition that is a[i]<a[i+1].
Now if 1 is in a[0] that is in first place then the answer is always "YES" , just converse of I said above.
Now when '1' is in middle , things become nontrivial. For example 1 is in middle and after applying some sort of operation we reached a state where we have 3 elements and '1' lies in the middle of these elements , then lets say these elements are a 1 b.
then if a<b then we can delete 1 from the middle and at the end we will have two elements a b since a < b then we can achieve a single element but when a > b we cannot.
Observation 1: you can't make any operation that decreases the 1st element Observation 2: you can't make any operation that increases the last element If the 1st element is greater than the last elements, then in the best case you'll end up with 2 elements [a1 a2] where a1 > a2. Otherwise there is an easy method to eliminate all but 1 element.
You have to remove the greater element in permutation while you can. If this element become the last in sequence, print YES, if you cannot remove the greater element, print NO. This is the key idea
Can someone tell how to solve problem C?
If v[1] > v[n] print "NO"
Check if the first element is smaller than the last element
Problem setters and testers to all the participants rn:
G is a good problem for Div2D?
I guess a subsegment of the problems is reversed before the contest...
You will be given 2 hours and 30 minutes to solve 9 problems, and we highly encourage you to read all of them :)
Did they want us to suffer? There is no gap only between A and B, E and F
I really need to start thinking in multiple directions before coding. Had I done that I could have solved A much much earlier :(
Leason learnt.
Probably should've listened to the Round Feedback.
I am pretty much impressed that a trivial thing can be stated in such a difficult way (problem E).
I haven't done anything trivial in E.
E is just a bubble sort problem, written in a non-obvious way.
I am shocked.
Imo the thing not THAT trivial either
I'm not saying solving this problem is trivial, of course. I can accept the opinion that the bubble sort might be non-trivial.
Why did you put the easiest problem as G?
+1, that was some kind of a joke xd
E killed my will to live, how to solve that?
Transform the array into a permutation by considering pairs ($$$a_i,i$$$). Use bubble sort on the inverse of that permutation; each swap of elements which differ by 1 only remove that inversion.
In a non-sorted permutation there is always a pair of consecutive numbers which are in wrong order. You can swap them and it doesn't affect any other inversion.
I tried to implement this for like an hour or more :/ Need to study the solutions.
Hi, I'm still a little confused with the statement that "it doesn't affect any other inversion".
In eg: 3 1 2, when we swap (3,2) we get 2 1 3, but here we created a new inversion (2,1).
Can someone explain this please? Thanks.
With
3 1 2there are two inversions. Positions (1,2) and (1,3). We swap (1,3) because of the min diff of those two inversions. Then we swap the other inversion (position 1 and 2) resulting in1 2 3.Why can't we perform swap of positions (1,2) and then (2,3). The value array will transform as follows : 3 1 2 -> 1 3 2 -> 1 2 3
No.
3 1 2swap positions (1,2) ->1 3 2swap positions (1,3) ->2 3 1Note that we do not swap "the positions of..." or something like this. We swap the positions as given in the inversions.
Thanks a lot, the last line cleared all my doubts.
What was the approach for A? Felt like I was over-complicating it
print in alternating signs, that was enough
Any proof as to why that always works?
bcs negative minus positive is negative, and positive minus negative is positive
Ahhh. I feel so stupid now LOL
Because in that way every adjacent difference have opposite sign too. That's sufficient.
because positive number — (negative number) will always be positive and negative number — (positive number) will always be negative. this will give equal number of (Ai+1 — Ai) positive and negative numbers.
if(CF Rounds==Ad-hoc Problems)
cout<<"100% true";
else
cout<<"0% true";
Output: 100% true
Actually, wrong answer on pretest 2 =(
Can anybody tell how to do D problem ?
try to make every element equal to its index ( 0 based )
Solution for A B C D:
A:
B:
Check if there is no cells greater than 4
Check if there is no cells next to border greater than 3
Check if there is no corner cells greater than 2
If all option is true, we can do it Like this
C:
D:
Solution for A?
!Updated!
make the array such that it contains alternate signs +ve ,-ve,+ve...
For A you have to just put alternate sign(+,-,+,-,+,-..). Thats it!
These aren't solutions, they are only implementations.
I have discovered a truly remarkable proofs of this problems which this blog is too small to contain.
for C: shouldn't it be arr[0] < arr[last]?
Yes, sorry.
Since when was it that, during the System Test phase, only the submissions in queue are marked
?in the Standings page, and those which are not remains showing blue score?15 minutes into the contest: Will make it 2200+ today.
After about an hour and a half:
Meanwhile testers after warning us ;)
Really nice problems tbh xD Sadly I only solved AB
Best 8 minutes at the end of the contest ever:
testers were right
This round is CF history
Can someone share their approach for D? I tried to convert the given array to {0,1,2,3... n-1} in a step-by-step manner, but It was taking more than 2*n operations.
Same with you.
I always WA on 1. When I implement it right, then it overflows 2n in the last 4 minutes, which I have not got enough time to solve it before the contest is over.
I think it will have a smarter way to solve it, because the brute step-by-step is very easy to be found out .
I did the same thing, if MEX < n , a[MEX] = MEX , else I made the largest element such that a[i] != i , equal to MEX. I used a set to keep track of largest element and its index
ConstructiveForces
TheoryForces
How to solve F??
I kept on playing as 2nd player and kept on losing on 1000th turn of testcase 1 (or I have not understood the interaction correctly)
My logic was, for every turn (except for the last one) we will check that we do not make the following two situations after adding y to a (assuming the last move was not on a)-
1. a=b or a=c
2. a is the max of the three piles and a-max(b,c)!=max(b,c)-min(b,c)
If these 2 conditions are satisfied, we can add y to a, else we can check for the remaining pile in the same manner. To start off we can start with any pile which satisfies these 2 conditions.
For the last turn, I will only check condition 1.
the first player always can win
Yes and only in three turnes
how?
You can check the editiorial
Damn, I chose the wrong side.
everyone who watched code geass will feel like you are 1000% smarter than guys with similar rating.
Can you explain your solution D
Yeah, I first removed all the duplicates by always operating on a value which has appeared before in the array. After this our array will be a permutation of [0...n-1].
Now I just need to sort it. Assume all the array elements as nodes of a graph and there is an edge between i and arr[i].
this graph will be having multiple cycles. For every cycle with more than 1 node in it, we can operate on any node in this cycle, suppose value of this node is val, after operating it will become n (since our array was a permutation of [0...n-1]). Now important thing is next time when we will operate the value of the node on which we will operate will become val. So why not operate on the node at valth position (since after sorting arr[i] will be equal to i). So we will do that and change val to value of operated node. This will end as the graph is made of cycles.
After doing this for all the cycles, we will have the sorted array.
G (tree modifications)
Let's color vertices with red and black so that any edge always connects a red and a black vertex. Then it's easy to note that each operation either reduces a black vertex or a red vertex (makes it the opposite color).
I counted Nred and Nblack and print the answer as min(Nred, Nblack) — 1.
WA6
Where am I wrong in my assumptions?
Where are you wrong? In your code I guess
Could you see please? Checking my code was all I was doing the last 10 minutes, no luck 85992861
-- I guess nn is the issue.
I think you didnt initialize your array "nn"
Huh, I can't express the mixture of emotions I have now... Using C++ for contests only has its dark side. And I'm a Java guy, yes...
Thanks, bro)
I don't now how it is in Java, but PLEASE do not declare arrays locally. Either use vectors or global arrays.
P.S. Tip: "min" function exists
D was a great problem in my opinion.
By pigeonhole principle, you can never exceed 2 * n operations. (since if you are having a cycle, you did not waste your operations in step 1 for those positions.)`
Submission
thanks
I had the same idea, and would've solved it if given 5 more minutes. I wasted so much time proving C although I guess most of people just wrote the one liner with a strong intuition. My own fault :(
Easier procedure:
Step 1: Write $$$mex$$$ to $$$a[mex]$$$ until $$$mex == n$$$.
Step 2: Find position $$$i$$$ such that $$$a[i] != i$$$. Write $$$n$$$ to $$$a[i]$$$.
:D
I also tried this approach sir..May be my fault
I solved the same way, but due to poor implementation I got 5 wrong answers
Damn, man. I did step 1, couldn't figure out to do step 2 in less than 2*n operations. Thanks a lot for the approach.
Try to make $$$array[i] = i.$$$
change the array to 0 1 2 ... n — 1 for hint : if mex = x and x < n you can choose a(x — 1) if you dont choose a(x — 1) again mex will never equal to x
Why did you host atcoder contest on codeforces?
I don't know how many people have encountered this problem, but I spent more than an hour on it and still didn't fix it :(
Nobody said to me July 5th is April 1st requiem
it was fun
A- alternative + and -
B- fill the matrix as
23332
34443
34443
34443
23332
C- if(last element>first element) ans=yes else ans=no
Most Ad-hoc Problems ever seen
You forgot to mention the rest.
OK, you've warned us, I'm quiet.
I'd press F to pay respects, but given the circumstances ...
E was well known to me xD https://artofproblemsolving.com/community/c6h380159p2102937 Kinda obscure source (Baltic Way 2007), but I remembered this as an exceptionally nice problem.
I spent one and a half hour to make a huge implementation on c and found the elegant solution just after i solved it smh
Cried after seeing the solution of C? Can someone give a proof for this?
Try with copy pen and observe .
You may have solved with observation, but there is a good proof. Here it is-
After each move the first element is increasing and the last element is decreasing; if in some moment there is only one element and a[0] > a[n - 1], the first element should be equal to the last element, but it's not possible (k = last element, then k >= a[0] > a[n - 1] >= k, absurd)If instead a[0] < a[n - 1], there is always a move because the array is never completely decreasingWhat If I resubmit an Accepted code with one line change ?? My solution has been skipped for system testing?
Problem C is one of the sign we humans have reached our advanced civilization.
True AF.
I stucked in B and after the contest when I saw the solution of C of top performers I feel bad for me
Fast system testing!
Fastest system test.
Everyone was too scared to submit. :P
Well, my C story: unsucessfully solving C for 30 min while checking out other problems and trying literally every possible idea on C, checking that C has a ton of solves and I should do something with C, coding and submitting unproven greedy which passed, and after contest finding out that it is just a convoluted way to determine in $$$\mathcal{O}(n)$$$ whether $$$a[0] \lt a[n - 1]$$$.
As a tester, I was struggling with C for too long, and I did something similar to you.
In B i got 5 WA because of
writing
arr[i][j!=0]instead ofarr[i][j]!=0so sad!!
.
Wasted 45 mins in C finally got a[0] <= a[n-1] after solving many test-cases.
Very good conclusion？
Actually，I was deeply surprised when I saw this F and G.
And even I didn't solve the C by the $$$a_1 \lt a_n$$$.
Rather than blame the survey scope of the person who made the question, it's best to regard it as a opportunity to progress.
lol
upd: the data of F is too weak... You can past it even you forgot to judge the "self-kill"...
Interactor was coded to only ever print 0 if it really can't make a valid move, not sure if that's what you mean.
the most frustrating thing is I spent nearly half of the whole competition time on F but didn't get the idea until the last 3 minutes and I didn't complete the code... Anyway, nice contest! thanks the authors and organizers. my rating should increase anyway:p
same
i didnt perform well but contest was amazing.
I love the problems in this contest!
Writers and testers thakns!!!
nearly 21000 participants registered and only about 8000 solved problem A so either participants are becoming too much conscious about their rating that they don't submit if they didn't solve problem A fast or problems were that tough but i don't think A and B were tough.so its actually the former point
Or they just register in advance without knowing whether they will be able to participate
85960902 and 85958960 are exactly same solution including macros and comments
85938310 and 85961324 are exactly same solution including macros and comments
Their handle are also same.
Looking on submissions times I can conclude that he tries to avoid rating decrease on main account in such a way. Looks like new cheating technique on CF discovered (actually, modification of "late submission" strategy for multiple accounts).
Today's contest came as a rating dropper for me. A didn't click try solving it for 30 min. Did B fast. Didn't notice that a1<an part. Tried solving it in a different way. Got the idea of D completed the code but because of one break statement kept getting wa. Contest got over than saw my mistake. Great contest Bad Day
Hey , I received a message that my code matched with someone. I even dont know this guy. Please recheck our codes and give my rating back for this contest .
When will the ratings change?
Codeforces comment section is addicting.
I thought this was code forces, not constructive forces...
As soon as I submit a solution, the problem gets locked. I am facing this problem for the past 2 contests. Is there something that can be disabled to solve this issue or it's a bug?
It looks like you locked all the problems around 1:24:00-1:24:30 at slightly different times.
Was this a scam to make more people add you as a friend? :D
No I have not done it for adding friends. The problem is genuine. The problem got locked after every submission. Once the contest finished, they all got the same time, I dont know how. And even when the problem was locked I was not able to look at the other submissions.
Congrats on becoming Red :D
Wrong, the color of his handle becomes the color of his shirt.
Stop giving your codes to devanshi345 and that might solve the issue. Proof: Devanshi's submission Aman's submission For those wondering how devanshi and aman are relevant, they are siblings. Why would someone make a submission in div3 D and then leave? If you see devanshi's code then you'll see she has added 1 to some variable and then subtracted 2 in the very next line and she has done this twice, you obviously know why. Also I didn't jump to the conclusions directly by looking at one code but I have been observing them closely and have a lot of other codes as proof. Just see devanshi's and aman's submission times for the past few contests, quite strange right? Exposing them won't benefit me and I'm wasting my time and know that well so if anyone has any advice in this context then please stfu and do your job. I felt good after writing this comment and don't care if I wasted my precious 5 mins.
Codeforces predictor showed that I was going to get 66 rating, but I only got 64. I feel scamed :(
Oh, I see these 2 points in your case meant a lot :D Congrats on approaching to red zone!
Rating prediction is inaccurate because CF doesn't provide "true" rating for new accounts. If I subtract 2-3 points from a rating prediction for every person, would this make contestants happier?
OMG
Other account? Main account? What are you even talking about?! You can’t have more accounts! You are just a cheater.
do you even read agreement before signing up for the contest?
It's not sensible because you consciously registered in both 2 accounts which means you willing to cheat. I am right? :))
seems that increasing ratings are getting less and less if you do the same amount of problems in each contest.
To see the first 5 contest you can not judge.cause after 5 contest your rating Will br balanced.its the new rule
Could anyone tell me the solution of the A :((
The Integer Game question was one of the best and greediest interactive questions I have seen on CodeForces.
but it is easier than E even D.
As a contestant i increased my rating!! Thank you for this great round!!
Are you jealous ?? :v
What a good contest! This contest is involving many knowledge points, like constructive, constructive and constructive, or guess one conclusion, second conclusion, and third conclusion. That's fantasitic, isn't it?
Yes, it was a great contest. The implementation of problem D was really good. It would be better if problem-setters include more of the problems on data structures in C and D problem.
o...you didn't understand what I mean. :)
The contest would've been better if not all questions were of similar category.
Congratulations to the t-shirt winners!
WHAAT!, two times in a row. How lucky am I
There goes, probably, my only chance of winning a t-shirt :/
Can we request a custom t-shirt design for rotavirus? Good deeds should not come unnoticed
uwu thank you so much
instead of calling this contest as global round 9, rename it to constructive algo contest