Hello, Codeforces!
We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2024, we will hold 4 such rounds. The series results will take into account the best 3 participations out of 4.
On Dec/19/2024 17:35 (Moscow time) we will host Codeforces Global Round 28. 
Codeforces Global Round 28 marks the fourth round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.
The prizes for this round are as follows:
- The top 30 participants will receive a t-shirt.
- 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.
The prizes for the 4-round series in 2024:
- In each round, the top-100 participants get points according to the table.
- A participant's final score will be the sum of the points they earned in their 3 highest-placing rounds.
- The top 20 participants across the series will receive sweatshirts and placement certificates.
We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2024!
The 9 problems were authored by our 4 authors: JoesSR, cmk666, NetSpeed1 and Little09.
We would also like to thank:
- Our coordinator 244mhq.
- Our friends who discussed the task with us zjy2008, Zhouershan, LXH-cat, 5ab, cyb1010.
- Our testers zhoukangyang, Um_nik, 275307894a, A_G, JCY_, A_zjzj, umbrella-leaf, _istil, zltzlt, Daniel777, Error_Yuan, lgswdn, gyydp123_LIM, Daniel081024, omeganot, jimmyywang, Meatherm, operator_, Imdie, chengcheng5677, Xiaohuba, ikira.57, Hanghang007, Chenly, angryarabianman, 0x4f, Hori, GusavoIsYou, Jerry_H, newb_programmer, CuteWhite, Abracadaber, Union_of_Britain, ishaandas1, dazlersan1, OIer_Chtholly.
- 244mhq for translating the statements to Russian.
- MikeMirzayanov for creating the Codeforces platform.
Round Information:
- Duration: 180 minutes.
- Number of problems: 9 problems with 1 subtask.
- Score distribution: $$$ 250 - 500 - 1000 - 1250 - 1750 - 2000 - 2250 - 2750 - (3000 + 3000) $$$.
We eagerly anticipate your participation!
UPD:
Congrats to the winners!
First Solves:
A: dXqwq
B: dXqwq
C: Marcin_smu
D: jiangly
E: sevlll777
F: dXqwq
G: BlackLily
H: jiangly
I1: jiangly
I2: nobody solved
UPD2: Editorial.
As a tester, I enjoyed the problems a lot!
As a tester, I enjoyed watching you suffer.
Should I be worried?
yes definitely :)
Hold on, should we create a team? the cow gang perhaps
we already have that group and we have a discord server :)
How did u guys
mooknow each others despite living in differentgrasslandscountries? And may I join?but are you a cow?
Hint: this is a cow: cowthecow
as a vessel, I have no voice to cry suffering.
Context: I had 30 wrong submits to F before getting AC
As a contestant, I enjoyed the problems a lot!
Super excited for Global Round 28! Big thanks to the authors, testers, and XTX Markets for bringing us these amazing rounds. Let’s have fun solving the problems—good luck to everyone competing
expecting increase
As an author, I hope you have fun & enjoy the problems!
As a tester, I tested.
(3000+3000). it seems a quite hard problem
Little unlucky it is during Saint Nicholas
As a discussant, I am glad with friends' problems.
As a discussant, I discussed.
December 19 is my birthday.
But will do a contest that day.
Edit: Thanks to everyone!
happy birthday
happy birthday
Happy Birthday bro :p
As one of the authors, I hope you enjoy our problems!
As a tester, I won't get negative delta :)
As a tester, I wish everyone good luck! :)
As a tester, I want to gain Contribution.
As a tester, I can confirm that this round does indeed have problems.
As one of the authors, I hope you enjoy our problems!
As a, I can
practice a lot for this round , hoping for increase
I’m close to reaching Pupil and only need six more rating points. Should I participate in this contest or focus on practicing more before competing again? Experienced people, give me suggestions. Do you think I have a good chance of reaching Pupil if I participate in this contest?
Don't think about such stuff and just participate for the thrill of it. Anyways Pupil is very early to even think about such stuff anyways.
Competing in live contests is a skill you should practice. Also, you will improve faster if you worry less about rating.
go for VCs (virtual participate) if you're not so sure about your performance.
Of course it's only available after the contest and the thrill of live contest is not there... But hey it's good practice and doesn't affect your rating if you scare about negative delta.
All the best everyone.
As a newbie, I would like some suggestions please. My first contest was Codeforces Round 993 (Div. 4) and I got the first 3 questions right only. Do you think I should try on this one too. Will it be too hard? Thanks! >(>-<)<❤️.
Estimation (no guarantees) : You should get first two questions at least I guess.
As a tester, I tested the round in order not to lose rating on my birthday, but I'm afraid I was wrong.
I greatly enjoy the problems and hope you will feel the same too! I'd love to see you showing your own record of positive delta under this comment, after the contest has ended >w<
Happy Birthday in advance!
Happy birthday! And then I will try to revenge... Can I beat CN Round this time?
edit: I did it!
Happy Birthday!
As a teter, I confirm this round has been tested
As a participant I've a
antontrygubO_o will be LGM once Again !
Why does mhq coordinate
Hoping I could get into expert :D
you did it!
Im pretty happy but sad because I think i could get E if i were push myself harfer T_T
As a participant, I am upset that cry is not a writer.
As a Xanlar, you are my friend.
omg tourist
No, I am specialist.
Newbie question ,is this contest rated
yes beluga as long as you are not invisible.
297192033 I am not able to get the testcase which is wrong. How should I be able to get the 93rd testcase?
wrong place :/
1 -> how did you find this test case?
2-> Is this the 93rd testcase?
3-> Max diff will be wrong for cases like 5 4 3 1 2 as the max diff I will get for this will be 5 (according to my code). I guess I will have to come up with a better solution. Thank you <3
i find this test case by just observing your wrong approach. But u can do stress test but for this type of ad-hoc problem stress test isn't effective, cause you idea is wrong actually.
Any tips how to maintain focus during the 3 hours of the contest?
it's strange. in my whole day, I can't focus on anything properly.
but when I am in a contest I have laser focus.
Contest ID: 2048
So ...
Notorious Coincidence : Problem B was a task coauthored with chromate00 , but unluckily it appeared in today's round (It was good to be top $$$90$$$) for $$$10$$$ minutes of the round.
My Editorial for the problem :
$$$\textbf{Hint 1}$$$ : The problem can be rephrased to :
$$$\textbf{Hint 2}$$$ : Assume you want to evaluate the sum (without construction) thus the sum is :
Take a look at some examples , Let's take $$$(3,2),(5,3)$$$ , For first case we've
It's optimal to maximize contribution about sub-permutations of minimum elements
thus It's optimal to place first
with minimum numbers in each index that is multiple of $k$ , and the rest indices can be filled in anyway (For example : fill missing elements in reverse order from larges to smallest).
Complexity is $$$\displaystyle \mathcal{O}(n+\frac{n}{k})=\mathcal{O}(n)$$$
Thank you.
I'm glad that It helped
What's going on, why E fails on pretest 2, who had this issue?
Wrong solution bro
My solution is based on the observation that edges of a complete graph on 2n vertices can be distributed into n non-intersecting hamiltonian paths.
In your solution, two adjacent vertices of the Hamiltonian path may be in the same fraction
Today I learned that stack size on CF is not unlimited.
ok so how do i solve F cuz i tunnel visioned so hard on it i spent 2 ENTIRE HOURS with PRACTIALLY 0 PROGRESS done
Consider DP(L,R, t) = max ai in [L,R] after t operations within in. Notice that if I do operation on smallest bi, might as well do whole [L,R], so in essence you can break the DP into smaller ranges split up by the indices of bi, then compute for each smaller ranges and combine the DPs. Then compute DP for the big range. Notice t is at most 60. So time complexity is like n 60^2. (We have n ranges to do dp on) Also, to const opt if bi > 2, make t like 40 or smth.
how to solve E!
I can at least explain why the answer is NO if m>=2*n:
Now let's say each of the n colors forms a spanning tree, then it takes n*(2*n+m-1) edges total
Now this number must be >=2*n*m=total number of edges. Solving this gives m<=2*n-1
nice! I never even thought of it like that.
Does anyone solve D with square root decomposition? (Finding the sum of every kth element starting from position s)
no of source can be at most n and jump(k) is 1 to m. do brute force. nlogn complexity. why need sqrt decomposition here?
what do you mean by source?
By bad! overkill :(
How to solve D?
hint: n + n/2 + n/3 + n/4 ...
E is cancer.
In E, For n=3 and m=7, in the example, it says no pattern is possible.
Can someone please suggest why this is an invalid solution?
1 2 3 1 3 2 1
1 2 3 2 1 3 2
2 3 1 3 2 1 1
2 3 1 1 3 2 3
3 1 2 2 1 3 2
3 1 2 3 2 1 3
As per my understanding, it should be possible for all m between 1 and k, where k is the number of permutations of (1 1 2 2 ... n n), all of which can behave as the columns of the answer matrix.
L1 — R7 — L3 — R3 — L4 — R4 — L1 makes a monochromatic cycle
Okk, Thanks :)
Understood my mistake
in row 2 and row 5. two times number '2' is matching.
Problem E was very similar to AGC061B. I used the same pattern as a last hope and got AC. My disappointment is immeasurable, and my day is ruined.
Really cool round, thanks! I had fun on all of Problems C-I. The statements are so natural and the solution is thinking-oriented. Also now that I got I1 right, it surprised me that I2 is doable...!
What's the reason for high constraints in F? Is there a solution better than $$$O(Nlog^2C)$$$ or $$$O(NlogCloglogC)$$$, or were there unintended solutions that passed with lower constraints?
P.S. The problems were good!
You can use two-pointers to make it $$$O(N\log C)$$$
I don't understand :( In contest I only thought of using min-plus convolution (which is two-pointer like maybe?), but I don't think the values are convex
For two non-increasing array a[i], b[i], let c[i] = min(0<=j<=i)(max(a[j],b[i-j])), then the optimal j is non-decreasing when i increases. You can check this by drawing function image of a[j] and b[i-j] for different i.
This round makes me wishing to stop playing Identity V
I HATE problem E, i'm pretty sure most of the AC just guessed it.
i guessed that m>=2*n is sufficient for the check, but it kinda does make sense
The proof of this is that the subgraph with edges of one color must form a forest. Thus each color must have at most $$$2n + m - 1$$$ edges of that color. So in total the number of edges should be at most $$$(2n + m - 1) \cdot n$$$. But there are $$$2mn$$$ edges. Thus
Ahh i had the 2n+m-1 written down, but i did not write the inequality down, thank you very much!
You can also think about it this way (which is basically the same proof). If $$$m = n$$$, then you have $$$4n^2$$$ edges and at least one color should use $$$4n$$$ edges. But a forest on $$$4n$$$ vertices can have at most $$$4n - 1$$$ edges, so there's definitely will be a cycle.
Also if $$$m$$$ is strictly greater than $$$n$$$, you can always consider any part of this graph with $$$2n$$$ vertices on the left, and exactly $$$2n$$$ vertices on the right, since this subgraph will contain a cycle for the same reason.
Didn't solved F in contest, because 200000*61*8 bytes (=93.08MB) make stack overflowed... First time get so much negative delta because of stack overflow (error code 3221225725)
Is it hard to rewrite your solution using stack to store dp states?
It's not hard to do this but I realized that after contest ended.
what could be the possible rating of problem D ?
My general idea of F:
Assume we choose intervals
[l, r]such that the minimum value in the rangeb[l..r], denoted asmn. We need to ensure that the selected intervals are local maxima. In other words, for an interval[l, r]:(l == 1 || b[l-1] < mn).(r == n || b[r+1] < mn).This leads to intervals forming a tree structure, where each node represents a valid interval
[l, r]with the minimum value within it.Consider the array
b[] = [3, 2, 3, 4, 2, 3]. The tree structure of valid intervals and their corresponding minimum values is:We can perform a greedy strategy on this tree, selecting the optimal ranges at each step:
[1, 6]has a minimum value of2. We choose this range untila[2] = a[5] = 1(2 and 5 only appear in root node).[1, 1]untila[1] = 1,[3, 4]untila[3] = 1, and[6, 6]untila[6] = 1.[4, 4]untila[4] = 1.But I'm not sure whether the order of operations (specifically the sequence of selecting intervals) will change the result. Is my idea roughly correct?
We can solve this problem by dp. Let dp(u, t) be the minimum value of (maximum value of a[i] on the subtree of u) if you do t operations on the subtree of u. Note that 2^60>=10^18 so t<=60. So when need to merge dp status from lc and rc: we have merged(i) = min (0<=j<=i) (max(dp(lc, j), dp(rc, i-j)). Note that the optimal j is non-decreasing when i increases, so we can merge them in O(log(A)). Then we need to used the merged value to calculate dp(u): We have dp(u, t) = min(0<=s<=t) (ceil(max(merged(s), a[u]) / b[u]^(t-s))), which means dp(u, t) = min(max(merged(s), a[u]), ceil(dp(u, t-1)/b[u])).
I overcooked so hard in C. Used a reduction to Z-functions. Probably wrong :)
Below is my solution. Counter-examples and hacks appreciated.
https://mirror.codeforces.com/contest/2048/submission/297300355
Funny, problem C seems a bit reminiscing towards 1743D - Problem with Random Tests (not really the same, XOR instead of OR there and only applying to the $$$n \le 1000$$$ subset). I guess just solving that one earlier today gave me a slight edge XD
how long has it been since you solved it ? Do u tend to remember the problems which u practice or they just stay at the back of your mind ?
Literally 6 hours before this contest, just coincidental. I don't remember much, if anything I remember the honed coding technique the most.
I changed E to Fill in a matrix with 2n rows and m columns so that the xor of the four corners of any submatrix are not equal to 0. But why this construction is not corret?
You can go from L1, R3, L4, R4, L2, R2, L3, R1 and back to L1. Here L and R are the two sets of the bipartite graph.
thanks, my thoughts was too naive :(
wasn't C solvable in O(n), why were the constraints n <= 5000??
Do not think so.Solved with O(n2)
Just choose indices for the second substring in such a way that the beginning of the string is aligned with the leftmost zero. And if there are consecutive zeros starting from the leftmost, then you go leftwards until you either meet the beginning of the string or the number of steps equals the number of consecutive zeros minus one.
how?
FFT 😂
Actually the original problem has $$$n \le 10^5$$$ (and it's div2 B), but we have to make it easier (and come up with an even easier 2B) to make the difficulty reasonable.
haha I see. Just that I often look at the constraints as well to come up with solution. So when I solved in O(n) and passed the pretests, inwardly I was still thinking there has to be something about the constraints. My overthinking sometimes......
Loose constraints can often appear in the first few problems in a contest, don't panic.
I'll keep it in mind. Thanks.
A problem identical to C appeared in the Korean Informatics Olympiad. It can be solved in O(n) time complexity. https://www.acmicpc.net/problem/32073
Can someone please tell me if my logic for Problem C is incorrect? The first substring will be the complete string, since it is mentioned that the string will always start with 1. The XOR can be maximized if the more significant zeros are flipped. So I find out the position of the most significant 0 (suppose it is at index k), then I XOR all possible substrings of length (s.len() — k) and see where I get the maximum value? I would have understood if I was getting TLE, but I am getting an incorrect answer error. My submission
i did the same thing as you, and got TLE, check my submission if you want. Maybe the repeated string to integer conversions I was doing contributed to TLE.
Only after ~73 top 500 performances do you have the same chance of not winning a t-shirt as you have the chance of winning a t-shirt with one top 500 performance 😓
nice problems!
Codeforces Hot News!
Wow! Coder chenlinxuan0226 competed in Codeforces Global Round 28 and gained -55 rating points taking place 1293
Share it!
Problem C can be solved in O(n) time 298450724
My congratulations to the t-shirt winners: