### Supermagzzz's blog

By Supermagzzz, history, 12 days ago, ,

Hello Codeforces!

We, Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, are ITMO students, who want to contribute to Codeforces community, went to MikeMirzayanov and offered him to help with rounds testing. But MikeMirzayanov invited us to create our own round with his help. And now...

We're glad to invite you to Codeforces Round #603 (Div. 2), which will be held on Nov/29/2019 17:35 (Moscow time). It will be rated for all participants with a rating below 2100. You will be given six problems and two hours to solve them.

The problems were invented and prepared by Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, MikeMirzayanov.

Special thanks to:

• MikeMirzayanov for great systems Codeforces and Polygon and coordinating round preparation.

UPD: Scoring: 500 — 1250 — 1250 — 1750 — 2500 — 3000

We hope you will enjoy the problems. Good luck, wish you a high rating!

UPD1.5: Thanks for participating! Congratulations to the winners!

Top 5 Div. 2:

Top 5 Div. 2 + unoffical:

UPD2: Editorial is out!

• +325

 » 12 days ago, # |   +30 Are there any subtasks?
•  » » 12 days ago, # ^ |   +47 No.
 » 12 days ago, # |   -41 Please share the score distribution.
•  » » 12 days ago, # ^ |   +15 Why do you have negative contribution?
•  » » » 11 days ago, # ^ |   -30 I am trying to get the feel and nature coders. Right now, I am not aware of it so this may be a reason. Hope for positive contribution soon :)
•  » » 12 days ago, # ^ |   +8 It will be shared about an hour before the contest . Does it make any difference though?
 » 12 days ago, # | ← Rev. 2 →   -31 I hope tomorrow I will be able to reach 2100 :)
•  » » 11 days ago, # ^ |   -16 Maybe the dislikes for your comments are because your avatar...
•  » » » 11 days ago, # ^ |   +45 Or because it's spam
•  » » » 11 days ago, # ^ | ← Rev. 2 →   -11 Or maybe he just posts comments wich are not usefull at all and reading them is not a good way of spending time
•  » » 11 days ago, # ^ |   -11 Me too!
•  » » 11 days ago, # ^ |   -14 I am not able to reach 2100 because I have missed a +1 in my code..:(
 » 12 days ago, # | ← Rev. 2 →   -13 This time no copy-pasted part ! ;)
 » 11 days ago, # | ← Rev. 2 →   -28 Good luck and high rating!
 » 11 days ago, # |   -31 hope to become specialist in this contest.
 » 11 days ago, # |   -53 Is it rated?
•  » » 11 days ago, # ^ |   -34 Yes, it is
•  » » » 10 days ago, # ^ |   -16 WOW! you guys are so mean
 » 11 days ago, # |   -30 I hope to become specialist in this contest. :)
 » 11 days ago, # |   -27 Hope it's not mathforces like last time! GLHF!
 » 11 days ago, # |   -14 good luck for all
 » 11 days ago, # |   -15 Scoring Distribution?
 » 11 days ago, # |   -18 Score distribution?
•  » » 11 days ago, # ^ |   0 here it is!
 » 11 days ago, # |   +9 There is a bug. I see some yellow coders in the official standings!
•  » » 11 days ago, # ^ |   +17 Yes, my bad. I'll fix it after the contest.
 » 11 days ago, # | ← Rev. 2 →   0 How to solve A?Am not sure of my solution :(
•  » » 11 days ago, # ^ |   +2 Sort by magnitude. It is optimal to pair the smallest with the largest until the largest and the middle are equal (or as close as you can), then pair the smallest with largest once and smallest once until you run out of smallest.
•  » » » 11 days ago, # ^ |   0 Nice solution!Thought so too, but tried different approach....:( Thanks BTW!
•  » » » 11 days ago, # ^ |   0 got timeout using this :? Python3.6
•  » » » » 10 days ago, # ^ |   0 You can't simulate the optimal solution directly, it's too slow (you could take up to hundreds of billions of steps across all $1000$ test cases). You need to find a way to calculate the steps mathematically.
•  » » » » 5 days ago, # ^ |   0 I did not actually do the simulation directly — it's just a description of how to go about this optimally. To simulate the simulation, I found difference between highest and middle, and checked whether it is higher than lowest or not. If so, then answer = lowest + middle. Otherwise, set lowest = lowest — diff and set highest to middle. Now remove lowest/2 from highest and mid, add answer = (lowest%2==0? lowest : lowest — 1) + min(mid, high) Not a very good solution (some repeated code) but you can see 65992022 to get the idea
•  » » 11 days ago, # ^ |   0 I found A very similar to this problem: https://codeforces.com/contest/1260/problem/B
 » 11 days ago, # |   +59 Non-dp solution for F: SolutionFirstly, we can achieve our goal by deleting all edges in the first or second tree, so suppose now that we leave at least one edge from both trees.We can consider our goal as choosing vertices from both trees so that the vertices from a tree are connected and for each pair of corresponding leaves, at least one of them is chosen.This sounds like a min cut problem.Suppose we label each vertex with S or T. A vertex in the first (second) tree is labelled S (T) if and only if it is chosen. How can we encode our conditions?Firstly, the root of the first (second) tree must be labelled with S (T).Next, if a node in the first (second) tree is labelled with S (T), then so is its parent.Finally, for each pair of matching leaves, we cannot have the first one labelled with T and the second one labelled with S.We want the minimum cut to denote the minimum number of vertices we can choose.How the final flow graph looks like:Vertices: Source, sink and the vertices of the 2 trees.For each non-root vertex of the first tree, there is an edge from it to its parent with capacity INF. For each vertex of the first tree, there is an edge from it to sink with capacity 1.For each non-root vertex of the second tree, there is an edge from its parent to it with capacity INF.For each vertex of the second tree, there is an edge from source to it with capacity 1.For each of the $n$ pairs of leaves, there is an edge from the leaf of the second tree to the corresponding leaf of the first tree with capacity INF.There is an edge from source to root of first tree with capacity INF.There is an edge from root of second tree to sink with capacity INF.
