صباحو (Good Morning), Codeforces!
I'm glad to invite you to Codeforces Round 746 (Div. 2), which will be held on Oct/03/2021 17:35 (Moscow time).
This round is rated for the participants with rating lower than 2100.
You will be given 6 problems and 2 hours to solve them. All problems were prepared by me and Bakry.
One of the problems will be interactive. So, it is recommended to read the guide on interactive problems before the round.
I would like to thank:
antontrygubO_o, for a lot of things (awesome coordination, suggestion for one of the tasks, helping in preparation, rejecting only not interesting tasks, a lot of useful discussions).
KostasKostil for one of the tasks and antontrygubO_o for preparing it.
YahiaSherif, ZeyadKhattab, mahmoudbadawy, Uzumaki_Narutoo, _zaher_ for discussing and testing the problems.
Our army of testers 244mhq, TripleM5da, Naseem17, Mohammad_Yasser, ZerooCool, compiler_101, TheSawan, IsaacMoris, Mohamed.Sobhy, AhmedEzzatG, Ahmed_AIansary, Evro, Sisy, G.A.T.C, mennafadali, Khater, It_Wasnt_Me, DAleksa, Samez, soba, O_E, AhmedZ, AshrafEzz, Urvuk3, Mo2men, Ahmad.houmani.
MikeMirzayanov, for the amazing Codeforces and Polygon platforms.
The statements are short and we have tried to make the pretests strong. I encourage you to read all the problems.
For people who don't like stories, you will find all the stories written in italic you can skip them safely.
This is our first official round on Codeforces. We are sincerely looking forward to your participation. We hope everyone will enjoy it.
Good luck and see you in the standings!
UPD:
Score Distribution: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$2000$$$ — $$$2500$$$ — $$$(1750-1750)$$$
UPD1: Editorial is out!
UPD2: Winners
Div. 1 + Div. 2
Div. 2
I think this round will be great one.
No jinxing plsssss.
I thought nobody likes stories
stories are annoying during contest time but enjoyable during practice
that's an amusing paradox.
Ya during practice it is very enjoyable but during contest specially for rated people most of us have not read it
Looking forward to this one!
Bakry and Hemose OP
As a contestant, I hope there are no XOR problems as it's always the case with Egyptian rounds.
Your prediction is true! They must upvote u!
Sorry for that.
lmao u r actually true
Regret for not trusting you, with tears after the contest
I claim that this round will be one of the best Div 2 rounds ever.
you can skip them safely.
Don't tell me what to do, I like stories.
For people who don't like stories, you will find all the stories written in italic you can skip them safely.
This line was not for you if you like stories.
Orz Bakry for winning the EOI
As a tester, it is a great contest with great ideas. I recommend participating. I am sure you will enjoy the 2-hours of the contest. Great Hemose well done!! :)
As a tester, I pinky promise you will like the contest.
Pinky promise >>>>
The struggle with D and E was real fun! Looking forward to the editorial. Kudos to the entire team for a great contest. :)
i think this contest will be amazing ,Good luck, God willing i hope to be pupil or expert lol
Waiting for an amazing round and wishing everyone good rating.
These Arabic comments are annoying!!! please use only English in an International site.
Imagine thinking you are entitled to regulate how other people talk.
That's not regulating, He's asking to use a common language
hopefully this blog wont get any downvotes.
I hope the difficulty level will be balanced unlike the last contest XD
I agree
I hope so
F
One of the problems will be interactive. So, it is recommended to read the guide on interactive problems before the round. Hope that it will be one of the last problems that I don't even touch!
Can candidate masters participate this contest?
yes! below 2100 rating can participate includes candidate master
thx
Looking forward to this one!
hope it's not as hard as the last one xD
"The statements are short".. I already like this contest :)
strong pretests are even better
But then there's less chance of hacking someone's code.
As I know you shouldn't post here anymore :)
wtf he got 904 upvotes for that!! lolll
Thank you for the opportunity to train on this site. This is the most convenient and practical site for sports programming!
This round will be a book for participants, where you can read stories, and also solve problems. Hope it will be interesting! Good luck all!
Scoring distributions?
Hello everyone!) I have a question. How many problems should be solved on average from the competitions of the second division in order to have a rating of 1400 — 1600. Thanks for the answer)
Till C in an average div 2 round.
Hope I go purple this round!
Hope I return purple this round!
Nice ♥
500 — 1000 — 1500 — 2000 — 2500 — (1750−1750) WHAT DOES THIS MEAN last problems will be of lesser difficulty than d and e?? someone pls clear
Last problem has 2 subtasks, if you solve just the easy one, you'll get max 1750 pts, if you solve both, easy and hard subtask, you get max 1750 + 1750 = 3500 pts. Also, avoid caps please :)
Egypt Round Today?
Long Q?
Way too long..
When you wait for 5 minutes just to see the verdict as Wrong Answer on pretest 2 :_(
Can the time limit exceeding be for the long queue time?
No. TLE has nothing to do with long queue.
I am getting a bad feeling about getting FST on B.
update: the solution is right
problem B is hard for being div.2 B imo.
gg wp
It has a 1000 points, usually it's only 750 points. I think its justified.
then for many users this contest will only depend on how fast you solve a and a lot of submissions for problem a are like:
wa pretest 2.
tle pretest 5.
pretest passed.
Good problems. But was this necessary ??
One day, Ahmed_Hossam went to Hemose and said "Let's solve a gym contest!". Hemose didn't want to do that, as he was playing Valorant, so he came up with a problem and told it to Ahmed to distract him. Sadly, Ahmed can't solve it... Could you help him?
Hemose was shopping with his friends Samez, AhmedZ, AshrafEzz, TheSawan and O_E in Germany. As you know, Hemose and his friends are problem solvers, so they are very clever. Therefore, they will go to all discount markets in Germany.
...
Sorry for pointing this.
Read the announcement carefully, (For people who don't like stories, you will find all the stories written in italic you can skip them safely.)
Ah my bad, sorry for that. Anyway thank you, I really enjoyed the contest.
You are Welcome!
Another contest with only 10% solving C...
Lovely problems.
I was manage to solve only one problem that is A, truly speaking I loved that problem. Because I thought that could be solve just traversing the non-increasing array, but that gave me TLE. After that it forces me to think other way to solve it. For me problem A was real meaning of "codefocres", loved it.
How to solve B?
+1 from future specialist
There might be a part of the array in the middle where we cannot move any element. If that part is not correctly sortet in input then ans=NO.
The main idea to solve this problem is that you will not able to swap the elements present in the array in the range from (n — x) to x, so, the elements that are present in this range must be sorted and must have values equal to the sorted array..
Can problem D be solved using Centroid Decomposition + knapsack?
I think binary search on the edges was required. Since the gcd of two numbers is always smaller than or equal to the smaller of the two number ( $$$gcd(a,b) <= min(a,b) $$$) . This means that the maximum distance will be between two nodes that are intially having a edges.
Now we can find the maximum distance between any two edges in 1 query. After that we can binary search on the edges and find the edge with the distance equal to maximum distance.
I was not able to get AC and might be entirely wrong.
Sorry, but what binary search on the edges means?
Sorry about it entirely wrong T_T.
No problem :D
Yes, basically the idea is the following:
1. Set the goal = query of all nodes, we will eventually end up with this score between exactly two nodes.
2. Perform the following operations on the tree, till the tree has exactly two nodes (the answer):
2.1. Find the centroid of the tree and let's root the tree at the centroid.
2.2. For each child of the centroid add all the nodes of the subtree rooted at the child into a set.
3.3. From 2.2, we have k sets of nodes where k is the number of children of the centroid.
3.4. Merge all these k sets into exactly 2 sets, here we need to make these two sets have size as close as possible to each other. This can be done accurately enough by using knapsack as you described, but I used a greedy version for my implementation and it got accepted. Although, I am not entirely sure it is correct, so please someone prove its correctness or hack it :p.
3.5. After merging we ask a query on the first of these two sets. If the query == goal then we know that we have a valid answer in the set we asked, so we remove all the nodes & edges of the tree from the other set. Otherwise, if query != goal we know that our answer is contained in the second set, so we remove the nodes & edges of the first one.
3.6. If we end up with just two nodes, this is our answer, otherwise, we repeat the 2nd step.
Note that the 2nd step will be executed at most log(n) times because in each iteration we remove almost half of the tree's nodes. It can be proven that the size difference between these two sets will be small enough to keep it in log time, (if we merge all the k sets optimally) because of the properties of the centroid.
Here is my post-contest submission (130742844) of this implementation.
(Again, I did not use DP knapsack to merge the K sets into 2 as optimally as possible, so it might be hackable)
Nice sense of humour in that iconic
at most k-1 edges
line.They probably had something like
split into at most k trees
and then changed it last-minute for that XDI actually got C wrong answer at 10 because I handled the case when K = 1 instead of 2 because of that line. after the contest I edited it and got the late ACC :(
I thought that was to be able to easily write the constraints on n and k. It was something like 1 <= k <= n <=
C, how to find the XORsums for all edges without TLE?
Then it should be not so hard. It cannot be more than 3 components, since if it would, we could put together 3 of them into 1.
So we want to search for XORsums in our list where both ends are same, or one end equals 0 and there exist two other ends with the same XORsum.
Edit: And yes, problems where way to hard. A trivial, B stupid. Actually only C somewhat interesting.
This is what I did. Let XOR of all elements be Xo.
1) If Xo == 0, then there is always an answer ( As all elems >= 1 => it is possible when two partitions have equal XORs ) 2) If Xo != 0, then we need to divide the tree into 3 components. So, I ran a DFS across the graph which basically returns XOR of the subtree. a) If Xor of a subtree == Xo => this is a candidate for division. Return 0 ( So that we don't double count it, especially for cases where some contiguous group of ancestors have a xor 0. This leads to double counting of this subtree b) If Xor of a subtree != Xo, just return Xo
Finally, if we have > 1 nodes with Xo XOR and k > 2 => we can always have an answer.
How does this dfs returning the xor of that subtree run without TLE?
Consider the trivial implementation: We iterate all children except the parent, and return the XORsum. But that goes TLE for a star like tree (one center and a lot of leafs arround it).
I still don't understand why the DFS will be any different from say DFS to return count of nodes.
While counting the nodes we can simply return the number of adj nodes, without iterating them.
Finding the xorsum we need to iterate them.
XOR of SUBTREE ( ROOT ) = Value ( ROOT ) ^ XOR of SUBTREE ( Children )
This is the recursion. We will visit every node once and if our dfs call at a subtree returns the corresponding XOR => we can easily derive the parent's XOR
Thus O ( V + E )
Went over your code ( TLE one ). Your DFS function itself seems correct but, the fact you are iterating for a lot of nodes is not. If you think a bit, if there exists an answer, it can be discovered with a single DFS call
Yes, I think I understood now.
It is enough to dfs starting at one edge, since foreach iterating edge we have the two values, and can simply store them also in the oposite direction.
I tried instead to dfs from kind of "all directions" :/
Rerooting approach (couldn't implement it in time because I was stuck at problem B):
Note: every edge is double-counted.
In the first DFS we calculate xor of all vertices in the subtree of u. In the second DFS we do it for every possible root. In the u's component XOR is dp[u] ^ dp[v] and in v's component XOR is dp[v].
what the heck is in test case 17 (and how to solve D)?
+1
I guess you are doing a simple binary search on the edges. Imagine this, you want to ask about Edges $$$(1,2)$$$ and $$$(3,4)$$$. You will get $$$7$$$ as answer!
T_T
Test 17 is really depressing. In your case, it was for problem D and in mine, it was problem C. ;-;
Thanks for interesting F
You are welcome!
Hurrahhhhh,,! after a long time againg specialist :)
are you sure? I mean from 1270 to 1400+ is a big jump considering you have solved upto B. But if it does happen then kudos.
CF-predictor: +144
It isnt 100% correct, expect for approx 25%>= change in the outcome
now it's +118 . bye guys :(
F
lmao someone got -1294 points for -50 hacks
I've no idea why authors of C decided that it's possible to delete at most k-1 edges, while input is k :/
If we delete $$$k-1$$$ edges, there will be $$$k$$$ pieces of the original tree. So if $$$k=2$$$ for example, there will be $$$2$$$ trees left after removing $$$k-1=1$$$ edge.
But in the solution we don't care about number of pieces, we care only about number of edges. Because of this k — 1 it's easy to get wa10.
It's easier to reason about number of pieces. Would you prefer "Two edges cut" or "three trees"?
If you prefer "Two edges", then just do
k--
, there's no one stopping you from that.Meaning that we cut the tree into k components, so the # of cut edges is k — 1.
K components is more natural
I think it is so that there are maximum k disconnected components as the result of the edges deletion, pretty reasonable.
Approach for C? I noticed that if the total xor is $$$0$$$, then there is always a solution. If it's $$$x$$$, and there is a solution, the solution requires at least $$$2$$$ total edge-cuts, and each of those $$$3$$$ pieces of the tree should have xor $$$x$$$.
But how do you implement a solution to find whether it there are $$$3$$$ subtrees with xor $$$x$$$?
Edit: Thank you chlalstjr and Ghassane :)
One dfs should be enough. For each subtree, calculate XOR for it. If a subtree has XOR equal to $$$x$$$ (XOR of all the elements), we set it equal to $$$0$$$ and increase the counter. If the counter reaches $$$2$$$, then we can split the tree in $$$3$$$ components with equal xor.
(deleted) I think I've figured out. Thanks.
i dont think this approch is correct.but this is Accepted.
this is case: ai=value at node[xor value]
here net XOR=5 and your count is = 3 times. but it is not possible to split in 3 parts Ghassane Can you explain this??
UPD: GOT it. i missed the part set it equal to zero.
Your observations are correct. Using x as the value of all XOR, I did a dfs from any point. At root, if A[root] == x, return 0 and increment numComponents, else return A[root]
At non-roots, you take A[node] XOR with dfs of all children (so excluding parent). Again if value == x, return 0 and increment numComponents, else return XOR value.
Basically what this does is everytime you get a subtree where its XOR equals x, you immediately break it away as a single component.
Then check if numComponents <= k or (numComponents — k) % 2 == 0 --> This means if you can achieve k components by combining 3 components into 1.
How to solve C?
If the xor of all $$$a_{i}$$$ is $$$0$$$, you need to make an even number of components i.e just one cut is enough.
If the xor of all $$$a_{i}$$$ is greater than $$$0$$$, let's call it $$$x$$$, you need $$$3$$$ components(two cuts) with subtree xor's equal to $$$x$$$. You can easily calculate that with a dfs and cutting edges off subtrees when you meet one with a xor of $$$x$$$.
Thanks!
let x = xor of all nodes z = equal xor value for each component if x is zero deleting any 1 edge will do the job other wise the number of components must be odd which implies even number of edge cuts and the xor value of each connected components must be x i.e z must be = x. Thus the number of components must be 3 , 5 , 7 ... (bound depending on value of k) but We don't need more than 3 components , suppose we 5 components , we can merge 3 of them into 1 maintaining the xor value since z xor z xor z is = z
Anyone How to solve B i am sure for x=1 ans will yes and for x=n no :(
Find an upper bound for when it's possible (a formula for $$$k$$$ in terms of $$$n$$$).
Test a few small examples, like $$$2\ 4\ 3\ 1\ 5$$$ and $$$k=3$$$, drawing the edges for which two spots you can swap.
Using the edges from Hint 2, try and find which two spots it's possible to swap using other spots as "buffers".
Which elements can you not swap at all?
I spent half hour just to change i+2 to i in my B solution it took me a dreaming journey in the universe to see it
When I suspect that something like this is happening, I delete everything, read the problem statement and start writing the code again.
it wasn't a typo i actually thought it's i+2
I solved B the same way you did, but I think this is a better way :
I knew it's a continuous range but my mind just didn't work to calculate it i guess not my best day
Is this called contest? :| I think you should change your minds
Not sure of the binary search approach for D but here is mine. The first query is the whole graph to search for the final value. The second query is to turn the size of edges set to the power of 2. The 10 next queries is to divide the set into 2 halves. Then just check for one half and move to the valid set.
You can use binary search over a traversal of the graph to do this without too much implementation pain. (You have to mark a node each time you visit it, so there are 2*#edges nodes in the traversal.) https://codeforces.me/contest/1592/submission/130700097
Can you share your code for this
I thought only Ehab is in love with XOR..
It seems common for all Egyptians
Seriously, what was pretest 10 in problem C!?
You probably forgot that you have to use almost $$$k-1$$$ cuts.
Can't we always find the answer with exactly two cuts when the xor is non-zero?
If $$$k = 2$$$ then you have only $$$1$$$ cut so the answer is NO.
I decremented $$$k$$$ already, I don't think that's the issue.
I could not pass the pretest 10 as well ;(
I think many ppl got stuck on the impl, C was actually pretty easy and interesting tbh.
For C, I would like to know if the following observation is correct or not.
If it is possible to generate components with the same XOR sum, it is possible to do so using either one cut or two cuts.
I played around with a few examples and reached this conclusion. But implementing this gave me WA.
If Xor = 0, One cut is enough
If Xor != 0, If there is a solution it always can be done with 2 cuts
Yea that makes sense, thanks.
Now I just need to check where I went wrong in the implementation :/
Proof: Let X represent XOR of all nodes
If X = 0, it can be done in 1 cut, because, say y represents xor of one component and z represent the other component. Then:
y ^ z = 0
therefore, z = 0 ^ y = y, so the two componnents will have equal xor value
If X!=0, it can be done in 2 cuts. Let x, y, z represent xor of each component after two cuts
x^y^z = X
since all components are supposed to be equal, x = y = z, therefore:
x^x^x = X
x^x^x = (x^x)^x = 0^x = x
x = X
So we should make 3 components with xor value = X
I tried to solve it. :)) but at the last minute, I realized that I misread problem A. I think I can solve problem B if I have more time :3
Fun contest ! My delight in solving the problems outweighed the frustration from repeated stupid bugs. Good job round setting team
Thank you!
Check out code of problem A,B,C of RestricePlanox. Looks like this guy gets the solution from somewhere and then add helper++ all over the code so that system can't detect it.
Great round but problem C and D aged me $$$10+$$$ years
Nice Contest , Thanks For The Round . Although my bad form Continues (Solved A and C but failed in B) , I enjoyed the round .
Only able to solve A but all problems are interesting and educational. Great round Hemose and other problem setters too
Thanks!
Now that all my problems passed system tests, I'd like to express my admiration and say Good job guys <3
Thanks!
Hey, can you help me out? Problem C of today. https://pastebin.com/jFS45YQM Why this code gives MLE? I don't see any point of MLE!! Does clearing vector before taking input is the culprit behind the scene?
deleted
I got it and posted about it. I am now flying on the doom of darkness and sorrow grasping me harder man!!! Haven't got MLE before this for that approach.
The system testing is in "Flash" mode
So is F2 flows?
I find it in the last 5 minutes.But I've deleted all my code written before to clean my computer.
Anyway it's a nice contest with hard but interestinf problem.
Really enjoyed the round, especially the C problem !!!
Amazing ABCD, but E was quite easy for its position. Amazing contest.
My code for problem C was wrong and i have the wrong case for it
1
8 3
16 16 8 8 1 3 3 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
and it passed the systests !!!!!
so weak systests its just a simple case !!!!
Well, I guess your test case is wrong, as it does not meet the constraints specified for the weight of the node, which was greater than 1 and thus cannot be 0.
Yeah I found it out its now a correct test
Sir Bakry or Hemose can you look into this?
Hard, but very exciting set!!!
Can someone tell me whats wrong in this Approach for Problem E?
I am looping for each bit i and trying to find the largest subarray all it's elements have 1s at bit 1
If the AND of this subarray > XOR, then the answer will be the size of this subarray, otherwise the answer will be Size of the subarray — 1, maximizing the answer with each i
when you are looping over some bit i, and let's say you have a subarray with bit i, it is not always sufficient to check, this total subarray, or subarray-1 .
Though just a little extension of your approach could have done it. Let's find a new array A from your subarray, such that for each element in subarray, you make an entry in this new array, with bits>=i.
Now in this new Array, find the max length subarray with xor = 0. That's your answer.
130719800
Were the tests of problem C weak? I used random to generate the root of the tree and solved it without checking 1 thing. Currently, I don't know what I'm forgetting. but it somehow got AC. If you know can you leave it here? my submission is 130722566 thank you.
Thank you Bakry and Hemose for this contest. Although I didn't end up solving C in contest time (which means I'll get -ve unfortunately), I thought that B, C, and D were very nice problems! I found the right observations for them, although couldn't implement C in time. I'll definitely be upsolving them :D
One question about C, was the constraint on $$$k$$$ added to troll about the previous contest that also had to do with $$$k-1$$$ edges? Because all it added was a simple if-statement, but it made many people fail pretests as it wasn't in any sample.
I guess the reason why authors gave the constraint k-1 is because when you delete k-1 edges then the tree ends up with k components, which looks easier to deal with. Again, just guessing
I'm not asking why it was $$$k-1$$$ edges cut versus $$$k$$$ components. I'm asking why there was a constraint with $$$k$$$ in the first place.
We are happy that you enjoyed the contest!
The constraints are the same from the beginning we didn't modify anything.
Is there anyone, who also thought problem C is doable and then couldn't able to solve it :(
Round was excellent!
When will the problems can be submitted?
once the system testing is complete, then you will be able to submit it. It's almost completed just a matter of 2,3 minutes.
Can anyone explain the approach for problem B??
You can try similar problems using union-find following links
https://atcoder.jp/contests/arc097/tasks/arc097_b
https://atcoder.jp/contests/arc107/tasks/arc107_c
https://atcoder.jp/contests/abc157/tasks/abc157_d
if k is bigger than half of the size of the array, then there are some elements in the middle of the array that we cannot swap with any other element.
We need to check if these not-swappable elements are in correct position.
hey, i do understand that but can someone prove that all swappable elements can be sorted??
The prove is that each two elements can be swapped by using a third element, and swap three times. So each element that can be swapped with any other element, can be swapped in any position that is reacheable by any swap. Like we can swap with the usual adjacent elements.
130711588 This submission is taking a lot of time. why why!!!!
difficulty gap between B and C was too high
I don't think so, it only required basic xor knowledge and dfs traversal.
You should definitely check out the editorial, it is pretty well explained there.
yeah I read the tut and it was was actually quite nice and intuitive logic :) One of my friends sent me this question which is equivalent to the case where the tree degenerates into a linked list.
very interesting problemset, I missed C by few seconds :/ https://codeforces.me/contest/1592/submission/130724367
pretest 10 on C haunts me , anyways nice contest
same here, I found the testcase but I completed my solution 3 seconds after the contest :/ really just 3 seconds :/
I came up with a very-overkill solution to E quickly but spent a good amount of time implementing/debugging it only to get mle on test 1.wish the ml was more.Its surprising that intended solution was so easy and short.
Yeah, I like E because The solution becomes easy and short after one observation.
hard one but good one
What is happening to this 130711588 submission by rainboy to problem D? It is getting "Denial of judgement". I have never seen one before...
Update: It became "Accepted". I wonder what happened...
We just rejudged the solution, We don't know the reason for this verdict.
we've rejudged his solution and he got AC
I have known Bakry personally for around 2 years and there is one thing I want to say,
Good job Bakry senpai, You always amaze me with your progress, keep up the great work.
Also, no one can forget the great work of the great Hemose in this contest.
Thank you guys.
Thanks! We are happy that you enjoyed the contest!
Thanks for interesting problems, I felt like real div2 C diff problem was missing.
To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
F1,F2 are interesting.
صباحو
Finally became a Div. 1 Newbie.
got -106 but still wht a great round and quality problems