### Hemose's blog

By Hemose, history, 14 months ago,

صباحو (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:

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

• +806

| Write comment?
 » 14 months ago, # |   +33 I think this round will be great one.
•  » » 14 months ago, # ^ |   +32 No jinxing plsssss.
 » 14 months ago, # |   +65 lighthearted meme
•  » » 14 months ago, # ^ |   0 I thought nobody likes stories
•  » » 14 months ago, # ^ |   +84 stories are annoying during contest time but enjoyable during practice
•  » » » 14 months ago, # ^ |   +3 that's an amusing paradox.
•  » » » 14 months ago, # ^ |   +5 Ya during practice it is very enjoyable but during contest specially for rated people most of us have not read it
•  » » » » 14 months ago, # ^ |   0 Did you just paraphrase my comment?
 » 14 months ago, # |   +12 Looking forward to this one!
 » 14 months ago, # |   +126
 » 14 months ago, # |   +26 Bakry and Hemose OP
 » 14 months ago, # |   0 As a contestant, I hope there are no XOR problems as it's always the case with Egyptian rounds.
•  » » 14 months ago, # ^ |   +1 Your prediction is true! They must upvote u!
•  » » 14 months ago, # ^ |   +6 Sorry for that.
•  » » 14 months ago, # ^ |   +6 lmao u r actually true
•  » » 14 months ago, # ^ |   +6 Regret for not trusting you, with tears after the contest
 » 14 months ago, # |   +29 I claim that this round will be one of the best Div 2 rounds ever.
 » 14 months ago, # |   +9 you can skip them safely.Don't tell me what to do, I like stories.
•  » » 14 months ago, # ^ |   +5 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.
 » 14 months ago, # |   +153 Orz Bakry for winning the EOI
 » 14 months ago, # |   +38 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!! :)
 » 14 months ago, # |   +64 As a tester, I pinky promise you will like the contest.
•  » » 14 months ago, # ^ |   +3 Pinky promise >>>>
•  » » 14 months ago, # ^ |   0 The struggle with D and E was real fun! Looking forward to the editorial. Kudos to the entire team for a great contest. :)
 » 14 months ago, # |   +8 i think this contest will be amazing ,Good luck, God willing i hope to be pupil or expert lol
 » 14 months ago, # |   +6 Waiting for an amazing round and wishing everyone good rating.
 » 14 months ago, # |   +48 These Arabic comments are annoying!!! please use only English in an International site.
•  » » 14 months ago, # ^ |   +10 Imagine thinking you are entitled to regulate how other people talk.
•  » » » 14 months ago, # ^ |   +22 That's not regulating, He's asking to use a common language
 » 14 months ago, # |   +4 hopefully this blog wont get any downvotes.
 » 14 months ago, # |   +19 I hope the difficulty level will be balanced unlike the last contest XD
•  » » 14 months ago, # ^ |   +1 I agree
•  » » 14 months ago, # ^ | ← Rev. 2 →   +4 I hope so
•  » » 14 months ago, # ^ |   +5 F
 » 14 months ago, # |   +1 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!
 » 14 months ago, # |   +4 Can candidate masters participate this contest?
•  » » 14 months ago, # ^ |   0 yes! below 2100 rating can participate includes candidate master
•  » » » 14 months ago, # ^ |   +3 thx
 » 14 months ago, # |   +3 Looking forward to this one!
 » 14 months ago, # |   +7 hope it's not as hard as the last one xD
 » 14 months ago, # |   +2 "The statements are short".. I already like this contest :)
•  » » 14 months ago, # ^ |   0 strong pretests are even better
•  » » » 14 months ago, # ^ |   0 But then there's less chance of hacking someone's code.
•  » » » » 14 months ago, # ^ |   0 As I know you shouldn't post here anymore :)
•  » » » » 14 months ago, # ^ |   +22
•  » » » » » 14 months ago, # ^ |   +11 wtf he got 904 upvotes for that!! lolll
 » 14 months ago, # |   +5 Thank you for the opportunity to train on this site. This is the most convenient and practical site for sports programming!
 » 14 months ago, # |   0 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!
 » 14 months ago, # |   +8 Scoring distributions?
 » 14 months ago, # |   0 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)
•  » » 14 months ago, # ^ |   +1 Till C in an average div 2 round.
 » 14 months ago, # |   +19 Hope I go purple this round!
•  » » 14 months ago, # ^ |   0 Hope I return purple this round!
 » 14 months ago, # |   +7 Nice ♥
 » 14 months ago, # |   0 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
•  » » 14 months ago, # ^ |   +9 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 :)
 » 14 months ago, # |   +4 Egypt Round Today?
 » 14 months ago, # |   -7 Long Q?
•  » » 14 months ago, # ^ |   -12 Way too long..
•  » » » 14 months ago, # ^ |   +1 When you wait for 5 minutes just to see the verdict as Wrong Answer on pretest 2 :_(
 » 14 months ago, # |   -12 Can the time limit exceeding be for the long queue time?
•  » » 14 months ago, # ^ |   -8 No. TLE has nothing to do with long queue.
 » 14 months ago, # | ← Rev. 2 →   +2 I am getting a bad feeling about getting FST on B.update: the solution is right
 » 14 months ago, # |   +10 problem B is hard for being div.2 B imo.
•  » » 14 months ago, # ^ |   0 gg wp
•  » » 14 months ago, # ^ |   +5 It has a 1000 points, usually it's only 750 points. I think its justified.
•  » » » 14 months ago, # ^ |   +2 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: Spoilerwa pretest 2.tle pretest 5.pretest passed.
 » 14 months ago, # |   -61 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.
•  » » 14 months ago, # ^ |   +74 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.)
•  » » » 14 months ago, # ^ |   +33 Ah my bad, sorry for that. Anyway thank you, I really enjoyed the contest.
•  » » » » 14 months ago, # ^ |   +2 You are Welcome!
 » 14 months ago, # |   +4 Another contest with only 10% solving C...
 » 14 months ago, # |   +14 Lovely problems.
 » 14 months ago, # |   +6 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.
 » 14 months ago, # |   +1 How to solve B?
•  » » 14 months ago, # ^ |   +7 +1 from future specialist
•  » » 14 months ago, # ^ |   +2 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.
 » 14 months ago, # |   +8 Can problem D be solved using Centroid Decomposition + knapsack?
•  » » 14 months ago, # ^ |   +9 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.
•  » » » 14 months ago, # ^ |   0 Sorry, but what binary search on the edges means?
•  » » » » 14 months ago, # ^ |   +3 Sorry about it entirely wrong T_T.
•  » » » » » 14 months ago, # ^ |   0 No problem :D
•  » » 14 months ago, # ^ | ← Rev. 3 →   +3 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)
 » 14 months ago, # |   +102 Nice sense of humour in that iconic at most k-1 edges line.
•  » » 14 months ago, # ^ |   +18 They probably had something like split into at most k trees and then changed it last-minute for that XD
•  » » 14 months ago, # ^ |   0 I 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 :(
•  » » 14 months ago, # ^ |   0 I thought that was to be able to easily write the constraints on n and k. It was something like 1 <= k <= n <=
 » 14 months ago, # | ← Rev. 2 →   0 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 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 XoFinally, if we have > 1 nodes with Xo XOR and k > 2 => we can always have an answer.
•  » » » 14 months ago, # ^ |   0 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).
•  » » » » 14 months ago, # ^ |   +3 I still don't understand why the DFS will be any different from say DFS to return count of nodes. Codeint currxo = vec[idx]; parent[idx] = par; for( auto v: adj[idx] ) { if( v != par ) currxo ^= dfs( pref, adj, vec, v, idx, parent ); } if( currxo == xo ) { pref.push_back( idx ); return 0; } return currxo;
•  » » » » » 14 months ago, # ^ |   0 While counting the nodes we can simply return the number of adj nodes, without iterating them.Finding the xorsum we need to iterate them.
•  » » » » » » 14 months ago, # ^ |   +3 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 XORThus O ( V + E )
•  » » » » » » 14 months ago, # ^ |   +4 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
•  » » » » » » » 14 months ago, # ^ |   0 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" :/
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 Rerooting approach (couldn't implement it in time because I was stuck at problem B): Codevoid dfs1(int u = 0, int p = -1) { dp[u] = a[u]; for(auto v: g[u]) if(v != p) dp[u] ^= dp[v]; } void dfs2(int u = 0, int p = -1) { for(auto v: g[u]) { if(v != p) { edges.push_back({dp[v], dp[u] ^ dp[v]}); dp[u] ^= dp[v]; dp[v] ^= dp[u]; dfs2(v, u); dp[v] ^= dp[u]; dp[u] ^= dp[v]; } } } 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].
 » 14 months ago, # | ← Rev. 2 →   +4 what the heck is in test case 17 (and how to solve D)?
•  » » 14 months ago, # ^ |   0 +1
•  » » 14 months ago, # ^ |   +11 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!
•  » » » 14 months ago, # ^ |   0 T_T
•  » » 14 months ago, # ^ |   0 Test 17 is really depressing. In your case, it was for problem D and in mine, it was problem C. ;-;
 » 14 months ago, # |   +34 Thanks for interesting F
•  » » 14 months ago, # ^ |   +12 You are welcome!
 » 14 months ago, # |   0 Hurrahhhhh,,! after a long time againg specialist :)
•  » » 14 months ago, # ^ |   0 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.
•  » » » 14 months ago, # ^ |   0 CF-predictor: +144
•  » » » » 14 months ago, # ^ |   +1 It isnt 100% correct, expect for approx 25%>= change in the outcome
•  » » » » 14 months ago, # ^ |   0 now it's +118 . bye guys :(
•  » » » » » 14 months ago, # ^ |   0 F
 » 14 months ago, # |   +5 lmao someone got -1294 points for -50 hacks
 » 14 months ago, # |   +1 I've no idea why authors of C decided that it's possible to delete at most k-1 edges, while input is k :/
•  » » 14 months ago, # ^ |   +13 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.
•  » » » 14 months ago, # ^ |   0 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.
•  » » » » 14 months ago, # ^ |   +2 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.
•  » » 14 months ago, # ^ |   +3 Meaning that we cut the tree into k components, so the # of cut edges is k — 1.
•  » » 14 months ago, # ^ |   +4 K components is more natural
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I think it is so that there are maximum k disconnected components as the result of the edges deletion, pretty reasonable.
 » 14 months ago, # | ← Rev. 2 →   +4 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 :)
•  » » 14 months ago, # ^ |   +5 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.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 (deleted) I think I've figured out. Thanks.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   0 i dont think this approch is correct.but this is Accepted.this is case: ai=value at node[xor value] i= node number, k=(100) XOR=xor of the sum tree root at this node (a1=0,XOR=5) / \ (a3=0,XOR=5) (a2=0,XOR=0) / \ (a4=5,XOR=5) (a5=0,XOR=0) / (a6=0,XOR=0)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.
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 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.
 » 14 months ago, # |   0 How to solve C?
•  » » 14 months ago, # ^ |   +3 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$.
•  » » » 14 months ago, # ^ |   0 Thanks!
•  » » 14 months ago, # ^ |   +3 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
 » 14 months ago, # |   0 Anyone How to solve B i am sure for x=1 ans will yes and for x=n no :(
•  » » 14 months ago, # ^ |   +5 Hint 1Find an upper bound for when it's possible (a formula for $k$ in terms of $n$). Hint 2Test a few small examples, like $2\ 4\ 3\ 1\ 5$ and $k=3$, drawing the edges for which two spots you can swap. Hint 3Using the edges from Hint 2, try and find which two spots it's possible to swap using other spots as "buffers". Hint 4Which elements can you not swap at all?
 » 14 months ago, # | ← Rev. 2 →   +3 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
•  » » 14 months ago, # ^ |   0 When I suspect that something like this is happening, I delete everything, read the problem statement and start writing the code again.
•  » » » 14 months ago, # ^ |   0 it wasn't a typo i actually thought it's i+2
•  » » » » 14 months ago, # ^ |   0 I solved B the same way you did, but I think this is a better way : Spoilerfor (int j = n - x; j < x; j++){ if (a[j] != b[j]){ yes = false; } } 
•  » » » » » 14 months ago, # ^ |   0 I knew it's a continuous range but my mind just didn't work to calculate it i guess not my best day
 » 14 months ago, # | ← Rev. 2 →   -20 Is this called contest? :| I think you should change your minds
 » 14 months ago, # |   0 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.
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 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.com/contest/1592/submission/130700097
•  » » 14 months ago, # ^ |   0 Can you share your code for this
 » 14 months ago, # |   +9 I thought only Ehab is in love with XOR..It seems common for all Egyptians
 » 14 months ago, # |   +1 Seriously, what was pretest 10 in problem C!?
•  » » 14 months ago, # ^ |   0 You probably forgot that you have to use almost $k-1$ cuts.
•  » » » 14 months ago, # ^ |   0 Can't we always find the answer with exactly two cuts when the xor is non-zero?
•  » » » » 14 months ago, # ^ |   0 If $k = 2$ then you have only $1$ cut so the answer is NO.
•  » » » » » 14 months ago, # ^ |   0 I decremented $k$ already, I don't think that's the issue.
•  » » 14 months ago, # ^ |   0 I could not pass the pretest 10 as well ;(
 » 14 months ago, # |   +4 I think many ppl got stuck on the impl, C was actually pretty easy and interesting tbh.
 » 14 months ago, # | ← Rev. 2 →   0 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.
•  » » 14 months ago, # ^ |   +1 If Xor = 0, One cut is enoughIf Xor != 0, If there is a solution it always can be done with 2 cuts
•  » » » 14 months ago, # ^ |   0 Yea that makes sense, thanks.Now I just need to check where I went wrong in the implementation :/
•  » » 14 months ago, # ^ |   0 Proof: Let X represent XOR of all nodesIf 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 = 0therefore, z = 0 ^ y = y, so the two componnents will have equal xor valueIf X!=0, it can be done in 2 cuts. Let x, y, z represent xor of each component after two cutsx^y^z = Xsince all components are supposed to be equal, x = y = z, therefore:x^x^x = Xx^x^x = (x^x)^x = 0^x = xx = XSo we should make 3 components with xor value = X
 » 14 months ago, # | ← Rev. 2 →   +3 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
 » 14 months ago, # |   +31 Fun contest ! My delight in solving the problems outweighed the frustration from repeated stupid bugs. Good job round setting team
•  » » 14 months ago, # ^ |   +20 Thank you!
 » 14 months ago, # |   +1 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.
 » 14 months ago, # |   +11 Great round but problem C and D aged me $10+$ years
 » 14 months ago, # | ← Rev. 2 →   +1 Nice Contest , Thanks For The Round . Although my bad form Continues (Solved A and C but failed in B) , I enjoyed the round .
 » 14 months ago, # |   0 Only able to solve A but all problems are interesting and educational. Great round Hemose and other problem setters too
•  » » 14 months ago, # ^ |   0 Thanks!
 » 14 months ago, # |   +6 Now that all my problems passed system tests, I'd like to express my admiration and say Good job guys <3
•  » » 14 months ago, # ^ |   +4 Thanks!
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   +17 The system testing is in "Flash" mode
 » 14 months ago, # |   +8 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.
 » 14 months ago, # |   +2 Really enjoyed the round, especially the C problem !!!
 » 14 months ago, # |   +6 Amazing ABCD, but E was quite easy for its position. Amazing contest.
 » 14 months ago, # | ← Rev. 3 →   +8 My code for problem C was wrong and i have the wrong case for it The test18 316 16 8 8 1 3 3 21 22 33 44 55 66 77 8and it passed the systests !!!!!so weak systests its just a simple case !!!!
•  » » 14 months ago, # ^ |   +3 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.
•  » » » 14 months ago, # ^ |   0 Yeah I found it out its now a correct test
•  » » » » 14 months ago, # ^ |   +6 Sir Bakry or Hemose can you look into this?
 » 14 months ago, # |   +1 Hard, but very exciting set!!!
 » 14 months ago, # |   0 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 1If 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
•  » » 14 months ago, # ^ |   +3 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
 » 14 months ago, # |   0 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.
 » 14 months ago, # |   +1 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 :DOne 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.
•  » » 14 months ago, # ^ |   0 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
•  » » » 14 months ago, # ^ |   0 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +4 We are happy that you enjoyed the contest!The constraints are the same from the beginning we didn't modify anything.
 » 14 months ago, # |   +5 Is there anyone, who also thought problem C is doable and then couldn't able to solve it :(
 » 14 months ago, # |   +15 Round was excellent!
 » 14 months ago, # |   +13 When will the problems can be submitted?
•  » » 14 months ago, # ^ |   0 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.
 » 14 months ago, # |   0 Can anyone explain the approach for problem B??
•  » » 14 months ago, # ^ |   +1 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.
•  » » » 14 months ago, # ^ |   +1 hey, i do understand that but can someone prove that all swappable elements can be sorted??
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +1 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.
 » 14 months ago, # | ← Rev. 2 →   0 130711588 This submission is taking a lot of time. why why!!!!
 » 14 months ago, # |   0 difficulty gap between B and C was too high
•  » » 14 months ago, # ^ |   +1 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.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +1 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.
 » 14 months ago, # |   0 very interesting problemset, I missed C by few seconds :/ https://codeforces.com/contest/1592/submission/130724367
 » 14 months ago, # | ← Rev. 2 →   +1 pretest 10 on C haunts me , anyways nice contest
•  » » 14 months ago, # ^ |   0 same here, I found the testcase but I completed my solution 3 seconds after the contest :/ really just 3 seconds :/
 » 14 months ago, # |   0 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.
•  » » 14 months ago, # ^ |   0 Yeah, I like E because The solution becomes easy and short after one observation.
 » 14 months ago, # |   0 hard one but good one
 » 14 months ago, # |   +4 What is happening to this 130711588 submission by rainboy to problem D? It is getting "Denial of judgement". I have never seen one before...
•  » » 14 months ago, # ^ |   0 Update: It became "Accepted". I wonder what happened...
•  » » » 14 months ago, # ^ |   +3 We just rejudged the solution, We don't know the reason for this verdict.
•  » » » 14 months ago, # ^ |   +4 we've rejudged his solution and he got AC
 » 14 months ago, # |   +15 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.
•  » » 14 months ago, # ^ |   +4 Thanks! We are happy that you enjoyed the contest!
 » 14 months ago, # |   0 Thanks for interesting problems, I felt like real div2 C diff problem was missing.
 » 14 months ago, # |   +15 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
 » 14 months ago, # |   +11 Telling everyone you're hitting expert After rating change
 » 14 months ago, # |   +9 F1,F2 are interesting.
 » 14 months ago, # |   -8 صباحو
 » 14 months ago, # |   0 Finally became a Div. 1 Newbie.
 » 14 months ago, # |   +8 got -106 but still wht a great round and quality problems