•  » » 10 days ago, # ^ |   +18 Your solution is so overcomplicated, but still very cool. Linear solution to FObservation 1: if some vertex is not going to be used, it's whole subtree is not going to be used. So let's have each vertex as some segment on the leaf vertices and by deleting this segment we can delete every edge in this subtree and the edge to it's parent (if there is one). Observation 2: those segments must cover each leaf exactly once (otherwise it would not be correct nor optimal). So it dropped down to a task: given a + b segments with some cost c find a coverage of n leaves with maximum cost, which is a stupid dp.
•  » » 18 hours ago, # ^ |   0 Hi! That's a nice solution. I just tried your approach. But, I believe that the case of deleting all edges from one of the trees is also covered as a special case in the minimum cut algorithm. Instead of outputting $max(a-1, b-1, a+b-maxflow)$, I just outputted $(a+b-maxflow)$, and it got AC.
 » 11 days ago, # |   +38 A-E all classical problems
•  » » 10 days ago, # ^ |   0 You have solved similar problems like A-E ? If so , would you please give the links of some of those problems ?
•  » » » 10 days ago, # ^ |   +8 They indeed looked familiar. E.G. as far as I remember the solution of A was also needed to solve DeleteArrays from SRM770
 » 11 days ago, # |   +10 The problems were great! Who can tell me how to solve C?
•  » » 11 days ago, # ^ |   +4 I found that if I just iterate for divisors till sqrt(A), then all quotients I get for higher values lie in a single continuous range.
•  » » » 11 days ago, # ^ |   +1 success or timeout?
•  » » » » 11 days ago, # ^ |   0 Success!
•  » » » 11 days ago, # ^ |   +1 Thank you!
•  » » 11 days ago, # ^ |   +5 You could refer to this post.
•  » » 11 days ago, # ^ |   0 i think i am right,but the answer is TLE.how to solve C?
•  » » » 11 days ago, # ^ |   0 Lol, your solution uses t both as the count for tests and n / i so it runs forever.
•  » » » » 11 days ago, # ^ |   0 thanks for your help.i know my error now
•  » » 11 days ago, # ^ | ← Rev. 2 →   +1 Imagine we iterate through kn/k — n/(k+1) = n/(k(k+1))this means that if k > sqrt(n) then at each step you will be decreasing less than 1so, after that you will pass for all non negative integers
•  » » 11 days ago, # ^ |   +1 start diving from i=1 and keep increasing unless u don't get same value when doing floor(x/i) after that it's a continuous decrease like for x=1000 at i=37 u will get floor(1000/37)==27 which is repeat for i=36. This means after 27 all are included like 2, 25...2,1,0. but i still got timeout. ;? but i see rohit_goyal has more optimal solution
•  » » 11 days ago, # ^ |   0 You can also start from 1 and do binary search every time that until what number n /j == i. and then move the pointer to that number .
•  » » 11 days ago, # ^ |   0 Well, for fixed n f(k) = n/k is a monotonous function. Binary search is a solution in O(Ans*log(n)).
 » 11 days ago, # |   0 I'm sad I didn't see D solution is it graphs or something
•  » » 11 days ago, # ^ |   +6 I think it was related to Union — Find algorithm...
•  » » 11 days ago, # ^ |   0 Yes ; one can connect strings who have a common character ( As these two strings are equivalent ) ; and finally answer is number of connected components !
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 It can be solved greedily as well. Start with the string having the most number of distinct characters and simultaneously mark the characters you have gone through. If we come across a string in which all it's characters are already marked, we need not count that string in our final answer.PS: The DSU Approach is great.
•  » » » 10 days ago, # ^ | ← Rev. 6 →   0 The greedy approach fails at test case 68. i tried it! when the strings of have same length have same number of unique elements and all are different it fails.for example abcd efgh faexpected — 1 output — 2
 » 11 days ago, # |   +2 Is pD really that easy ?? I tried to do it with a bitmask-things but I couldn't. Can somebody help?
