Hello, Codeforces! Or, as we like to say in Servalish (created by Serval): High-low, Cold-for-seize!
We are glad to invite you to participate in Codeforces Round 947 (Div. 1 + Div. 2), which will start on 25.05.2024 17:35 (Московское время). The round is a combined round and will be rated for everyone.
The problems are prepared by Atomic-Jellyfish, Nerovix, SanweiTreap, Serval, Toxel, jhdonghj112 and me. You will be given 9 problems to solve in 3 hours. Scoring distribution will be announced later.
We would like to thank everyone that makes this round possible:
- errorgorn for his 🐸, 😱, 👍 and 🥶 coordination.
- Alexdat2000 for Russian translation.
- BFLSTiger and wzy2001wzy for providing some
rejectedproblem proposals and discussing problems with us. - 2sozx, JJLeo, YUKI_LELOUCH, Hanghang007, zlc1114, fried-chicken, zhicheng, fsfdgdg, H_W_Y, 200815147, CrTsIr, OMG_link, RDDCCD, SSerxhs, Tony2_CF, zhaohaikun, Hank2019, WZKQWQ, cxaphoenix, LGyxj, Oshwiciqwqq, fallleaves01, forget-star, monstersqaq, Narukara, Ricky2021, MagicalFlower, Saule_, kgqy, YSY_, dan_dolmatov, lowbob, sleepwa1ker, Nanako, Qingyu, Meatherm, PersistentLife2024, Vamperox, FransValli, skywalkert, shstyle, Lavine, kaichou243, gamegame, Cai_Guang, xhytom, qiuzx, Legitimity, Kevin114514, Adam_GS, htetgm, zengminghao, Melania, JCY_, yaoxi, schrodingerstom, jqdai0815, SSH_automaton, platelet and sjc061031 for testing the round and providing valuable feedbacks.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.
- You for participating in the round.
We recommend you to read the statements of all problems. Good luck & Have fun! (=・ω・=)
UPD: Scoring distribution: 250-500-1000-1500-2000-2500-3000-4500-6000
UPD2: Editorial is available now.
UPD3: Thank you for your participation in this round! Congratulations to the winners:
And the first solves on each problem:
UPD4: Chinese editorial is available now.
Photo of reviewer and some authors:
About the quiz: First of all, not genshin impact.
Sadly this is not a game, but you reminded me of Jellyfish Can't Swim in the Night.
same sir, this anime is orz
so it's star rail
Ok I know its Arknights.
Plea vet, cold-for-seize! Water she wall Serval days. Wall shall Servalish. Good Luck & Have Fun!
Translation: Hi (maybe Russian), Codeforces! I'm Serval (Japanese) and I speak Servalish (Chinese). Good Luck & Have Fun! (English, obviously)
Wasn't it supposed to be CodeTon Round 9?
They probably don't have money. From Last round didn't come money
As a tester, jhdonghj112 is so handsome.
Are you his alt account ? 😂
As an author, Saule_ is handsome too.
Omg errorgorn Coordination !
I hope he played Dota 2
jhdonghj need better camera!
I think its hp's fault, they should equip a better camera on laptop lol
Not only hp, general problem for every single laptop on earth
As a tester,I sincerely hope that all the participants would enjoy the magnificent problems while competing in this round~
kinda sus!
60 TESTERS, is that a codeforces record?
It was supposed to be codeton I think that’s why
60
24
17
10
5
0
1
2
1
geometry dash?
Fire in the hole
music available?
As a tester, wish you enjoy the contest.
Acknowledge the hard work of the organizers and contributors.
It's gonna be a math round isn't it?
I'm gonna be really disappointed if Jellyfish didn't play getting over it with bennett foddy this time around.
A GIANT TESTER ARMY...
So many testers 😮
How come it is div1 + div2 when it seems like the sponsor (codeton) has backed out?
Can't trust the unrated testing fsfdgdg smashing 3000+ questions while being unrated ;_; .
Bruh I'm his classmate
Actually he's in NOI2024 Sichuan Provincial Team. He just has no time to take part in CF rounds cuz he usually lives in school
Best of luck all the participants.
Did anyone recieve their prize from the last CodeTON Round? (Round 8)
Tester count in this contest are more than entire Vatican City population.
CF is lagging a lot , is anyone facing the same issue ?
hope i can solve A or B :D
same bro
me too
As a tester I highly recommend you writing this round!
my div1+2 history isn't good, hope to change it today
This round is clashing with leetcode biweekly Dominater069
As a fan of Dominater069 I would like to say this.
This round is clashing with Al Ahly vs ES Tunis match — CAF Champions League Final
Luck good¡¡¡
Excited for the 6000 rating problem
Gellyfish looks just like the man in the famous painting The Son of Man by Magritt.
Mochaforces
Is everyone waiting to be evaluated? Or CF now only assessing the questions in this contest right now.
"Jellyfish usually got ideas from games, so what game did Jellyfish play this time?"
Slay the Spire
Solution of C was present here https://www.geeksforgeeks.org/find-largest-median-of-a-sub-array-with-length-at-least-k/.
Just put k = 2
Ohh boy and here I was thinking why many of the solutions for task C looked very familiar with each other. Even some experts have cheated from the GFG code. Hope that they will be severely punished when the system testings are being done to find copied codes. I would like to draw the attention of the moderators to make sure that the solution codes for problem C are checked against this particular code to prevent any mass cheating
Codeforces policy allows you to use code written before the contest.
Thanks Xellos for the hint for C: Chamo and Mocha's Array
I have added hints and thought process for this problem on CF Step
Here's my code for reference.
lesson learned from today's contest: never wasting time on ChatGPT.
so you tried to cheat?
Stuck on F for 2h, please tell me there's something elegant and it's not some bitset crap
Suppose $$$v[0] = \lbrace 0 \rbrace$$$, so that it is of length $$$2^n$$$.
Solve recursively, on a given $$$v$$$ of length $$$2^m$$$:
If $$$m = 0$$$, then it is solveable only if $$$0 \in v[0]$$$.
If $$$m - 1 \in S$$$, then you can reduce to a new vector $$$u$$$ such that $$$u[i] = v[i] \cap (v[i + 2^{m-1}] - 1)$$$.
Else, reduce to $$$u[i] = v[i] \cap v[i + 2^{m-1}]$$$.
Then solve recursively for both $$$u$$$'s (both of length $$$2^{m-1}$$$), while carrying your decision. While this may seem naive, the time complexity is $$$O(n2^n)$$$.
Okay that is fully my bad — I had this but did not calculate the complexity correctly. Thanks.
u can try merging the constraints as u fix one bit at a time, eg if you fix the 0th bit to be on, then u can combine all x with x+1 (since both of them share all other bits so the other bits must satisfy both their constraints), thus at each level, the array shrinks by 2, while the number of calls double by 2, so in the end the complexity is n2^n
How to solve F?
How to solve E ?? :(
How to solve E without TLE you mean?
Solving usually does mean without TLE. I don't think a solution which gives TLE is considered "solving".
My logic: You only need two things no of connected components if we only consider the black nodes in the tree .We only need to check further if the components is 1.
Now to know if the conn comp is a chain you only need to see if the distance between the 2 farthest nodes in the conn comp is equal to the number of black nodes in the tree, in a chain these two farthest nodes are leafs i.e. nodes connected to only 1 black node.
To maintain both conn comp and leafs, you only need the number of black neighbours of a node. Now i did this using segment tree on bfs ordering, since changing the colour of a node only affects its children and parent. My sol is $O(q log^2(n)) but there might be a better way.
root the tree end points of the chain are the black nodes which have no black child so chain is possible if the count of such nodes are <= 2 if count is 1 chain is possible if count is 2 let l be the lca(u, v) chain is possible if total no. of black nodes is equal to dist[u] - dist[l] + dist[v] - dist[l] + 1
But how are you finding the leafs? My approach was qlog^2 due to the leafs
Ohh right, black child means i only need to update parent thanks.
Calm down bro, they are discussing trees only.
Bruhhhh xD
Can't figure out how to optimize by O(qlog^2) sol to pass in E, Someone help Submission, The main time is due to the call of query_r2 func
Passed it after i changed my compiler ffs
is problem D DP on Tree?
A little bit of DP, but the main idea is adhoc anyway
No, you use DFS to calculate the distance from node A to node B — they should walk towards each other, and will first meet each other at some node C. After that they "travel together", and the number of steps is equal to the number of edges times two, minus the (distance from meeting point C to some furthest node D). Because it's best to "end" the trip in that node from which you don't have to return — so you make this ending node D the farthest one.
When both of them travel together does the node color directly go from white to blue?
Yes (is mentioned in the question)
But it is only mentioned for initial nodes.
the order they move is in the description; first P_A moves (and marks the vertex red), then P_B moves (and marks the vertex blue)
What if it's a-> f -> g -> b they will meet on g or f I know it's impossible too meet in one of them but what is the solution in that case?
Let a stop at f and b stop at g, then b follows a.
That's what I did but it didn't work maybe there is something wrong with my implementation I will wait and see the tutorial.
if dist is odd ..
first time solved E i am literally shivering :)
problem-B is toxic, thought too much for that simple thing.
How to solve it ?
If a number $$$small$$$ divides $$$b$$$, then it is true that $$$b$$$ should be bigger than or equal to $$$small$$$.
Think about the minimum element of the array. If you don't select it as the candidate, no element would be able to divide it. Hence, one candidate is locked. I'll leave out the analysis for the second candidate as an exercise.
sort list. All items must be divisible by first item(F1) or the first item not not divisible by F1.
You need to make a simple observation:
In order for some $$$a_k$$$ to be divisible by some $$$a_i$$$ , $$$a_k \geq a_i$$$, so we need to choose the smallest element to be our $$$a_i$$$.
We then mark every multiple of $$$a_i$$$ as visited, this can be done in plenty of ways.
You will have a new array of visited and unvisited elements, you choose the minimum of the unvisited elements, let's call it $$$m$$$. Loop through the array, skip the visited elements, if one unvisited element is not multiple of $$$m$$$, the answer is No.
You need to find 2 minimal elements in the array such that:
First element is always the minimum of the array(because if it's not minimum and other number is chosen, the minimum won't be divisible by a bigger number)
Second element is always the minimum element in the array that is not divisible by the first minimum.
For example array: 4 2 15 5 6
First you find minimum — 2 in this case, after that second minimum is 4, but it should not be chosen, because then we can not check on 15 correctly, 4 is divided by first min without remainder. So the second min is chosen to be 5 and then we are going to check if all the array elements divide by those two minimums we chose.
TC: O(N)
what was it?? I am still unable to find error in my code.262564497
You just assumed that after sorting the array the first and the second element are the required i and j. Assume the case as Array=[2,4,5,6,10,15] where your code.But here the answer is yes with i=1 and j=3.
Your code fails on the testcase,
n = 3,
2 4 7
Correct answer: Yes
Your answer: No
In E I used CD with HLD to find out if all black vertices are connected. But I have no idea how to understand if all of them lie on a path
Same, which got me TLE on pretest 13
me too.... :)
after rooting the tree end points of the chain are the black nodes which dont have any black childs so you have keep track of all black nodes which have no black child
Connectivity can actually be checked in a much simpler way: The black nodes are connected iff there is exactly one black node that doesn't have a black parent.
Thanks. My mistake was thinking about all degrees instead of parents only
To solve $$$E$$$ I am thinking if any way I can maintain number of black nodes having adjacent black nodes of size 2 and number of black nodes having adjacent black nodes of size 1 , am I thinking in the right direction?
you only have to care about black nodes which have no black child
G made me lose the little mental sanity I had.
One of my worst contest
For E, I was thinking of maintaining the degrees of all black vertices . If it is of the form {1, 1, 2, 2.....2}, then it forms a path, considering the corner case for #black vertices=0, 1, 2 . Am I thinking in right direction?
Would be difficult to maintain. A single query can change up to N values (all neighbors).
root the tree and think about the end points of the chain and how the chain will look like.
I had the same idea during contest and managed to get $$$O(n\sqrt{n}log(n))$$$, complexity but it was to slow. You can maintain big/small vertices and recalculate "black-degree" for every vertex every $$$\sqrt{q}$$$ operations
How solve G? I know there is a bitset solution but I don't know how to optimise it
I ended up with WA7 so I may be wrong, but I believe most of it is correct (and I probably have a bug):
If none of the strings contain asterisks, then it is easy.
If both contain asterisks, then check both prefixes and suffixes for equality, until you reach asterisks. If prefixes and suffixes were equal, then it should be "Yes".
Assume now that $$$s$$$ has no asterisks, and $$$t$$$ has at least one. Remove equal prefixes and suffixes, so that $$$t$$$ begins and ends with asterisk. If all of $$$t$$$ is asterisks, answer is "Yes".
Now, you need to take every substring of $$$t$$$ between a pair of asterisks, and match it to the first substring of $$$s$$$ that matches it, greedily.
It's a classical algorithm to determine whether a string can be anothers' substring, when both may contain '-' symbols, using fft in $$$O(n \log n)$$$ where $$$n$$$ is the larger of those lengths.
Now, to find the first position in which a substring of $$$t$$$, of length $$$m$$$, matches in $$$s$$$, starting from a given index $$$i$$$, you can do an exponential search:
Check if the substring appears in the substring of $$$s$$$, starting at $$$i$$$ of length $$$m$$$. If it isn't found, increase to length $$$2m$$$, and so on until it is found.
The total complexity should be $$$O(n \log^2 n)$$$.
It's $$$O(n \log(n))$$$ because the moment you find something in string of length $$$2m$$$ you at least jumped ahead $$$m$$$ characters. And you did at most twice as big wildcard matching as the amount of characters you jumped ahead. So it's $$$O(n \log(n))$$$ amortized.
Oh right. So it's not too bad.
378QAQ is this the name of elon musk kid?
IMO, F << E
I have the opposite opinion. In fact I found that D, F >> E.
In E I was writing something like dynamic connectivity(dsu) offline. But in F very simple divide and conquer, standard idea for tasks with bits.
Thanks for the contest! I'm looking forward for Editorial. Problems were quite good!
For the first time I hacked someones soln
which one ? and case ?
Solved problem E, but the contest ended just as I was about to submit it. I was so close to a huge positive delta! :(
Can anyone please check if my solution for problem E is correct? I can't wait the system to finish and submit it.
How to solve D?
Observation 1: The blue color chess piece needs to visit all the nodes once, after it reaches a node colored red. It needs exactly this, no more or less.
Observation 2: The red and blue color piece meet most quickly if they move towards each other.
Solution: Find the midpoint where they meet using DFS/BFS. From this point as the starting point, find the minimum cost to visit all nodes at least once, again using DFS/BFS.
For calculating the minimum cost to visit all nodes at least once, you can show that this is equal to
2*(number of edges) - (distance to farthest vertex from starting point)
. (Why?)I was doing exactly this :( I found the mid point and tried doing DFS, two things I was stuck at when they are are at odd distance and in dfs i had overcounting when i had to stop just when dfs ended.
Or find max path to any node from meeting point. In this case it will be one of the 2 endpoints of the diameter.
C is quite similar to 1349B - Орак и медианы
Last 2-3 problems might be kept for another round.
Nice contest
Is this approach intended for E:
-> Maintain the smallest depth (i.e highest) black node.
-> For every node, maintain a set of it's children which are black.
-> Now for the highest black node, if the count of it's black children is greater than 2, then the answer is NO.
-> Then for it's (<=2) children, we can find the deepest black nodes in their respective subtrees using subtree max queries, say U and V.
-> Now we just have to check if all nodes on the path b/w U and V are black, and dist(U,V) + 1 = total no. of black nodes.
-> Path sum queries with updates is a standard cses task
If this is indeed the intended approach, it's a garbage task
Had no time to submit D.
Logic I used was: if the distance from nodes is 1 they won't meet at the same point so return (n-1)*2
else I considered that optimal was for Pa and Pb first meet, then with DFS find the longest path to reach the ending point of the graph from meeting point (Because thought it was optimal not to "go up" from the ending point of the graph) int maxPath = CalculateMaxPath()
Considered that other edges are visited twice (going up also counts as a step) and calculated
(n-1)*2 — maxPath + minimumstepsNeededToMeet
What am I missing in logic?
Here's what I did (passed all pretests):
Calculate the midpoint node between $$$a$$$ and $$$b$$$. Let this node be $$$m$$$. (In case the distance between $$$a$$$ and $$$b$$$ is odd, take the point further away from $$$b$$$).
If the distance between $$$a$$$ and $$$b$$$ is $$$d$$$, moving $$$B$$$ to $$$m$$$ takes $$$\lceil \frac{d}{2} \rceil$$$ steps.
Answer will be the above steps + minimum number of steps to reach every node from $$$m$$$.
This worked but I'm not able to prove why it did. Just went with intuition.
had exact same idea but couldn't solve in time
maybe "minimum number of steps to reach every node from m" is what really matter
This seems correct: (n-1)*2 — maxPath + minimumstepsNeededToMeet
Why do you have an extra case? In case distance between nodes is 1, you still need to use the same formula. (minimumstepsNeededToMeet = 1 in this case, and you will have to still subtract maxPath)
Yes, kinda similar what I have I guess..
Can anyone prove why checking subarrays of size 2 and 3 are enough for C?
I guess because increasing the subarray length won't increase the median, we are not limited in minimum steps count so if we find maximum medians of subarray of length 3 we can eventually make the whole array consist of that median values only. suppose [3, 2, 2] subarray from some longer array. no matter if the first element is greater or less then other two equal elements, the median will be still "passed" to that third value too, that proves the fact that eventually the whole array can be filled with median values that we found in subarray length of 3.
consider some segment containing a[i]. for a[i] to be median, there should be at least one element in this segment >= a[i]. lets prove that one is enough. consider, there are at least two of them. if they are on the same side from a[i], than if distance between them >= 1, the second one doesn't change anything. otherwise, use those two consequent elements as a new segment, with a bigger median. if those two elements are on different sides, just use on of the sides, it also won't change anything. So, you just have to check that there is an element >= a[i] in 2-proximity
Anyone with D's Approach???
Go to middle point if odd then get at one edges distance.Then find the deepest node so that you do not have to return from the deepest nodes.Thn count -maximum+(n-1)*2.
Understood.
Video Editorial for (A, B, C) YOUTUBE VIDEO LINK --Click Here
Can anyone explain me D, when point A and point B are not overlapping and say d distance apart and d is odd.
Because wen d is odd then they will be separated by one edge .Think like this that red goes over all edges and at any times blue is one step behind as red finsihes blue will be one step behind.So one step more to complete.That is steps to be one edges away+ one step to cover the delay for the red
Some fun facts about this round:
The original constraint of problem G was $$$5\times 10^5$$$ and 3s. However, I managed to squeeze a bitset solution inside the time limit during testing. That's why the constraint seems so insane in the current version.
If you ever mistyped and corrected your mistake after testing the sample in problem D, it's also because of me. The original sample was (probably not intentionally) so weak that even if you didn't read from input correctly, you could still pass it. I got stuck here and wasted too much time on a stupid mistake during testing :(
solution of Problem $$$D$$$ is the greatest love story if distance between $$$a$$$ and $$$b$$$ is even and greatest simping story if distance between them is odd
Wow interesting
Editorial for E is mind-blowing and elegant. Maybe we over-think it because it's an E not a B/C lol.
In fact, 2745518585 passed E 20 seconds before maspy, so the first solve on E is 2745518585.
262542481
I don't know why people are downvoting this comment but this comment is actually true , the reason why maspy appears before the other guy in terms of judging time because when sorting based on judging time second parameter is ignored and sorted based on minute first then based on handle name , as both of them have same value in minute parameter then they were sorted based on handle names and it looks like any handle name starting with digit comes later after handle names starting with letters
[submission:262597281]As, you have stated that a submission coincides with some others, I don't know how significantly, it matched, because I used ChatGPT for this question, I admit this much, so this maybe the reason that it may have similarity, otherwise, I haven't copied anyone's else code
You are not allowed to use ChatGPT here either.
are the ratings rolled back , didnt get any notification but my 2 contest have not been counted what's the issue
Is it possible to solve Problem C using binary search? Because it appears like a max-min problem
How div1+div2 is different from div 1 and div 2 contests?