Hi! 
On Aug/16/2020 17:35 (Moscow time) we will host Codeforces Global Round 10.
This is the fourth round of a 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.
The prizes for this round are as follows:
- The top 30 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 are as follows:
- In each round, the top 100 participants get points according to this table.
- The final result for each participant is equal to the sum of the points they got in the four rounds where they placed the highest.
- The top 30 participants over all series get sweatshirts and place certificates.
Thanks to XTX for supporting the global rounds initiative in 2020!
The problems in this round were prepared by KLPP, zscoder, qlf9, golions, MagentaCobra, and me. We would like to give a huge thanks to the following people:
- antontrygubO_o for
rejecting most of our problemscoordinating our round. - gamegame, dorijanlendvaj, thenymphsofdelphi, aryanc403, Ari, alireza_kaviani, KonaeAkira, Mn619, AmShZ, smax, galen_colin, cuber_coder, gabrielwu, nvmdava, 300iq, Monogon, Mohamed.Sobhy, maroonrk, 244mhq, pajenegod, Devil, Osama_Alkhodairy, Mohammad_Yasser, taran_1407, Um_nik, physics0523, hugopm, mohammedehab2002, gonP, tfg, Joker_11, kshitij_sodani, JAPL, duckmoon99, Blastman, coderz189, and Antebe for testing and providing invaluable feedback.
- MikeMirzayanov for the Codeforces and Polygon platforms.
- All of you for participating in our contest!
We had a lot of testers as the problemset of the round changed significantly throughout testing! As a result of the huge amount of feedback, we think that we've managed to make the round really high quality and hope that you'll enjoy it :)
You will be given 3 hours to solve 9 problems. The score distribution will be announced at some point in time before the contest starts. Good luck!
UPD: Score distribution:
500 — 750 — 1000 — 1500 — 2000 — 2500 — 3000 — 3500 — 4000
UPD: Editorial
UPD: System tests have finished. We hope you liked the problems! We apologize for the weak pretests on A and B — that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)
Congratulations to the winners!
Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
Cute anime girls solving cute problems
As a problem writer, I really hope this round is truly rated for everybody
I tested this against my will. I demand financial compensation.
I wrote this contest against my will. I demand therapy sessions paid for by antontrygubO_o
+1.
I demand my pending 2 cf t-shirts. I'm waiting for them for the last 3-6 months.
Testers and problem setters of https://codeforces.net/blog/entry/79745 are a subset of this round's setters and testers.
Notorious Coincidence indeed.
Still waiting for this random top 500 T-shirt.
one question comes to my mind everytime I see these waiting memes:
Who the hell steals clothes from the dead body and leave it naked??
The world is very bad outside, be inside and save your clothes as well :P
'Notorious coincidence indeed'
are you trying to say that the problems are going to be stolen from round 655? o_O
You don't have dick?
-1 for the name
As a tester, I regretted that I can't participate this as an official contest...! The tasks are very interesting, glhf!
#copied?
Yes the problems were very interesting.
Yes, Best round of CF's history, i really enjoyed it. Thank You CF !! CF should put such rounds every week.
As a tester, i like the contest.
As a tester, I tested it when it was a div.2 :))
As a tester, Me too :((
As a tester, me three.
Is there any specific reason to give a 3 hour contest as it rarely happens :P
Usually a div 2 contest has 6 problems and is for 2 hours, a ratio of 1/3 hours per problem. This one has 9 problems, therefore to maintain the 1/3 hours per problem ratio, contest needs to be 3 hours long.
What us div2 people going to do for the rest of 2 hours watch the standings :XD
Celebrate pretests passed before we face the wrath of Wrong answer on test 11
You are missing unrated tester :D
As a writer, I recommend you to read all problems :)
last time I read such comment from writer/tester, I lost 170+ rating :)
last time I read such comment from writer/tester, I gained 132+ rating :)
Goodjob!
How many did he reject XD ?
Colorful testers!
So many testers?!!
You mean hostages
Really? I think being a tester is a great feeling!
Many of us tested because it was div2. Then it became a global round, so we lost the opportunity to participate in a rated contest.
At that time, we tested only 4 current problems and now we can't participate rated.
(-__-)
Just approach any problem writer,too simple!
Really?? You got the testing opportunity by approaching the problem setters??
Also, how will I know who's gonna host a contest in the coming months? What did you do? How did you know they'll be hosting a round?
I would say that you have to know some of the problem setters to have a chance of being invited , since there's a lot of information that has to be kept confidential.
[Your text to link here...](
As a tester i would like to say that the problems are really interesting and you all should enjoy participating in this!!!
I was thinking about skipping this round as I have an exam the day after this round but your comment made me ignore the idea :D
We seen many specialist testers in the last few contests and now, we got a newbie too.
Nice to see authors from all round the world tester from all colors.
Global round indeed
Do longer contests cause bigger rating changes (on average)? It would make sense to me that in a 3 hours contest rating changes 1.5 times as much as in a 2 hours contest.
How high were you when you wrote this?
The average rating change after every contest should be theoretically zero.In reality, recently the average rating changes have been a small negative value. If you want to check the average rating change of any contest,use this code
Code Author : farmersrice
The fact that the rating change should be close to zero has nothing to do with what Round_Dice said
Variance vs expected value.
Yeah, variance or standard deviation makes more sense. What I meant when I wrote it: Average of the absolute values of individual rating changes, which is called average/mean absolute deviation.
The writers picking people to test their round:
Still couldn't make strong pretests for A,B
Really happy to see so many testers. Especially because there is so much variation in the colors: All colors from grey to black-red are there among the testers <3.
9 Problems with 3 hours?? Awesome
I still get flashbacks from global round 9
what is the point of tourist, Benq and their gang getting CF t-shirts every global round?
these guys must be using CF t-shirts as wipers.
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 joked about by random people.
Ari hi
Ari hi
orz
Guys, please don't tag Ari unnecessarily.
Oh trust me, Ari would not be mad at me because I tagged unnecessarily and said orz.
Why are you tagging Ari though
Looks nice maybe
Guys seriously stop tagging Ari.
Fair point.
I did not think about it. Usually I use handles to make my comment colorful
Alternatively to make your comment colourful, you can use css inline styling by using any html tag like, span.
I didn't win a t-shirt last time ...
I wonder how many t-shirts programmers like you have.
No problem. Even those who won don't get a T-shirt. click
As someone who frequently ends up in the top 30 places, do you think it makes more sense to distribute the t-shirts to top 30 participants who have not received CF t-shirts before?
This way will get many more participants excited about the global round.
First time receiving CF t-shirt, you will get excited, the second time hmmm maybe a bit, the third time I am sure you would not even track the cargo.
well maybe if they actually receive the t-shirts... I'm starting to wonder whether these CF t-shirts are actually real
Personally, I do so with mine, not from cf though.
Literally me this round :( CF-Predictor predicted that I would lose 98 rating.
Will this be rated for div-2?
Global rounds are rated for every division. Read the announcement carefully. It says "The rounds are open and rated for everybody."
question for administrators. are there any team contests planned in the near future, its so funny and interesting when you and your team can sit and solve problems in sports programming
BEST WISHES EVERYONE ...!
oh hi kira
hi
oh shit...!!!
got you. ;-)
f
Depends on your performance
Why the next contest is after 9 days?
God damn it if it was 8 problems and 2 hours I would've made a joke about Barcelona
We are done with that shit. #BARTOMEU_OUT
I like this contest ,because we have high competition in this,and problems are found to be so much interesting in global rounds.
I hope that difference between the difficulty of two consecutive task (especially D and E) will be at most 400!
I am new to codeforces. Please let me know if this contest is rated?
I think u have the ability to read the announcement carefully!
Looks like antontrygubO_o is famous for rejecting problems.
Nine days without contest ...
FeelsSadMan
.
As someone who had 0 involvement in the making of this round, I also guarantee this contest is great!
.
.
)
You should come visit us in div1.
Definitely, I will!
Till now I am bearing the damages of two global rounds.
When will be the 2nd Div-4 contest?
When mike need to have some load test of server.
Blog posts of non-educational rounds before the contest begins -> 150+ comments, many memes.
Blog posts of educational rounds before the contest begins -> 20-30 comments, hardly any memes.
Why does CF community like to comment and post memes more on non-educational rounds? Number of contestants are similar in both round types. I was just wondering.
Educational rounds has traditional copy pasted announcement and same author,co-ordinator,testers.
Non-educational different author, testers and sometimes different style of writing announcement. Memes and most of the comments are based on this writing styles, no of tester, color of tester, what happened on author's previous rounds ,wish and expectation from new author and so on
Guess that "Rainbow Dash" thingie from round #662 had its effect on the testers.
...
No more "Read all the statements" message ? :))
9 problems! Rated for all! It would be great if it was told at which problem Div2 coders should stop, and start seeing leaderboard for rest of the contest.
Hope it won't be a QueueForces or ThinkForces
Newbie and Pupil testers give me hope
All the best everyone for the round :)
queue forces
long queue?
3 hours for this long queue?
tourist on fire !! Solved 4 out of 5 questions first till now.
why downvotes ?
because
Another Unrated Round I guess !! Long Queues ... feeling sad.
Oh lord Omkar! please help me increase my rating
Don't worry Lord Omkar will Give you Power to defeat all your Worries !
Wow. What an excellent contest guys. Well prepared, interesting problem statements, you guys nailed it on this one!!
Incredible contest, this is the first time I solved 4 in 1h30m, the problems are so good that you feel amazing after solving it.
Really Bad Pretests :(
Pretest kinda suck ngl
36 testers and 900 hacks
I don't know why people complain about this every time.
It's not against the rules that pretests are weak. It might be a questionable choice by the authors but it is not automatically a sign of shitty preparation.
It is a very questionable choice on combined rounds. The top standings being determined by who hacked the most div 2 contestants is pretty dumb :/
IMO the existence of combined rounds is a very questionable choice :P
I think hacks should not give extra points.
It seems strange to me that some participants in top-100 can get extra 200-400 points by hacking grey or green guys. At least it adds some randomness to the competition.
My solution to B in testing would've been hacked. Just because there are a lot of testers doesn't necessarily mean that authors use all of their solutions to check if tests are strong. I don't know why wasn't $$$t \leq 10^4$$$ which would've allowed random test cases to catch most bugs.
Though i did help with test cases by trying to submit an unordered_map and gp_hash_table solution to A which both got AC and later realized that in those solutions didn't clear the hash table after each test case so then pretest 2 in A was changed to break solutions which don't clear the hash table/map after each test case.
Good problem set. How to solve F?
Does the solution use parity of heights?
No, just the sum.
Someone has a hint on E?
a[i][j] = 2^(i+j) * (i % 2). You can figure out where to go by checking k & (2^(i+j)).
Thanks! That is smart.
How many bits do you need per diagonal in order to be able to reconstruct the solutions? How can you make sure you get this information?
Was D Dp? I tried but was getting the wrong answer on one sample case.
Submission
States were dp(index, prev_selected, current_selected, next_selected)
Just calculated the minimum number of changes to prevent 3 same characters ($$$LLL$$$ or $$$RRR$$$) in a row. Let's see if it passes the system test.
I did the same, tried to prevent the 3 same characters in a row. Hope this will work
Worked like a charm.
I did with DP, the pretests were passed. I did with 3 DP states, (index,curr,prev). Since I am not storing the next state, I had to specifically check for every possible starting state (as it is cyclic dp). You could check my submission here. 90129512.
I tried the same too with 3D dp). But it failed on the same case. So I tried implementing in 4D, maybe if I am missing some cases. At last, wasted my whole contest time debugging without knowing where I am getting a mistake.
I know I should blame myself. I also know that complaining about this is not good but...
How did you make the pretests?
Video Tutorial for D. Omkar and Bed Wars
:(
Pretest2 in D is a bi*ch
What were the hack tests for A and B?
For A
1
8
1 1 2 2 2 8 16 32
answer please
There is always answer 1 but if all elements of array are same,answer is n(size of array).
For B 1 1 1 -10000000
Why would this test case hack solutions?
Many people initialize
maxwith $$$0$$$.If the input was all-negative then it will break.
B Hacked :(
Very weak pretest of B:
90095907
I think every number in pretest are greater than 0 and it makes so many hacks...
How do u construct the grid in E ?
From every point, you can reach two new points. Ensure these two points have different values. Use uniquely identifiable values (0,1,2,4,8,16...) for each unique manhattan distance from the start point. You may repeat values, as long as two points touching at a corner don't have the same value.
So for example,
Essentially at each point in the grid, you can determine the next move (left or down) because each of those two values will be different.
How to solve E?
a[i,j] = fib(2*i + j) fib(0) = 1 fib(1) = 2 fib(n) = fib(n — 1) + fib(n — 2)
How do you prove that there won't be any paths with the same sum?
Thanks for the not-ultra-strong pretests in the easier problems which left a healthy amount of hacking opportunities.
It Was Amazing
Task E: How does this solution get TLE? My complexity 2 * n * q = 50,000 https://codeforces.net/contest/1392/submission/90167797
not flushing output
Fantastic round! Lot of variations in the set. Problem E stands out, really enjoyed that one in particular. Thank you authors and testers.
By the way, here is problem D on OEIS: https://oeis.org/A007040
can you explain a bit
Calculate the minimum number of changes so that there is no $$$LLL$$$ or $$$RRR$$$.
That's the total number of distinct strings of length n where all the players are acting logically according to Bed Wars strategy.
That sequence is the number of (marked) cyclic n-bit binary strings containing no runs of length > 2, so it essentially tells you what to solve here, which can be done with a trivial DP.
Problem C was a repeat. https://codeforces.net/contest/205/problem/B
Not the same problem, there is no nondereasing condition on the chosen subarray...
Its same. I took a random code and now its accepted for today's C Soluton
Not the same problem, there is no nondecreasing condition on the chosen subarray.
The fact that the solution is the same doesn't mean it is the same problem, at least in this case when equivalence isn't obvious.
Jebaited (no NTT involved on the problem with 998244353 but FFT is involved in I XD)
Nice round. I just wish there were fewer easy problems. 9 problems (in total) is too many. 7 or 8 next time please.
And more geometric scoring, obviously. It's bad that every next problem is worth only ~15% more points.
Its rated for every body(global), not only for div1..
Yeah, and div2 participants didn't really touch the hardest problems. If only it was possible to give different problem sets to div1 and div2...
Understandable, have a nice day
someone please explain problem C
From i=0 to i=n-2, search for all peak values and find the differences between the peak values and the immediate next value, and then find the sum of those differences.
Example: 5 6 7 1 2 3 4 5 1 2 3 5
Here, the peak values are in index 2 (7) and index 7 (5). Sum = (7-1) + (5-1)
It was quite easy for a C problem. Even I didn't check it out during the contest, thinking my skills wouldn't suffice for a Global Round C problem. Alas! :(
What is the logic behind it?
You take the last two segments. If the last is smaller than the prelast we need to add some hight to the last. Repeat for all i.
For me, problem E has a huge pitfall, and I debugged it for an hour:
(1 << (i-1)) is treated as an int rather than a long long(if you want to get long long) , so you need to obtain it by: 1LL << (i-1) // to complete the operation of h = 1<<(i-1)
1LL << (i - 1).Thanks a lot, now I get it.
Great contest,problems are so interesting,I solved 4 problems but 6 wrong submission before it.
Fun problems, thanks!
What would be the solution to F if the initial array was non-decreasing instead of increasing?
I think my solution handles nondecreasing as well: https://codeforces.net/contest/1392/submission/90123388
I maintain a stack of positions of "flat" segments.
RIP Newbies :)
Anyone solved E with a non-greedy approach? I think the constraints were chosen carefully to disallow such solutions, but did anyone manage to pass? I'm particularly interested in randomized/backtracking solutions for E. Did anyone solve using that way?
I was also trying the same but no luck, got WA and TLE.
Thanks for the interesting problems.
Tnx for your fast responsiblity at contest
Thanks for the careful preparation and interesting problems.
A,B,C in like 15 minutes, and turns out all other not even close to a working solution. Not that exciting problem coice from my point of view.
How to solve c???
You need to sum $$$a[i-1]-a[i]$$$ for all i.
Correction : if and only a[i] < a[i — 1]
Was C a standard problem?
Anyone else feeling the same after getting B hacked or failed at system testing because of initialising maximum as -1. F for me
I am back, whether you were waiting for me or not, but I am here.
Really great contest... Appreciating the effort
hello problem setter or admin I don't understand this .when this contest is running then hack my code in B problem (https://codeforces.net/contest/1392/submission/90140478) .But when contest end showing Final standings then i submitted same code then show code is Accepted(https://codeforces.net/contest/1392/submission/90171270)
I think it's because not all successful hacks become system tests
is it real to solve this problems with python? i had rly big execute time at A and B while it's almost insta launched in my jupyter notebook, any opinions? or u should know c++ ideal to solve contests like this?
This blog should help you.
Can someone point out my mistake? Thanx in advance. https://codeforces.net/contest/1392/submission/90167944
UPD: I got it.
No rating changes yet? Why so late?
For problem C, once I read the solution, I can understand why it works, but I am not sure how I would have arrived at the solution from scratch. Somebody help me?
assume an array like this
8 9 10 , 7 8 9 , 2 3 4 , 1 2 => ans=0
non- decreasing sub-arrays are separated by commas
now consider last two sub arrays - increase last sub-array by ans+=(4-1)
situation changes like this
8 9 10 , 7 8 9 , 2 3 4 4 5 -> array 1
again consider last array => ans+=(9-2)
8 9 10 , 7 8 9 9 10 11 11 12 -> array 2
again consider last array => ans+=(10-7)
8 9 10 7+3 8+3 9+3 9+3 10+3 11+3 11+3 12+3 -> array 3
resulting array 3 is non decreasing
so answer is absolute difference between comma separated element of array 1
hoping this solution will help you
Leave it!
for every possible k -> (according to your given values of grid)
there should be a unique path
if there are two paths that have same sum then you don't know which one is correct path so every path should have different sum -(so you can use bitmask for it)
The point is if you set every element to a constant say 1, then no matter what path duck will take sum will always be same, and if you output any path which is satisfying the sum i.e. in this case "any path" then your answer will be considered wrong as a specific path is to be printed which is hidden in the test case
Why is the next contest scheduled after so many days? Anyone has any clues?
The group of people who run this website do so primarily to protect themselves. In reality, however, they form a secret organization to fight the evil in the world. In a few days they will return from their undercover assignments and then organize the next contest.
My congratulations to the t-shirt winners:
This is a very good contest.