•  » » 11 days ago, # ^ |   0 For each letter find a word that contains it and build a graph by connecting every other word that contains it with that word. The answer is the number of connected components of that graph.
•  » » 11 days ago, # ^ |   +7 it's dsu. But only there are only 26 arrays, so I think bruteforce may be accepted too.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 A node is a charfor each pair of letters x,y in a string add an edge x->yThe answer is the number of connected components
•  » » 11 days ago, # ^ |   +3 It is fairly simple dsu, just build groups by contained characters.
•  » » 11 days ago, # ^ |   0 For every password you could build a set of letter. then if 2 letters are in 2 passwords — just join the sets. after count how many sets left
•  » » 11 days ago, # ^ |   0 Wow I just realized that I totally misunderstood the Task. Rating goes down again!
•  » » 11 days ago, # ^ |   0 You can use simple approach such as brute force :))) 65990114
•  » » » 10 days ago, # ^ | ← Rev. 4 →   0 Your solution gives wrong answer on test case 67, though its accepted. Quite strange
•  » » » » 10 days ago, # ^ |   0 it didn't have test case 67, bro!!
•  » » » » » 10 days ago, # ^ |   +5 It does have test case 67. Check my 2nd last submission, I just pasted your code and it gives WA kn test 67
•  » » » » » » 10 days ago, # ^ |   0 Wow, this is my first time seeing something like that.Is that a hack test case?
•  » » » » » » 10 days ago, # ^ |   0 New test case after contest ??
•  » » 11 days ago, # ^ |   0 Yes ; for each string ; you may store a bitmask corresponding to it ; and then the strings with common character could be joined ; and at last answer will be number of connected components !A code which does bitmask + DSU : https://codeforces.com/contest/1263/submission/65980587
 » 11 days ago, # |   -8 In F, wires between nodes do not intersect. shouldn't it be bolded?
•  » » 11 days ago, # ^ |   -8 Hmmm, my bad. I didn't see the condition It is guaranteed that each grid is a tree, which has exactly n leaves and each leaf is connected with one device. Also, it is guaranteed, that for each tree exists a depth-first search from the node 1, that visits leaves in order of connection to devices.
 » 11 days ago, # | ← Rev. 2 →   +17 I don't understand why such a tight time limit was put in E. It cost me multiple TLEs when writing output using cout, however with printf it passed.
