Hello Codeforces!
On Nov/26/2022 17:05 (Moscow time) we will host Codeforces Global Round 24. Note the unusual time of the round.
It is the sixth round of a 2022 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 2022:
- 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 2022 supported the global rounds initiative!
The problems were written and prepared by Cocoly1990, waaitg and Imakf. 👀👀👀
We would also like to thank:
- errorgorn for 🥵 and 🥶 coordination.
- KAN for translating the problems. 🥳🥳🥳
- Wolam for proposing
rejectedproblems. 😭😭😭 - Our testers for testing and providing invaluable feedbacks: Rebelz, Sugar_fan, ShmilyTY, dXqwq, Aestas16, SSerxhs, Qiulyqwq, Leasier, Yakumo_Ran, Nanako, Celtic, JohnVictor, installb, mafailure, CuiZhenhang, lunchbox, _rey, Wolam, apeiya, mejiamejia, TomiokapEace, QAQ_QWQ, mkisic, Mahfel, luanmenglei, ak2006 and NishikigiChisato. 😋😋😋
- MikeMirzayanov for amazing platform Codeforces and Polygon. 🥰🥰🥰
Round Information:
- Duration: 2 hours and 30 minutes 🔥🔥🔥
- Number of problems: 8 problems, one split into 3 subtasks 🤯🤯🤯
- Score distribution: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$1750$$$ — $$$2250$$$ — $$$2250$$$ — $$$(2000+500+500)$$$ — $$$3500$$$ 🤤🤤🤤
- There is an interactive problem, so please see the guide of interactive problems if you are not familiar with it. 🤭🤭🤭
As always, hope you all gain non-negative ratings $$$\Delta$$$ in this round! 🍾🍾🍾
UPD1: Editorial
Auto comment: topic has been updated by Imakf (previous revision, new revision, compare).
As a participant, I hope the problems are interesting!
These were indeed interesting problems, the difficulty gap b/w D and E was a bit high tho
Yes, agreed!
As a participant, I hope the problems are interesting!
As a tester, Imakf 🤤🤤🤤
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
omg 3 subtasks round
Haha I break the order
omg 3 subtasks round
omg 3 subtasks round
As a tester, I can say that the problems are all very interesting. Thank you for your participation.❤️❤️❤️
As a tester, I must say that the problems are all very nice.
Genius lgm problemsetter imakf, I'm a big fan of yours! orz imakf, orz waaitg, orz Cocoly1990!
So basically everyone who solves $$$G2$$$ and $$$G3$$$ gets $$$150$$$ more points each.
As we all know, a problem can be split into subtasks only when it's difficult to solve completely.
I should have read this comment before the round xD
No matter how the round turns out, had to upvote for the emojis 😌
As a tester, I have to say that all the problems are very interesting!
orz Cocoly1990, Imakf and waaitg!
Wait are you the guy who (up)hacked 120 submissions in my round?
Yes, I uphacked some submissions using slow-output functions or languages in your round.
Note unusual timing
As a writer,i want contribution.
stO Cocoly1990 Orz
downvoted/ng.
omg emoji round
As a tester I can say that you will really enjoy the problemset. I would suggest you to read all the problems. Problemsetters and errorgorn have tried their best to make statements easier to understand.
As a tester, Orz Cocoly1990.
As a participant, Orz Cocoly1990.
Editorial filled with emotes lol... My reaction for the Global Round as usual ^,^
Orz Imakf <《^,^》>
The last line is completely illegal, how will be the ratings gonna balanced than?
Everyone gets a 0 lol
As a tester, i think that the problems are all very interesting.
All the problems are very interesting!
orz Cocoly1990, Imakf and waaitg!
Consecutive rounds! :O
Too many emojis, downvoted. Hope the contest is good tho.
you must be single.
True
Because I'm also, so True & True
As a tester, I'm still curious how the authors found me for testing, I didn't know any of authors :D
btw, don't miss this great, well prepared round from such awesome authors!
As a first time tester, this is definitely the best round I ever tested
Note :: UNUSUAL TIME OF CONTEST
Brillant use of emojis
omg emoji round
Oops
as a participant I hope I will get +100 delta.
I want another ConstructForces like 836 div.
There are 10 subtasks, but I have a feeling only 4 would be doable by < master. Let's see, excited. Hopefully master tomorrow!
Thank you coddeforces
hoping to solve upto D!! :)
hopefully no choking this round
Celtic /se
Chinese round! /tyt
Hello everyone, I am a beginner programmer. I don’t know about the difficulty of Global round 24 . Anyone could explain about difficulty of problem in this round.
Very difficult
Because of my university online exam in contest time. I can't participate in this round. Feeling sad.
Good luck with the exam. :(
Proceeds to fuck up both
Task failed successfully :)
https://codeforces.net/contestInvitation/e949aed8ba775616b4e21b10a0c1480426f6ff8a
Emojforces ☺️
Hope for fun with the interactive one and (3 subtasks) one .Best of luck everyone.
nice emoji
Does score distribution imply that I should skip to G1 after D.
Everyone for good luck!
omg Imakf round
As a participant, this round is my decisive battle.
I lost this game. Though I will got $$$+\varepsilon$$$, my place is around 200 (without any FST).
Anyway, the round seems good. Though some problems are typical, I love E! Thanks for the writers' and testers' amazing works!
As a lottery winner...
don't expect much you will do better.
G1 easier than F, E .. intersting :)
So G has 3 subtasks? XD
The problems are good quality.It suprised me very much.I am looking forward to more contests!
Solution videos for problem B on youtube combined have over 1600 views.
Unfortunately, people who uploaded videos didn't show their usernames, but one of them has to be vedantkakade.
MikeMirzayanov
The top standings in this contest are a good example of why the scoring system needs to be reformed, in my opinion.
Why is that? Looks like several top scorers were saved by the pretests which allowed them to resubmit. But the penalty put them beneath other submitters who didn't need as many resubmissions.
You have mentioned just penalty aspect when OP (brunovsky, correct me if I'm wrong) is talking about general scoring mechanism. Which is, basically, how many points you will get for solving particular problem at particular moment. The issue is well-illustrated by top-1 scorer who gets more points for speed-solving D (1666/1750) then for late solutions to much harder F (1523/2250) or G1+G2 (1536/2500).
:|
Contest is not over yet. Delete it.
There are people who does cheat but using different ways but you my guy did this in the comment section....you could have waited for the round to be over
Why is div1+2 D so hard again?
Yeah It was hard and was also interesting. Couldn't solve it though.
the solutions to the first three problems were on youtube before the test was over, I think this interferes with the scoring of the round as many can copy and paste the solutions.
How did you find these videos?
haha lol!!
What was the logic in number B?
If all the numbers have common divisor or factor, then the ans will be
maxElement / commonFactoror else ans will bemaxElement. Here you can find if the numbers have common factor by takinggcdof the whole array, and ifgcd > 1then it does have a common factor.How could C be approached?
You can think of dividing the vertices into 2 parts. eg.
1 2 2 3 3 4 4 4 5 6 7 7 9can be divided into two part as following :IMP : sort the vertices by their weight
1)
1and2 2 3 3 4 4 4 5 6 7 7 9, Now you can connect the left part's vertices to all the vertices of right part but you cannot connect any vertices of the same part, so total possible edges =len(left_part) * len(right_part)= 112)
1 2and2 3 3 4 4 4 5 6 7 7 9, but this configuration is invalid, as you can imagine that left's2is connected to right's2&9so basically you can go 2 => 2 => 9. So here you have to make sure that partition are done in such a way that there are no equal element in both partitions.left_partis strictly less thanright_partelements.so best configuration we can find is :
1 2 2 3 3*4 4 4 6 7 7 9which is 5 * 7 = 35Also edge case is when you can't partition the array. i.e all the elements are equal, so at that time just output
n / 2as you cannot connect more than 2 verticesthe maximum number of edges can be achieved when the graph is only 1 connected component.
For each value a[i] , let A be the set having all values less than a[i] , and let B be the set having all values greater than a[i] note that you cannot make edges from a[i] to some x in A then from a[i] to some y in B because that will violate the condition in the statement ( you have edge from y to a[i] and edge from x to a[i] and (x <= a[i] <= y)
from this point you can match every a[i] with every x in A then match every x in A with every y in B
OR
you can match every a[i] with every y in B then match every y in B with every x in A
and just handle the case when all elements are equal (every two nodes form a connected component)
Scariest problem D
How to solve D?
Solution for D:
Observe:when the deleted pegs firstly form a continuous segment with a length of $$$l \geq n/2 $$$,we get a scheme.
Enumeration length $$$l=n/2,n/2+1,...,n-1$$$,let's calculate the answer when the continuous segment's length is $$$l$$$.
First,calculate $$$cnt$$$,which is the number of pair $$$(a,b)$$$ satisfying $$$a+1+b==l,a,b<n/2$$$.
Then select some pegs outside this continuous segment that can be deleted.
Suppose $$$i$$$ pegs(outside) have chosen, there are $$$C(n-l-2,i)$$$ schemes.
The total answer is $$$cnt * \Sigma ((l-1+i)! * C(n-l-2,i)) $$$.
Because the beginning of a continuous segment can be any peg, we need to multiply the final answer by $$$n$$$.
Thanks for your clear explanation!
how to solve B?
Anyone has the answer in D.(answer like O(1))?I mean an explicit formula
What a tough contest :(((
C was quite tough to spot the right answer.
I do agree
i was going in the direction of frequency and hashmap that how many smaller elements can be between 2 greater elements or how many greater can be between 2 smaller
please provide a hint
The brief idea is to sort the array and split it in half then connect every edges between two halves. This won't violate the rule. Now you have to consider the case where there are same elements (which is a little bit complicate).
You're right.I spent an hour and a half doing problem C.
I guessed the solution but I can't prove it
Solved problem F in a Div 1+2 Round for the first time! Yay
Why FST...sad
How to solve Problem D when n % 2 = 1?
In even cases, ig we had to consider diagonals, so, in the odd ones triangles?
In fact, it is wrong to consider diagonal.
Consider $$$n=6$$$,$$$[1,3,5,6]$$$ is a valid scheme,although $$$1,3,5$$$ deleted all diagonals.
Oh, I was thinking about calculating the ways in which the game ends with either a diagonal or a triangle 'breaking'.
In the above case, the triangle 4-2-6 'breaks' in the end.
I forgot to consider 'triangles' for even cases as well.
D actually ended up being fun lol
how did you solve it?
combinatorics
after all operations we must be left with some chunk with size $$$\le (n + 1) / 2$$$ (and possibly gaps in between).
The last operation must've been removing a peg in the diametrically opposite chunk.
Then just count the number of ways to do this using binomial coefficients and factorial
Only solved till C but my best div 2 round so far.
Any hint of problem C , (PLEASE DON'T GIVE COMPLETE SOLUTION)
You should think about the GCD.
That's for problem B
Quick sort partitions
... How many roads can you make with n nodes of height 1 and m nodes of height 2?
... How many roads can you make with 2 roads of height 1, 4 nodes of height 2, and 3 nodes of height 3?
If you need more help just reply!
182673131
what was the problem in this approach can anyone tell ? i was checking if all were divisible! if then ans is max/min else ans is max why i got WA in this approach didn't understand
answer is $$$\max(S)\div\gcd(S)$$$
what if i don't go for GCD then?
then you get WA...
got it [15, 20, 25] here 20 & 25 is not divisible by 15 but all are multiple of 5 so answer is 25/5= 5 that's why gcd works
Here is some feedback on the problem set:
Overall the contest was very well prepared, the problems were nice, and the difficulties were on the spot. Congratulations to the authors!
On G, I had the following order of observations:
1) You can find the maximum value in ~10 queries
2) There are only at most two values which are unpaired with $$$k=2$$$: $$$1$$$, and potentially the maximum value.
I couldn't finish from here in the contest, but someone gave me a hint afterward: The idea is that we can query $$$[a, m]$$$ and $$$[m+1, b]$$$ for a range $$$[a,b]$$$ and $$$m = (a+b)/2$$$. This tells us how many unpaired values there are on the left and right; since there are atmost two unpaired values, we can go to the correct side.
Auto comment: topic has been updated by Imakf (previous revision, new revision, compare).
Please dont do cheating guys,it hurts alot especially in rankings and ratings
Why does taking gcd of the whole array and then dividing it by the last number work in Problem B?
$$$\gcd(x,y) \vert x$$$ and $$$\gcd(x, y) \vert y \Rightarrow \gcd(x, y) \vert (x - y)$$$
Thus any element we add will still be a multiple of the $$$\gcd$$$ of the entire set.
However, by the Euclidean algorithm, we can always get $$$\gcd(S)$$$ to be in $$$S$$$ after some number of operations.
Thus we can get $$$\max(S) - k\cdot\gcd(S)$$$ to be in $$$S$$$ for any $$$k=0,1,2,\cdots,\frac{\max(S)}{\gcd(S)}-1$$$ (For greater k values the number would not be positive)
Thus the max size of $$$S$$$ is $$$\max(S)\div \gcd(S)$$$
Thank you very much, great explanation!!!
It is kind of clever use of gcd algorithm that one learns in high school, i.e. gcd(x,y)=ax+by for some a and b.
Note that if 1 is in array, then you can construct any element from 1 to a[n-1], and if you can construct 1 then also you can construct any element from 1 to a[n-1]. (basically you can construct 1 only if two elements have gcd 1 in the array).
Similarly, you can work it otherwise.
Bezout's Lemma! yay
I don't have a formal proof, but this is what I thought of :
Base : If array has
1or we managed to generate1then it is possible to generate each and every element from1....max(array).Now let's do some case work :
1) gcd is 1 for the whole array, so it means that there lies 2 elements which does not have common divisor, so let's assume it as 4 and 599, now you can generate values as 599 — 4, 599 — (4 * 2), ....., 599 — (4 * x), now this
599 - (4 * x)term will be surely < 4 as we already know that we can't reach to 4 as 599 is not divisble by 4. so any value of 1, 2, or 3. Now in case of 1 & 3, we can generate 1 by either (4 — 3) or (4 — 1) = 3 then (4 — 3) = 1. so we generated 1. Now if we have 2 then (4 — 2) is 2, but again 599 & 2 are not divisble, so 599 — 2, 599 — (2 * 2), and ..... we will get last value as 1. So in short whenever we have non divisible numbers we can go upto 1 for generation by successive subtraction.2) gcd > 1, let's say gcd is 5, so now whatever you do in the array your subtractions will result into a multiple of 5 as when you subtract two number which has
xas common divisor, you will have a result that will also be divisible byx. so you have to output the number of multiple of gcd that you can fit in the arrayso ans is =>
max(array) / gcd(array)Who else agrees that the 2nd sample test case for problem C should be explained as well
that would give up solution
So close to solving D.
if n is even, go over all pairwise points, pretend this is the arc when it first touches the blue pin. We know that this can only happen with the smaller arch, and that the last point removed before it gets to this arc must be one of the opposite pin with the smaller arc. From there just do nCk and multiplies with factorial of two sets of points.
if n is odd, solve similarly, except the outer arcs count before getting to this arc is the number of edges of adjacent pin instead of the number of points.
Don't loop over all pairwise points, but instead over all possible arc lengths when it touches the blue pin and then multiply by n.
a similar problem as problem B: https://codeforces.net/contest/347/problem/C
A similar problem appeared recently but with lower constraints so you could simply add the missing numbers while you there's a missing number. I couldn't find it but I'm pretty sure it's in a CF round that happened durin 2020-2022.
mmm an even more similar problem lol https://mycode.prepbytes.com/problems/sorting/ELMT
Thanks for the fast editorial! Also thanks for the round.
Problem E:
How can the answer of input
1
3 5
3 2
2 1
1 2
be "YES"?
I got WA2 and this is the case I failed :(
Use permutation [2, 3, 1], then 1, 3, 5 can be colored in this order.
Thank you for problem G!
Actually reloaded the page a couple of times to make sure it's $$$\le 30$$$ queries, not $$$30 n$$$ or something.
The feeling of just how impossible the problem seems at first... priceless.
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
B is pretty hard for usual B imo. It’s an easier version of a 1800 rated problem. And that problem has negative numbers
it’s so bizarre that B has so many submission.
it's not too hard to guess after looking at a few cases
Can you link that problem?
https://www.geeksforgeeks.org/maximum-difference-elements-that-can-added-to-a-set/
finally a round i enjoyed :)...
Completely forgot that on resubmission previous submissions are skipped, Resubmitted D for stupid reason, got -50 and +25 minutes.:(
Thanks for the great problems and well-balanced round!
The only negative thing I noticed is score distribution. Complexity jumps between A-B and B-C is definitely smaller then the ones between C-D and D-G1 (cannot say about other problems), but the point difference is two times bigger.
Anyways, kudos to the problem setters and testers for an awesome job!
Thanks for the round! I think F is incredible, and C is fun too.
Problem D really pegged me.
Intially I thought of Bipartite Solution
">" -> Red edges, "<" -> blue edges and then For "=" I did not understand which color to assign and thought Bipartite wouldn't fit.
To add Fire to above thought. I came up with a pattern which is giving solution for 2nd example
1) sort the array 1 2 2 4 5 5 In Most of Hill and valley problems this pattern helps 2) And use the pattern [a1,a2,a3,a4,a5,a6] => [a1,a4,a2,a5,a3,a6] 3) In above pattern if we connect edges to adjacent and also connect each vertex with every vertex alternatively I got all the edges so dumped the idea of bipartite and tried to code the above approach
What is that C question ?. I tried it for almost one day. I went nowhere
I did it considering a bipartite graph(maximum edges it can have is x^2/4 , x->vertices). Check out my submission for this problem.
UnRated?
by somehow it's just rated again
For me, E is very very easy, even easier than C. I can't understand why people struggle with it. When I saw problem E I was like, well, this problem can't be just a straightforward greedy problem, there must be something that I missed, but indeed it is. You just sort the colors by $$$x$$$ and then find the maximum position that could be colored by colors other than $$$1$$$. I did struggle a lot on C and D. In C I didn't realize that the resulting graph could only be a bipartite graph, In D I ended up with a much more complicated approach using Inclusion-Exclusion Principle. To be clear, I'm not complaining, I'm just curious that maybe some people would have the same feeling as mine.
I think my F would be a little better than std.
The beauty of this problem lies in $$$f(x,x)$$$. It is not difficult to find that the closer the point to $$$x$$$, the more times the point is repeated, and the different $$$x$$$, the different times each edge is repeated ~~ (isn't it obvious) . So we can actually figure out the distance between any two points based on this property. Here's an example (in the figure, the red number indicates the number of counts) :
You will find that all the edges are repeated the same number of times except for the number of times that the edges between the two $$$x$$$are repeated, so you can consider the inclusion repulsion, which is actually $$$dis_{x_1,x_1}+dis_{x_2,x_2}-2 \times dis_{x_1,x_2}$$$. This should make sense, and when you're done, you actually find that the point between the two $$$x$$$has been calculated exactly $$$n$$$. In fact, it is easy to prove that for $$$2 \times dis_{x_1,x_2}$$$the middle of the two $$$x$$$must not be counted because it is already looped, And then $$$dis_{x_1,x_1}+dis_{x_2,x_2}$$$actually understands that every point is on the edge between these two $$$x$$$, so repeat the $$$n$$$ calculation. So we've figured out the distance between any two points, and now we want to generate a tree, and in order to satisfy the distance that we figured out before, we need to minimize each edge, so we need to minimize the spanning tree.
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.
WHOOOOOOOOOOOOOOOOOOOOOOOOO
Yoooooooooo