Hello, Codeforces!
On Nov/23/2021 17:35 (Moscow time) we will host Codeforces Global Round 17.
It is the fifth round of a 2021 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 2021:
- 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 2021 supported the global rounds initiative!
The problems were written and prepared by AliShahali1382(Ali Shahali), AmShZ(AmirMohammad ShahRezaei), DeadlyCritic(MohammadHossein Paydar), Keshi(Alireza Keshavarz), alireza_kaviani(Alireza Kaviani).
We would like to thank these people:
- antontrygubO_o, for coordinating and helping a lot to make this round happen.
- Tet(Soroush Sahraei) and Davoth(Alireza Samimi) for giving ideas for some problems.
- our testers for testing and providing helpful feedbacks: gamegame, Kalam, Amoo_Safar, prabowo, dorijanlendvaj, aarr, ymmparsa, nor, ArshiaDadras, Davoth, ijxjdjd, sohsoh, 16204, wxhtzdy, naman1601, mblazev, fatemetmhr, hiva_, manish.17, Saman., SMahdi, Vjovein, mohammad_rastegar.
- again gamegame for being an orz tester and ACing all of our problems!
- MikeMirzayanov for codeforces and polygon platform!
You will have 3 hours to solve 9 problems. As usual, it is highly recommended to read all problems!
The score distribution will be announced at least 5 minutes before the round starts! :)
Score distribution : 500 — 1000 — 1500 — 2250 — 2500 — 2750 — 3250 — 3500 — 4000.
Please give me contribution, I slept two hours later last 3 nights because I was trying to come up with a problem which makes the round better.
[edit] Sorry, it wasn't intentional :(
[edit] make it 6 nights...
I'm so depressed that all of my hard work and dedication on preparing problems has failed as I couldn't achieve the first comment :(
Sorry, it wasn't intentional :(
On behalf of the contest setter's committee, I would like to congrate you for achieving the position of first commenter. Here's a golden titop prepared by the committee for all your dedication and hard work:
Omg It's so huge, May I share with family & friends? Give to charity?
There are amazing skits and plays. Then there are Global Rounds. :)
Give us the Golden shaam, mr generous. It is more than 1 year we're waiting.
I think another problem with name SifidLee is coming XD isn't it?
Omg that's such a nice idea.. I wish I was as smart :D
As a tester, good luck on contest and upsolve all problems because they are awesome!
As a tester, I can confirm that the problems are pretty nice! I would recommend participating in this round and enjoying the problems.
Apologies to the setters for having them first change one problem's constraints and then for them to have to remove the problem entirely; it was a nice problem in my opinion. :(
<3 :(
The table at the contests tab currently shows 2 hours duration for Codeforces Global Round 17. Is it actually 2 or 3 hours?
3, info will be updated soon
What does sifid like this time :D ?
Orz
Orz
Orz
Orz
gorz
goraz
As a tester, orz
Hope AliShahali1382 will not make shitty problems like 1440C2 - Binary Table (Hard Version) this time.
That problem was prepared and authored by Mohammad.H915 ! not AliShahali1382
GL, HF
No light-hearted meme this time :(
Iranian contests always had interesting problems,I am sure this one will be as good as others
CF Round 684 still gives me PTSD...
Auto comment: topic has been updated by AmShZ (previous revision, new revision, compare).
As a tester, I wish everyone good luck!
R.I.P Tet
I'm so excited for this round :")
I am excited for another Iranian round :)
This is an exciting competition :))
Hooray :D
Please give the scoring distribution as early as you can as there are 9 problems
Expect Great Round :"
Hope it meets your expectations brother
heeeyyp... have good contest...
Hidden...
every global contest makes me upset, I hope this round will be diffrent .Good luck to every one QwQ
"The score distribution will be announced at least 5 minutes before the round starts! :)" really very useful information :) thanks
I definitely don't find any reason for not giving the scoring distribution an hour earlier before the contest
Why is scoring distribution so significant before the round? I don't quite understand, can you explain?
At least 30 minutes before: Where is the score distribution?
At least 5 mins -> 6 mins :)
I prolly will go back to being a specialist, but it would be fun anyway!
Good luck everyone!
Is this div.1?
Sad :')
I think setters and testers are giving down votes to everyones comment
We're too busy :(
Did B,C in first try still couldn't do A ;-;
everyone who didn't pass A probably missed this case
n==1 && m == 1omg, I hate my life
you missed the case with answer 2 sad(
tfw your only WAs on a problem were on A
I'm never doing global rounds in my entire life, never, ever, again.
p.s: but it was a good contest, and it's not that because the problemsetters were Persian, not at all ;).
I think you should definitely buy this
https://www.amazon.com/Forum-Novelties-Spots-Costume-Standard/dp/B00TTLZO48/ref=sr_1_2?keywords=clown+custom&qid=1637761582&qsid=131-0361440-3231543&sr=8-2&sres=B008509O1I%2CB00TTLZO48%2CB06XNP8H7X%2CB07CZPDFY2%2CB07TT84J1R%2CB09DFYQ5C1%2CB003PCEP10%2CB01NC37Z7T%2CB07WDSH3TY%2CB07WVQNSHZ%2CB01N6CEFOU%2CB01DYMAFMS%2CB01MSDZ3KY%2CB001F9VZ22%2CB00IMB254I%2CB079GHK4XM%2CB074N94GPX%2CB079C4YB21%2CB07XC415M4%2CB086RDP874&srpt=COSTUME_OUTFIT
Is this Rated?
Noob question: I've searched for these and couldn't find answers: Within the post above, it says "The rounds are open and rated for everybody". However, within the title, it doesn't say it is rated. On my graph, this competition comes under unrated. I'm quite confused. Is there a way to tell which competitions are rated or not, that I'm not aware of?
The system is calculating the rating change for each one
B,C,D are decent problems but A is not appropriate for its position.
.
I don't know what to say about this round. I just appreciate that I don't feel bad although I performed poorly.
How to solve C ?
My solution is based on binary search on the answer. The boundaries for BS are l = 1 (you can always call 1 friend), and r = n. Now we are interested in whether can we call m = (l+r)/2 friends to the party? Let's iterative from first to the last friend and keep count of the number of the friends we have already invited (this will be cnt).
First of all — all friends to the left of the i-th friend are poorer, and all friends to the right are richer. If i-th friend satisfies these requirements we will call him, and update cnt = cnt+1:
1) a[i] >= m-cnt-1 //number of friends who will be richer than i-th is m-cnt-1 (since we are trying to call m friends with cnt already called + himself, that leaves us with m-cnt-1 friends to the right)
2) b[i] >= cnt //number of friend who will be poorer than i-th is cnt, since we called already cnt of them and all of them are to the left of the array
If in the end cnt >= m, then it is possible to call m friends, otherwise it is not. According to this we continue with our binary search.
how are finding the subset of m friends from the whole array? as each time a person is picked(say i), we have to check whether some person which was picked previously(say j < i)it's a[j] is not less than i-j i.e no of person's after it?
For anyone looking for video explanations (for A,B and C only)
You can visit here
Idk how D has so much solves compared to E. For me it felt D >> C > E.
Shitttt!! Got the blunder upon seeing others' code T-T
All you said is true apart of -> each difference has to be bigger than sum of all previous differences. So the number of elements chosen is O(log) + (the number of elements equal to the first one chosen, so there can be a lot of them, but we "jump over" them at once).
I feel like its really easy to go down the wrong route on D after making observations on the first sample for $$$\equiv 0 (\text{mod } 4)$$$ and $$$\equiv 2 (\text{mod } 4)$$$ part, but if you realize (or guess) it generally applies to $$$\equiv 0 (\text{mod } 2^x)$$$ and $$$\equiv 2^{x - 1} (\text{mod } 2^x)$$$ then its fairly easy to arrive at the solution.
Unfortunately took me wasting 1 hour hard coding a special case for pairs of $$$\equiv 0 (\text{mod } 4)$$$ and still overcount sample 2 to think about it properly and realize it.
It took me 1 hour to solve D and only 15 min to solve E. I thought there was a better solution but it turned out people did the same. Am I incredibly dumb or how did a lot of people come up with a not-so-trivial idea that fast?
I did not like Problem D, as in my opinion it did not serve its purpose well, e.g. it wasn't a good problem to "balance" the round, and in my opinion Problem E was much easier than D.
Problem C has taken atleast a decade off my lifespan I think. How to do it?
binary search
How do you do D?
Count of all non-empty subsequences where there is at least one odd number, or the count of even numbers with the least LSB is even.
How did you come up with that least LSB thing? I wasn't able to solve this part.
This isn't a solution unless you explain why exactly these subsequences are good.
When an odd number exists we can think of the numbers as a single odd number and have their sequences combined as a one sequence symmetrical around $$$0$$$, where the sum will be $$$0$$$. Every other odd number can have its sequence symmetrical around $$$0$$$ on its own with $$$0$$$ sum as well.
When no odd numbers exist, the sequence sum corresponding to an even number $$$v$$$ is $$$\frac{v}{2}+c*v$$$ where $$$c$$$ is an arbitrary integer. We can re-write this as $$$v*c'$$$ where $$$c'$$$ is an odd number.
We want to partition such sums into $$$2$$$ partitions with equal sums (one of them is negative):
Could you give more details or example about this?
Suppose the starting sequence of any even number $$$v$$$ is $$$-(\frac{v}{2}-1)$$$, $$$-(\frac{v}{2}-2)$$$, $$$...$$$, $$$\frac{v}{2}-2$$$, $$$\frac{v}{2}-1$$$, $$$\frac{v}{2}$$$. The sum of this sequence is $$$\frac{v}{2}$$$. Whenever you shift this sequence $$$c$$$ units the sum changes by $$$c*v$$$. So we can generalize the sum formula as $$$\frac{v}{2}+c*v$$$.
Probably overkill, but this is how I came up with it.
For any $$$a_i$$$, the segment sum it can create is of the form $$$a_ix_i + \frac{a_i(a_i+1)}{2}$$$. For any subset $$$S$$$, we can say that:
By Bezout's lemma, $$$g = 2 \cdot gcd(a_i), i \in S$$$ must divide $$$\sum_i a_i^2 + a_i$$$ for a solution to exist. Let every $$$a_i = 2^{p_i} o_i$$$, where $$$o_i$$$ is odd. Then $$$g = 2^{min(p_i)+1}$$$ times some odd number. This odd part will surely divide the sum, so I'll just ignore it from now on. Now we have two cases:
This value is 0 if and only if we have an even number of $$$a_i$$$ such that $$$p_i = y$$$.
Basically the idea in D is consider a number b then sum of all possible subsequences of b consecutive integers would be of the form b/2+rb when b is even, where r varies from -infinity to +infinity and when b is odd then it would be 0+rb here also r varies from -infinity to +infinity so the final conclusion comes that those subsets would be good where the m=(summation of even nos.)/2 is divisible the GCD of the whole subset. Here we should not bother about the odd factor of GCD as the m would always be divisible by the odd factor of GCD. Main concern is the power of 2 .Now by slight observation you could on just need to not count those subsets ,consider the even factor of GCD to be 2^i where i>=1 then the no of occurrences of no divisible by 2^i but not divisible by 2^(i+1) has occurred odd no. of times .Now let the total count of these subsets be m then the final answer would be 2^n-1-m
Contest so hard, but anyone can give me hint for solving problem C.
Binary Search on answer
Not to say that the contest was bad, but problem F was quite known and problem I was very well-known. We gave some modification of problem F (with very similar solution, though) in a math summer school in 2018, where we took it from some Kolmogorov tournament, where it was from some obscure competition called "usa imo selection 2011" or smth, and problem I is just hackenbush, I looked it up in the Conway's ONAG.
GH seemed interesting, though
what actually you want from problem solver for problem A??
Hint 1: 0 <= ans <= 2
Hint 2: m == 1 && n == 1 => 0
I think he wants to understand the statement, not the solution. What you wrote is also kinda pointless because it's not obvious why these implications hold.
You have an $$$m\times n$$$ grid; you know one cell in this grid is chosen, for example $$$(x, y)$$$; you can choose $$$k$$$ cells from this grid. For each of these cells you choose, say $$$(x_i, y_i)$$$, you will be given the Manhattan distance from $$$(x_i, y_i)$$$ to $$$(x, y)$$$; then you are asked to determine $$$(x, y)$$$; now, the question is asking for the minimum number of cells you need to choose, which is $$$\text{min}(k)$$$, so that you can always find $$$(x, y)$$$ regardless of where it is in the grid.
Got MLE on F...
Imagine coming 2nd and still have negative delta. Couldn't be me.
I found B quite similar to this
Grandma Capa Knits a Scarf
I feel like I have seen Problem B in one of the previous cf rounds
https://mirror.codeforces.com/contest/1582/problem/C
I used same solution today, but got time limit exceeded.
That's because it's not the same problem. In round 750, the alphabet size is 26. You have enough time to brute force over all possible removals. A solution O(A*N) where A = alphabet size is fine.
In this round, A <= 200000. A solution O(A*N) is far too slow. Therefore an observation is required: how can we narrow down the pool of candidates for removal? It turns out we can limit the number of possible removals to 2 (and check the starting array), which allows for an O(N) solution.
Ohh, I felt it the same because I used the same O(n) logic in that problem too. Thanks for the clearance.
How many of you make at least 1 WA for problem A because the case m=n=1 ?
How many of you tried to implement dynamic programming on problem C and get stuck on it?
Me haha, spent half an hour on trying to make DP work but failed.
The case $$$n = m = 1$$$ on A is so dumb, at least include that in the samples. Do you want participants to solve problems or notice dumb edge cases? In general I am fine with a few sneaky edge cases but I think problem A is a bit special and should be as easy as possible.
+1. What I think is the worst is that the statement does not mention about the range of $$$k$$$, so it is incomplete (if strictly speaking). Such a "dumb" with an incomplete statement is... not good.
Due to this case i did't submit the solution till the last minute just because in the problems it is not mentioned that it is also possible that system return nothing.
nothing != zero
We can take it even further. Since there is no constraint on k. What is stopping me from asking -1 question to computer for $$$n = m = 1$$$ case. Where -1 denotes that instead of me computer asks me such queries and I reply correct Manthan distance for that query. I lost 90 pts and ACed A on 30th min after ACing B,C.
Authors could have added a "non-negative" keyboard before k, but all they wanted was to troll people on A.
Newbies smiling in the corner.
+1. I think that not including this case in samples was an absolute shame. Problems were good but this issue alone is sufficient to make me downvote the round.
I'm generally okay if the corner case involves some thinking. This one is, on the other hand, just boring and annoying.
Let's read the statement again. The author intentionally left out $$$k \geq 0$$$, which made the definition of giving $$$0$$$ cells to the computer and receiving $$$0$$$ numbers extremely unnatural. Do we even receive if we give nothing? If you hate contestants that much, please don't set the first problem.
Systests were super fast! :D Were pretests == full tests for most (if not all) the problems?
Pass pretests during the contest but finally TLE on the pretest 31 during system test :(
136677675
And the exactly same code passes after the contest:
136680689
How to solve E? Two pointers?
We can just greedy, consider a[i] is the smallest number in the array. We add the largest number a[n-1] to the set, then the next element is the largest that not bigger than a[k]=(a[n-1]+a[i])/2. Then the third should be the largest that not bigger than (a[k]+a[i])/2. My submission right after the contest :( https://mirror.codeforces.com/contest/1610/submission/136680210
Ok so i guessed that as long as every 3-tuple of the array is not terrible, then the array is good.
So under this condition the good sequences are $$$a_0,a_1,a_2,\ldots$$$ where $$$a_i \geq 2(a_{i-1}-a_0)+a_0$$$.
So actually there are only $$$log(10^9)$$$ distinct elements in each good subsequence and we can brute force each possible $$$a_0$$$. (Remember to handle equal elements properly or you might TLE).
How did you come up with $$$a_i \geq 2(a_{i-1}-a_0)$$$ condition? All along I had $$$a_i \geq 2*a_{i-1}-a_0$$$ on paper and it lead me to nowhere.
Nwm. Got an AC using it. Later I further relaxed that to $$$a_r-a_m \geq a_m-a_l$$$ and that was a mistake because I used $$$l=i,m=i+1,r=i+2$$$ after that.
Solved E almost in 1 hour but can't solve C or D in the remaining 2 hours..
Reaction in the third question ---> Although that was the easy one !
https://pbs.twimg.com/media/EN-dJiBUcAIr09l?format=jpg&name=large
how to solve C ?
Binary search https://mirror.codeforces.com/contest/1610/submission/136670710
Binary search on the range of answer
monotonicity: if we can invite some
kfriends, then we can invite somek-1friends. we want to find the smallestxs.t. we can't invitexfriends, then the answer will bex-1.the greedy strategy to check a
x: if we can invite somexfriends, and say the first (the poorest one among all invited friends) friend's index is $$$f$$$, then both $$$a_f \geq x-1$$$ and $$$b_f \geq 0$$$ must be satisfied. similarly, for the second invited friend whose index is $$$s$$$, $$$a_s \geq x-2$$$ and $$$b_s \geq 1$$$ must hold, ... and so on. so for a givenxwe can loop through all friends (from the poorest to the richest) and keep track of the number of current invited friends, then check whether we can indeed invitex(or more) friends in the end.https://mirror.codeforces.com/contest/1610/submission/136663604
wrong compiler :(
How to solve F?
A vertex can be an Oddysey vertex only if the weights of its incident edges have an odd sum. It turns out that it is always possible to make every such vertex an Oddysey vertex.
From well-known Euler path stuff, it is always possible to partition the edges of any finite graph with exactly $$$k$$$ odd-degree vertices into $$$k/2$$$ paths and some number of cycles, such that the path endpoints are exactly the $$$k$$$ odd-degree vertices. Do this for the subgraph consisting of weight-1 edges and for the subgraph consisting of weight-2 edges. Then we can direct the cycles arbitrarily and just need to direct the paths so that every vertex which is an endpoint of a path in both subgraphs has one path coming in and one going out. (But that can be done by the same routine!)
hey, is there a place i can read about this algorithm? (partition the edges of any finite graph with exactly k odd-degree vertices into k/2 paths and some number of cycles)
Once upon a time cf contests were good filled with beautiful tasks and nice ideas. And among all of them Persian contests were filled with nice graph dp problems as once Clix said. But now I see these contests filled with adhoc tasks and not quite programming for example this contest could be a perfect atcoder contest but in cf I expect seeing cf-like contests as I once did. I know people have different tastes of problems but in my opinion there are many nice sites for solving adhoc problem so let cf be for non-adhoc ones.
no need for mention
how is this supposed to be a global round?! just look at this submission for B
136651931
even a stupid chicken can clearly see that it will TLE. I find it strange that such retarded authors who can't even make decent pretests were allowed to create a global round.
Amshz :
i was confused why you are being so mean, until i saw the spoiler...
I'm a stupid chicken that floats on water. Can confirm that I can see that it will TLE
Not able to understand problem D, can anybody please explain what do we have to do.
My solutions aren't judged on system tests? WTF?
MikeMirzayanov hey man! can you fix this.
The edge case in A is the case with no edges
Can someone help me with this?
136659367
Don't know why it is not passing testcases.
Here's my working submission: 136686415. The mistake is that in Java comparing Integers using
==is unreliable. Better to compare integers using.equals().Thanks a lot for finding out the problem.
Don't you think it was compiler's fault?
Emm, no. It's just that == compares by object's reference, which is not what you expect when comparing integers.
I don't think it's a valid point. The program ran successfully for so many testcases comparing integers with ==
Read about java primitives/wrappers comparison and integer pool
This is not true. read here
I have 2 friends that asked about if k can be equal to zero in problem A and they got a "yes" reply , how come this wasn't posted to all of us in global clarifications , very unfair
If there is anything unfair about it it is the fact that your friends were given a reply. Obviously it is part of the problem to understand what the possible answers are.
I completely agree,the reply given basically spoils the solution
I disagree.
I think the statement was poorly written and should have clarified in at least some way that k could be zero.
However, I also think that if someone realizes "oh, it could be zero" and then asks if that is allowed, at that point they have already figured out the insight and replying to their message doesn't spoil the problem.
In C, I see lots of solutions using
int mid = (low + high + 1) >> 1;instead of the usualint mid = (low + high) >> 1;. Can someone explain why?For convenience only. Imagine you have some condition
condwhich is true for allx <= band false for allx > b(just like in task C). Now you want to find the smallest integer numberxfor whichcond(x) == false(it isb + 1as you can see). Typically your code will look something like the following:Imagine now, that the task has changed and now you wanna find the greatest number
xfor whichcond(x) == true. Of course you can use the same code as above, but sometimes you will have to write additional conditional expressions for border cases. However in some cases we can use another approach without any additional code:In the second code example we cannot use
int mid = (low + high) >> 1;, becausehighmay be invalidated in casehigh = low + 1before last iteration. That's why it is necessary to add one in the second approach.This round not for beginners ....i am fullly depressed
Just got back to solving problem D since I couldn't solve it in the contest, and it is really a cool problem in my opinion.
When I came back I had my dark-mode filter enabled and found a funny easter egg in the statement! I won't ruin the fun for you so go find it yourself xD
But I'm writing this to ask, who is the problem setter for problem D?
Good to see someone found it :)
[edit:] guess who. Hind: Someone who doesn't have Lee in their username and they are not from China.
I'm low-key writing the comment to let more people discover it :P
Would it make sense to have an option to buy tshirts if you are in the top 500, but not in the randomly selected list?
The problem is it's not guarantied that the t-shirt will actually reach you in finite time. So if you buy, then they have to fix it I think, hard to fix...
:D
Can anyone understand why my Python solution for B has been TLEd when it looks the same as other python solutions that were accepted? https://mirror.codeforces.com/contest/1610/submission/136645557
Your code should not pass because it's $$$O(n^2)$$$.
Problem A lacks the sense of clarification
Thanks for this great contest!
Author of problem A might not have survived in ancient greece
Actually its the first time I appreciate living in Iran...
Random works in problem F? 136677110
MikeMirzayanov, there is something weird going on with difficulty of problem H (it is currently 2100), which is clearly not the correct rating.
PS: It is fixed now, thanks.
Shout out to everyone who solved D, you deserve massive respect. After reading the solution for 2h I barely understand it...
Congratulations to tshirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.
As usual, we used the following two scripts for generating random winners, seed is the score of the winner.