•  » » 11 days ago, # ^ |   0 I had the same issue — little bit annoying lol
•  » » » 11 days ago, # ^ |   +6 VERY annoying actually.I used Java, and with Java lazy SegTree doesn't pass at all :(
•  » » » » 11 days ago, # ^ | ← Rev. 14 →   0 you can solve it without lazy just normal segTree my submission (that was after contest because I forgot ind = max(ind,0) xD )
•  » » 11 days ago, # ^ |   0 I too was getting TLE, but it was a coding error in my case though, I was calculating values again and again, instead of just referencing already stored values... :(
•  » » 11 days ago, # ^ | ← Rev. 2 →   +42 Jury has a simple linear solution with stacks in this problem.
•  » » » 11 days ago, # ^ |   -16 Ah, that's cool, but imho segment tree with lazy propagation isn't really a bad solution to this problem.
•  » » » » 11 days ago, # ^ |   0 How to use segment tree WITH lazy propagation in this problem? I came up with a solution only needed to modify a single position.
•  » » » » » 10 days ago, # ^ |   0 I think they update the prefix sum.
•  » » » 11 days ago, # ^ |   +7 Its a little sad though when you correctly implement everything, but still get TLE because of using Java :(I think the time limit should be 3 seconds, or N should have been less than 200,000.
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   +3 After the contest I optimized a tiny bit and got it to pass. I changed all the longs to ints first (I'm not sure if this actually did anything meaningful). Most importantly, you're querying three times over the segment tree per change, which can be reduced to one (Query max and min at the same time because they're over the same range and manually store the prefix sum over the entire array). However I see that you fail on TC 4, which means that you might have to optimize your seg tree implementation.Edit: Some other simple optimizations, I found .toCharArray() to be faster than charAt(i). Also when you build your segment tree you can initialize your tree as zeros to save some time
•  » » 11 days ago, # ^ |   0 I think cout endl cause TLE. Pls read this https://codeforces.com/blog/entry/43780 for more information.
 » 11 days ago, # |   0 How to do first if there are n piles.
•  » » 11 days ago, # ^ |   0 Its very similar:min(sum of n-1 smallest piles, sum of all piles / 2 floor)
•  » » » 11 days ago, # ^ |   0 Thank you.
•  » » 11 days ago, # ^ |   0 I think that if you want you could derive the condition considering finally piles are of the form : { 0 0 0 0 0 0 A 0 0 0 ...... 0} So you could apply constraint between A, sum of all piles and largest pile's value and find minimum A, and hence maximize the value of answer!
 » 11 days ago, # |   +10 Is intended solution for E Segment Trees w/ Range Propagation and then leveraging min/max/sum?
•  » » 11 days ago, # ^ |   0 My solution on that passed in 202ms so I guess yes.
•  » » » 11 days ago, # ^ |   +3 Damn Java
•  » » » » 11 days ago, # ^ |   0 Lol system tests even reduced that to 187ms
•  » » 10 days ago, # ^ |   0 No, it wasn't intended to be seg-tree in any way, although many solutions passed... It can be solved with 2 stacks storing brackets, one from left and other right, with 2 arrays(although i used sets 66013420) to check the max and min on both sides
•  » » » 10 days ago, # ^ |   0 I used the same but got runtime eror, can you check my solution?
•  » » » » 10 days ago, # ^ |   0 It's seems like STL stack overflow error, your stack couldn't allocate 5*10^5 size... although my STL vector could.
 » 11 days ago, # |   +3 In Problem E. How to update number of different color need to use if text is correct
•  » » 11 days ago, # ^ |   +4 I found that we can use the maximum prefix value(by assigning openings as 1 and closings at -1) that one can get as answer, because answer is longest opening sequence(it may have some complete brackets within) and any closing would just decrease the answer
 » 11 days ago, # |   0 I'm so confused where do I wrong on E. I was so close to an AK.
 » 11 days ago, # |   0 Anyone got the wrong answer on pretest 2 of A and then got correct?Or any possible testcase where this could get wrong?Thanks in advance :)My solution — https://codeforces.com/contest/1263/submission/65990422 (I stresstyped every possible case because I was getting the wrong answer :( )
•  » » 11 days ago, # ^ |   +3 I believe yours fails on the input 3 4 5 since then it returns 5 whereas 6 is the answer.
•  » » 11 days ago, # ^ |   0 On the case 10 15 20 your code returns 20 while the answer is 22.
 » 11 days ago, # |   +51 strange round. D is just — "oh my, write DSU". E is just "oh my, write segtree with mass updates".
•  » » 11 days ago, # ^ |   +2 No DSU was needed in D. Create N+26 nodes (N nodes for each string, 26 nodes for each character). Connect node of string and character, if the string contains this character. Answer = number of connected components among nodes corresponding to strings.
 » 11 days ago, # |   +32 I think ideas of CD are quite standard. E is just a boring version of this.
 » 11 days ago, # |   0 Very easy div2 contest.
 » 11 days ago, # | ← Rev. 2 →   0 For probB ,My solution passed pretest 2 . But failed on test 2 , is'nt it amazing .
 » 11 days ago, # |   +7 So, I tried to solve E using a Segment Tree with lazy propagation. I wrote the bracket series as a prefix sum, for example like [1,2,3,2,1,0,-1,0,1]. Then, to process 'L' and 'R' moves I just shifted an index variable. To process '(' and ')' updates I simply lazily updated all the numbers in the prefix after the index i. Then, to find if it was valid or not, I simply used Segment Tree range min and range max query.In total, my algorithm was Nlog(N). And yet it TLED. Any reason why? (I used Java)
•  » » 11 days ago, # ^ |   -6 First, nlogn in segment tree. Second, Java.
•  » » » 11 days ago, # ^ |   0 Can you be more specific thx.
•  » » » » 11 days ago, # ^ |   0 Segment tree has a rathar large factor constant. And so Java.
•  » » 11 days ago, # ^ |   0 Here is a link to my code 65980577
•  » » » 11 days ago, # ^ |   0 TL 1 second, n = 10^6, you use java. there is no chance
•  » » 11 days ago, # ^ |   0 Apparently the intended solution was linear, i was thinking about segmet tree too, but i guess we will have to wait for the editorial. https://codeforces.com/blog/entry/71803?#comment-561282 Some people were able to get nlogn with fast inputs too, it seems.
 » 11 days ago, # | ← Rev. 2 →   +1 A is quite beautiful if you prove things by construction and the triangle inequaltiy.
•  » » 10 days ago, # ^ |   0 How to solve A using triangle inequality ?
 » 11 days ago, # |   0 How to solve B..?
•  » » 11 days ago, # ^ |   0 For repeating pins, replace their first digit with the digit that is not present in other pins first digit. Since maximum value of n is 10, we can be sure that all digits will be distinct after the process.
•  » » 11 days ago, # ^ |   0 If the pin is $Pi$, Check from $Pi-100$ to $Pi+100$, get the one which is unused and gives min difference with original
•  » » 11 days ago, # ^ |   0 I thought it like this : Say I iterate over the input values(as strings) and if I have more than 2 strings of current type, I can change it to a whole other string just by changing 1 character because if I just change a single character, I can get 40 strings or nearabout that number of strings, so I just find such a string by brute force, trying changing each character so 4*10 combinations are there, and changing string value to the one which is not present in my set of strings, and incrementing the count of moves by 1.Finally I print all the new strings(or old ones in case of unchanged....)!
•  » » » 11 days ago, # ^ |   0 Thanks, my algorithm was exactly what you said. I just realized that my implementation was wrong..TT
 » 11 days ago, # |   0 The problemset is nice although i performed badly this time :(
 » 11 days ago, # | ← Rev. 2 →   +50 "L — move the cursor one character to the left (remains in place if it already points to the first character);""It is guaranteed that all characters in a string are valid commands."Somehow I thought the second line meant that there can't be an input where you go left from the first position...... (and it doesn't seem to even be in the pretests?)(Also trying to fail $O(n\log n)$ segtree solutions with $n \le 10^{6}$ and 1s TL is not really cool as many such implementations actually would pass. I think this has been said by many people in different contests, but either give up on failing these solutions or increase the constraints so that it would clearly fail all (or at least those without extremely heavy constant optimizations attempts) "bad solutions" (in this case it's hard to increase because of I/O size though, so maybe some input/output compression would work))
•  » » 11 days ago, # ^ |   +1 I think this might have been in pretest 5. Luckily, I had an assert that checked L was valid... But I agree this is confusingly worded
•  » » » 11 days ago, # ^ |   +5 Welp my solution failed system tests because of that so I thought it might not be in the pretests.
•  » » » » 11 days ago, # ^ |   0 I don't think it is in the pretests either, as I failed on the same thing.
•  » » » » 10 days ago, # ^ |   0 I failed on pretest 5 due to my pointer going out of bounds i.e. -1, so it was in the pretests, although it didn't affected ur solution.
•  » » 10 days ago, # ^ |   0 I didn't deal with this situation in my program,pretest passed,but system test failed.
 » 11 days ago, # |   0 i got timeout for 1st question :/ My approach: subtract difference of 2nd_max and 3rd_max from 1st_max and 2nd_max. count changes to count+difference(2nd_max-3rd_max) Now find 1st_max and 2nd_max and decrease them by 1 and count changes to count+1. Output is optimal but not able to pass the time limit. Please share ur algo if u passed
 » 11 days ago, # |   +19 MikeMirzayanov Did you just banned Ashishgup only because he wrote "A-E are classical".
•  » » 11 days ago, # ^ |   +110 He is not banned, he is temporarily in the read-only mode. I believe that the rules should be the same for everyone. And any discussion of problems during the contest is unacceptable. We cannot predict how this or that opinion about the problems will affect the participants. I am pleased to discuss the problems, but this can only be done after the end of the round.
 » 11 days ago, # |   0 Too much easy problem set!
 » 11 days ago, # |   +6 Can anybody tell me if this solution is correct for problem E? My solution use segment tree without lazy propagation. For each node in the segment tree I know v[nod].left = number or '(' without a pair (basically open) , v[nod].right = same but for ')' and v[nod].depth = how many colors do I need. How to find v[nod].depth if we know every information for its children? v[nod].depth = max ( v[ 2*nod ].depth, v[ 2*nod+1 ].depth) maximum depth of its children + min ( v[2*nod].left, v[2*nod+1].right) this if for: '(' CONFIGURATION + CONFIGURATION '))' so in this case I increase the depth with 1 because I make new pairs. I had a bug in implementation so I couldn't submit it, but does anybody have the same approach?
•  » » 11 days ago, # ^ |   +8 Alternatively, You can consider point updates +1 for '(', -1 for ')' and 0 otherwise. Then maximum prefix sum is depth and minimum prefix sum should be 0 for correct sequence.
•  » » » 11 days ago, # ^ |   +3 yeah, this is the approach with lazy propagation. Or, could it be solved without lazy?
•  » » » » 11 days ago, # ^ | ← Rev. 3 →   0 You can maintain the maximum and minimum prefix for each segment node. Then you won't need lazy propagation.
 » 11 days ago, # |   0 Time limit for different languages is different or same for all?
 » 11 days ago, # |   0 Can Someone Explain How To Solve Problem C? I kind of felt it was related to divisors
•  » » 11 days ago, # ^ |   0
 » 11 days ago, # | ← Rev. 2 →   +26 Maybe I am the only one who solved B using mincost-maxflow.
•  » » 11 days ago, # ^ |   +14 maybe I am the only one who solved B using randomization?
•  » » » 5 days ago, # ^ |   +3 I used srand(time(0)) ; in your code and got WA at first at test-8 , then on test-10. But without using srand(time(0)) , your code gets AC . Any idea why this is happening ?
•  » » 11 days ago, # ^ |   +54 I'm calling the police
•  » » 11 days ago, # ^ |   -11 Yeah, you used a bomb to kill a mosquito.
•  » » 11 days ago, # ^ |   +5 I thought of using Hopcraft Karp algo. but gave up even before I began to code XD
•  » » » 5 days ago, # ^ |   0 For which problem ?
•  » » 11 days ago, # ^ |   0 Was it bipartite matching implemented with flows? Cool! Here is my idea: start with the 10 pins; this is part A. Connect each pin with numbers that differ in one place or don't differ at all. You get up to 40 neighbors. This is part B. Now find a perfect matching between A and B. The numbers which pins are matched to are the answer.
•  » » 11 days ago, # ^ |   0 How?
 » 11 days ago, # |   +2 My first submission to D got accepted but it doesn't pass 4 a ac b cb 
•  » » 11 days ago, # ^ |   0 Answer should be 1 right? I saw both of your submissions giving 1 as output :3...
•  » » » 11 days ago, # ^ | ← Rev. 3 →   0 When I ran it in the Codeforces custom test it printed 2.My first submission should be wrong because my find() function recursively calls find(cur) instead of find(par[cur]), and when I insert the numbers into set< int > cnt, I should insert find(par[cur]) instead of par[cur].
•  » » » » 11 days ago, # ^ |   0 Seems that there's a problem in judge data... Some other solutions also got AC which was actually wrong.. sad :(
 » 11 days ago, # |   +22 Good contest!
 » 11 days ago, # |   +5 I think the problems were much easy and this should've been a div 3... anyways... thanks to the setters.
 » 11 days ago, # | ← Rev. 2 →   +8 MikeMirzayanov Supermagzzz My solution for E passed the pre-tests, but after system testing gave TLE on test case 5 which was part of the pretests.65979337Moreover changing language from c++17 to C++14 got accepted 65994359.Can you look into it.
•  » » 11 days ago, # ^ |   +29 See, your solution is on the edge between OK and TL. It is just a random it fits in TL or not. Just try to improve your solution a bit. Also, it is a good practice to verify that your solution fits in TL with some gap on pretests.As I see this problem can be solved even on Python, so I don't think the TL is too tight.
 » 11 days ago, # |   +9 I Got AC in problem D, I think it shouldn't pass. Consider the following test case: 3 asd qwe aq
•  » » 11 days ago, # ^ |   0 your solution outputs 2, but it should be 1! MikeMirzayanov can you please see this?
•  » » 11 days ago, # ^ |   0 exactly!
•  » » 11 days ago, # ^ |   0 Another similar submission is here: 65988894
 » 11 days ago, # |   +31 I used a O(n) algorithm to solve Problem F.It can be proved easily that when each of the electrical devices is covered by just one grid, the answer will be the best. And the problem guarantees that every nodes x in the grids will cover a range [l, r]. That means we can disconnect the electrical devices with the gird if we erase the edges connecting to the nodes in the subtree of x. We can get it by doing a dfs/bfs. Then the problem is transfromed to an easier problem: There are some ranges, each range has a value. we need use them to cover the range [1, n] and maximize the sum of these values. dp[i] means the maximum sum of value when the range [1, i] is be coverd. For dp[i], we just need to check the ranges beginning at i + 1 to transform it. So every range will be used just one time. It also solves in O(n).
 » 11 days ago, # |   +16 F can be easily done in $O(n)$https://paste.ubuntu.com/p/8SJHkS5w6d/I'm very confused about range of $n$ in contest....
 » 11 days ago, # |   +15 It is the first time I reach Purple, thanks to this interesting contest.
 » 11 days ago, # | ← Rev. 2 →   0 I can't understand why my submission for B got WA.
•  » » 11 days ago, # ^ |   0 Study how your code performs when the input is 3 0000 0000 1000Your code makes 2 moves, whereas the minimal moves required is 1.
•  » » » 11 days ago, # ^ |   +3 Thank you.
 » 11 days ago, # |   +1 The templet of segment tree used in Problem E. can be found at https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/UESTC/2156.cppBut someone else used that templet in E and our codes are almost the same. So I was blocked, but I promise that we didn't communicate with each other during the contest.I wonder how to solve the misunderstanding.
•  » » 11 days ago, # ^ |   +11 The main parts of the codes are completely identical:
 » 11 days ago, # |   0 Problem A idea is same as https://codeforces.com/problemset/problem/478/C (Table decorations).
 » 11 days ago, # |   -13 MikeMirzayanov, why has my 65968043 to 1263A - Sweet Problem been "Skipped"? It's the first time when i see this. By the way, I didn't cheat. At the round verdict was all pretests passed and I leave round with happy thought that I 'll become green. Now I am very disappointed.
•  » » 11 days ago, # ^ |   -21 Your earlier submission of A accepted so your later submission is skipped.
•  » » 11 days ago, # ^ |   -15 This is really unfair, king. I think we all must do everything possible of us to correct this blatant act of injustice. MikeMirzayanov, you really need to look into this horrible situation.
•  » » 11 days ago, # ^ |   +30 Instead of a thousand words:
•  » » » 11 days ago, # ^ |   -24 Could you check another accounts by IP? Especially my time is different.
•  » » » 11 days ago, # ^ |   -41 MikeMirzayanov, maybe I could prove my innocent. Before send I program in ideone.com . In this site there is a page "Recent code". This is my code: https://ideone.com/L2fM6l . It's a public paste. On 23:22 I have found this code here (https://ideone.com/recent/19). So, all users that use ideone are at risk be unrated, don't they?
•  » » » » 10 days ago, # ^ |   +38
•  » » » » 10 days ago, # ^ |   +12 In the terms of agreement when you register, you are forbidden from sharing or publishing your code before the contest finished. Also I have no idea why you need to paste your code onto public paster. No matter intentionally or not, the fact that your code is somehow published makes your code skipped. This would be fair for everyone.
 » 11 days ago, # | ← Rev. 2 →   0 What is the answer for this input of problem D? 4 a b ab acd EDIT: How about this? 3 abc abd abe 
•  » » 11 days ago, # ^ |   0 1
 » 11 days ago, # |   +5 Test case for 1263D - Secret Passwords was weak.This submission 65988894 gives output 2 for input 3 ab bc ca, but output should be 1.
•  » » 10 days ago, # ^ |   +1 yeah, I got accepted with the false solution(naive one), after the contest, you can check 66023526 which fails for a simple test case like this: 7 a b c d ab cd abcdHere the correct answer is 1, but the program outputs 0.
 » 11 days ago, # |   +5 So, I am done with the comments, would like to read the editorial now. Thanks!
 » 11 days ago, # |   +14 in the rating changes the rating predictor rating is not same as the changed rating for this contest has codeforces changed their rating algorithm and forgot to update the predictor????
•  » » 11 days ago, # ^ |   +7 Oh... You are right. The predictor showed me +12 but I actually have -5 :(
•  » » » 11 days ago, # ^ |   0 i waited for the standings and they came out wrong :(
•  » » 11 days ago, # ^ |   +12 cf-predictor used ratings before last educational round so that's why rating changes are inaccurate.
•  » » 11 days ago, # ^ |   +4 CF Predictor is a 3rd party extension. CF has nothing to do with it.
•  » » » 11 days ago, # ^ |   -8 read this mate https://codeforces.com/blog/entry/50411
•  » » » » 4 days ago, # ^ |   +1 thank you .
•  » » 4 days ago, # ^ |   0 yes , i faced same issue.
 » 11 days ago, # |   +3 I don't understand what hacking is. Does anyone explain it to me? And when I get hacked?
•  » » 11 days ago, # ^ |   +1
•  » » 11 days ago, # ^ |   0 It means that there are some bugs hiding in your code. The bugs may be some easily mistakes such as OVERFLOW, FORGET TO CLEAR MEMORY. Your wrong code with these mistakes can pass pretest data, but have high probability FST. The hacker is helping you to improve your program.This is the charm of Codeforces I think.
•  » » » 10 days ago, # ^ |   0 Thanks
 » 11 days ago, # | ← Rev. 2 →   +12 Well at least I found out about how editors color the brackets in code today! XD
•  » » 11 days ago, # ^ |   0 In my experience they mostly stop responding or crash horribly when you load a huge file of parentheses...
•  » » » 11 days ago, # ^ |   0 I guess it indicates brute force implementation in editors. :D
 » 11 days ago, # | ← Rev. 2 →   +7 Can anyone please tell me how to hack a submission after the contest ? I am getting this message "You cannot hack the submission"
•  » » 10 days ago, # ^ |   0 At least when it came out, "uphacking" was restricted to div1 users. Maybe that's still the case. (Source: https://codeforces.com/blog/entry/68204)
 » 11 days ago, # |   +13 This was a very interesting contest !
 » 11 days ago, # | ← Rev. 2 →   0 There seems to be a problem with the C compiler for problem C. My solution 66003014 submitted in GNU C11 TLEd on test 4 but the exact same solution submitted in GNU C++17 66003340 passed comfortably MikeMirzayanov supermagzzz
•  » » 10 days ago, # ^ | ← Rev. 2 →   +3 You have to choose the compiler yourself. Different compilers have different efficiencies (optimizations).
•  » » » 9 days ago, # ^ | ← Rev. 2 →   0 I'm pretty sure GNU C11 is the only compiler available for C. There is no reason why a SQRT(N) solution would timeout when compiled in C vs when compiled in C++ (both are compiling the SAME SOURCE code). My guess is that an incorrect TLE multiplier was applied(some sites apply multiplier for different languages so that implementation in slower languages like Java don't TLE)
•  » » » » 9 days ago, # ^ |   +1 printf is very slow in C11
•  » » » » » 9 days ago, # ^ |   0 Checks out! Replacing printf with putchar brought down the execution time from 2s to 46 ms. Thanks for pointing it out. Something to remember during future contests
 » 11 days ago, # | ← Rev. 4 →   0 If you want to see my personal editorials for the problems, come to my blog!:p CF Round 603 Broken Editorial
 » 11 days ago, # |   0 WDYT about solving 1263F - Economic Difficulties with min-cost-max-flow? Let every edge have flow one and cost one. The sink is connected to the two root nodes, and the n devices have a single outgoing edge to a sink node; each with flow 1. The min-cost flow will then use as few edges as possible. MCMF can be solved in $O(E^2)$, which should be small enough since $E\approx 2000$.If I'm right, then the whole of the problemset could be solved pretty easily with standard copy-pastable algorithms.
•  » » 11 days ago, # ^ |   0 Between witch nodes are you running min-cost-max-flow ?
•  » » » 10 days ago, # ^ |   0 I connect a source to the two root nodes, and I connect all devices to a sink. All edges have capacity one.
•  » » » » 10 days ago, # ^ |   0 If you pass $k>1$ units of flow on some edge then these edge have cost $k$ not $1$, so I think that your solution are wrong, you have implemented it?
•  » » 10 days ago, # ^ | ← Rev. 2 →   +6 My solution is related to maximum independent set. Consider each tree as a part in a bipartite graph with the vertices are its edges. Now if two edges from different trees cannot be removed simultaneously, connect a edge between them in the bipartite graph. Answer is the maximum independent set of the bipartite graph.
 » 10 days ago, # |   +3 when the editorial will be posted?
 » 10 days ago, # |   0 Is Problem A solvable with binary search? If yes, can anyone explain a bit :)
•  » » 10 days ago, # ^ |   0
 » 10 days ago, # |   0 I can't find the tutorial. I saw someone solved problem A with the following idea. sum <- r+g+b if the smallest two of r,g,b is smaller than the largest one ans = the sum of the smallest two else ans= (r+g+b)/2Can anyone prove the correctness of it mathematically?
•  » » 10 days ago, # ^ | ← Rev. 4 →   +4 Assume that the values are sorted $a \leq b \leq c$If $a + b < c$, then the optimal strategy is to take $a$ with $c$ until $a$ is gone, then take $b$ with $c$ until $b$ is gone. It is impossible to access the rest of the candies in $c$. Total number of moves = $a + b$.Otherwise, the optimal strategy is to take $a$ with $c$ until $c = b$, at which point $a := a - (c - b)$, then take $b$ with $c$ until $a = b = c$. Then, there are three sub-scenarios: $\geq 2$, in which case you can take $ab$, $bc$, $ac$ and decrease all of them by two, then repeat $= 1$, in which case you just take any two and leave a single piece, $= 0$, in which case you obviously stop Since the strategy for this scenario always leaves $0$ or $1$ candies, the number of steps is $\lfloor \dfrac {a + b + c} {2} \rfloor$.
 » 10 days ago, # |   0 I'm pretty new to Codeforces and competitive programming in general. Where do I find the editorials to the problems?
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 Editorial will be published, you will then see a seperate link for tutorials.
 » 10 days ago, # |   0 When will Editorials be updated ?
 » 10 days ago, # | ← Rev. 2 →   0 Why MCMF is wrong for F ? see some MCMF solution with same wrong answer on test 5. code
•  » » 10 days ago, # ^ |   0 I figured it out .I miss understood MCMF.
•  » » » 10 days ago, # ^ |   0 Hi, can you share why is it incorrect?
•  » » » » 10 days ago, # ^ |   +5 the cost of flow is flow multiply the the cost of this pipe .if a pipe with flow more than one the answer is not equal.
 » 10 days ago, # |   +13 I solved problem E in O(n) by six stacks.As we can see, for a regular bracket sequence, we can calculate depth of it by simply calculating the max prefix sum of bracket sequence by assume '(' for -1 and ')' for 1,else for 0.e.g"((0)())" can convert to 1 1 0 -1 1 -1 -1,and the prefix of it is 1 2 0 1 2 1 0,which the max value is 2 for the answer.However,we have to deal with the irregular bracket squence like ")(",because it should be output -1(for irregular) instead of 0,this can be solved by calculating the min value of ths prefix sum array.If it is a negative number, it must be a irregular sequence.Now we just need to deal with the problem by what we said before.We maintain two stacks for prefix sum,stack A for restoring from begin to current cursor,stack B for current cursor's next position to the end of the prefix array.We can see the each operation will only happen in the curosr's postion,so if the cursor move to the left,we just need to pop the top value of stack B to stack A,moving to right is same.e.g "((0) ())", space for separating. For stack A,it is [1,2,0,1]. For stack B, it is [1,2,1]**(looking from right to left,it is '))(')**.In the same way,we maintain two stacks for max prefix sum and two stacks for min prefix sum.Thus we can calculate the answer by these stacks just check the top value of prefix sum stack A and prefix sum stack B are the same and sure two min stacks's top value is >=0,if all the condition is true,the answer is the max of two max prefix stacks The code is here 66020705Sorry for my poor English >_<
 » 10 days ago, # |   +5 This contest is so great!!!
 » 10 days ago, # | ← Rev. 2 →   0 https://codeforces.com/contest/1263/submission/66026507 how could this problem got accepted ? it is giving wrong answer in this test case: 3 ab cd da output:2 ans:1
 » 10 days ago, # |   0 For me, A is still harder than B,C and D... It required more time than any other task for me... What's the idea behind solving it in one line?
•  » » 10 days ago, # ^ |   +3 a = [r,g,b] a.sort(reverse = True) ans = 0 if(a[0]>=a[1]+a[2]): ans = a[1]+a[2] else: ans = a[0] + (a[1]+a[2]-a[0])//2if the maximum of r,g,b is greater than the sum of the remaining two terms than the answer is sum of those two terms. else the answer will be maximum term + floor((extra sum of next max two terms)/2)
•  » » 10 days ago, # ^ |   0 Could you help me find a mistake in my code of Problem B... https://codeforces.com/contest/1263/submission/66032322
•  » » » 10 days ago, # ^ |   +1 Your code doesn't properly maintain the order of the PINs given in the input. It is appending the changed ones to the end of the list.
 » 10 days ago, # | ← Rev. 2 →   0 How to solve problem E using lazy segment tree? :)
•  » » 10 days ago, # ^ |   +18 lazily
 » 9 days ago, # |   0 The problem with problem D is still not fixed? There are still WA solutions out there having AC verdict. :/
•  » » 9 days ago, # ^ |   0 Verdict won't change as old submissions won't be rejudged even if some of them are hacked later. But new submissions will face stronger tests so WA solutions will probably not get AC now. See this blog
•  » » » 9 days ago, # ^ |   0 So, the contestants who submitted wrong solutions and still got AC, will still get the points?
 » 8 days ago, # |   0 Thanks for the contest!
 » 8 days ago, # |   0 It was fun participating! Thank you for the contest and the editorial!