### Artyom123's blog

By Artyom123, 15 months ago, translation,

We hope that you enjoyed the contest. Let's get right into the editorial:

A: Median Maximization
B: MIN-MEX Cut
C: MAX-MEX Cut
D: Seating Arrangements
E: Buds Re-hanging
F: Points Movement
G: Four Vertices
H: Xor-quiz
Who did what?

• +372

| Write comment?
 » 15 months ago, # |   +28 Thx for fast editorial
•  » » 14 months ago, # ^ |   0 Nice profile picture:)
 » 15 months ago, # |   +50 Thanks for the round and fast editorial.
 » 15 months ago, # |   +7 Fastest Editorial I've ever seen
 » 15 months ago, # | ← Rev. 2 →   -14 I can't read the condition!!! For task D2 , I thought that there are columns and rows that do not affect anything. Because of this, I did not solve the problem. OMG
•  » » 15 months ago, # ^ |   +5 that is why reading question is imp before solving it. :)
 » 15 months ago, # |   0 Got the logic for D2 but wasn't able to convert it to code :(
•  » » 15 months ago, # ^ |   0 solving lot of implementation questions helps! and generally it comes with time and consistency.
•  » » » 15 months ago, # ^ |   +2 Did i tell wrongly? Downvoters should comment the appropriate answer before degrading my answer.
 » 15 months ago, # |   +1 Feels bad to solve B and C but not A ):
 » 15 months ago, # |   +6 Thanks for the editorial. I noticed that the second solution for Problem A has the editorial for Problem B. It will be great if it can be rectified.
•  » » 15 months ago, # ^ |   0 Yes, thank you. It will be fixed soon.
 » 15 months ago, # |   +90 I think you over-killed F with seg-trees. it could be done with just one sort and the rest was O(n) dp.first remove all covered segments that have either a point or another segment inside them. then sort all segments and points.(compare segments by right ends with points). now let dp_i be answer for the first i things(segments and points together) and let pd_i be answer if we force that after our operations, we have a point in the position X_i.(if the i'th thing is a point X_i is its position otherwise its the segment's leftpoint) you can see details of updating the table in my submission.128662794(its very messy cause I finnished debugging in last minute of the contest)
•  » » 15 months ago, # ^ |   +33 I have something similar with just a sort and O(n) dp.First keep only useful segments and assign them to the point on their right. Then for each point, we want to calculate dp[i][c], which is the minimal cost to cover all segments on the left of point i if the point i travels to the left c times (c = 1 or 2). Either point i goes to the left, then comes back and goes to the right, or vice versa.Then to go from point i to i + 1, there are (k + 1) ways to split the k intervals between them, and for each of them there are 4 transitions. Finally, the answer is just dp[n] (we add a point with position +inf at the start).You can see my submission here 128653517
•  » » 15 months ago, # ^ | ← Rev. 3 →   +21 Code is good, but logic description would be better.I have also O(n) dp without trees. I did check point coverage by binary search, then removed overlapping segments using simple sort and stack. Additional observation is that you don't need to move point over any previous point initial position. So dp[i][j] was where dp[i+1][j] would tell how much we need to move points [0,i] to cover everything up to point i would be visited and j segments in between point i and i+1 exactly visited by point i. So dp[2][1] would tell how much should we move points 0 and 1 such that every segment up to point 1 would be visited and exactly single segment between points 1 and 2 would be visited by point 1. For each j I did brute force how far we should go left and then rearranged it a bit and noticed fact that we actually pick one of two choices for each j. 128674186 (commented part is brute force version).
•  » » 14 months ago, # ^ |   0 the author's approach to finding segments that don't contain other segments might also be overkill. If we consider all segments in decreasing order of L then we can just maintain the min r[j] we've met so far. When considering {l[i], r[i]}-> this segment contains another segments if (min r[j]) <=r[i];I'm not really sure why the author decided to use Fenwick trees here
•  » » 13 months ago, # ^ |   0 Nice Approach
 » 15 months ago, # |   +1 This was a nice round. For the first time I solved more than 2 problems of a global round. Could have solve D2 also, but the implementation was beyond me....
 » 15 months ago, # | ← Rev. 2 →   +10 For E, Can anyone explain why Sum of Leaves + Sum of Buds = n — 1? Precisely, why this holds true? Initially, there are n - k - 1 leaves (total amount of nodes — the amount of buds — root) 
•  » » 15 months ago, # ^ |   +3 Because if initially a node is neither a bud nor a leaf, when you remove all the buds under this node, it becomes either a bud or a leaf (doesn't apply to the root).
 » 15 months ago, # |   +1 Constraints in D should've been stricter IMHO
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 I instinctively went straight to ordered multiset (happy that I would finally use this thing in a contest) to achieve $O(nmlog(m))$ but yeah, I didn't notice that $O(nm^2)$ fits.
•  » » 15 months ago, # ^ |   0 I completely agree. I myself used the Fenwick tree, not noticing that the constraints allow us to solve for a square.
•  » » 15 months ago, # ^ |   +54 I strongly disagree — the problem is nice in its current state, increasing constraints just unnecessarily adds some data structure work on top of that.In my opinion adding data structures is usually justifiable if its easier than the actual ad-hoc part of the problem. Even a fenwick tree (or any other easy method of inversions) is way tougher than the observations needed in D1, maybe even D2.
•  » » » 15 months ago, # ^ |   +35 In my opinion, counting inversion is actually easier (or more straightforward) than the construction part. Still, I agree with you that it adds no value to the problem.
•  » » » » 15 months ago, # ^ | ← Rev. 3 →   +4 I see your point, but I'd argue its more standard, not easier. It still requires someone to know Fenwick / pbds / merge sort trick. This is most likely trivial for anyone 17-1800 or higher as they've likely encountered the idea before. However I suspect there are a lot of participants in the 14-1600 range who could make the observations for D1/D2 but don't know any of the standard methods for inversions. I certainly didn't till I was 16-1700.
•  » » » » » 15 months ago, # ^ |   0 Some knows, some don't. With this logic "there are some people who don't know these alg/ds" you could cut them out from any problem.Your argument makes sense, but I think you underestimate what people know. Pretty sure half the cyans know about Fenwick/Segtree nowadays and would be happy to practice them
•  » » » 15 months ago, # ^ |   0 Ya your point is fine increasing constraints force the participants to use data structures like fenwik tree/segment-tree but in my opinion this has a positive outcome,If the participant couldn't solve the problem during the contest due to lack of data structure knowledge but it enables them to learn these data structures after the contest and then try to solve it again that's what upsolving all about. Having knowledge of more data structures always helps :)).
•  » » 15 months ago, # ^ |   0 Ya I did it in O(nmlogm) by counting inversion with divide and conquer whereas my friend got also got passes with naive O(nm^2) algo.T_T
 » 15 months ago, # | ← Rev. 2 →   -52 I recently encountered a problem during the contest. I don't know if it's a bug or a Codeforces thing. The problem is, if I give two correct submissions for the same problem, my last correct submission is taken into account for my points distribution. I think that logically, the first correct submission for the problem should be taken into account. I solved D1 first, and then, D2. After which, I submitted the solution for D2 in D1 also, due to which I lost half of the points of that question. So, it didn't matter if I got AC for D1 long ago, I got considerably low points .
•  » » 15 months ago, # ^ |   +33 Not a bug, part of the rules. You might want to resubmit a problem if you think it won't pass sys tests or it will get hacked.
 » 15 months ago, # | ← Rev. 2 →   +6 Thanks for the great round!
 » 15 months ago, # |   0 Really liked the question. This contest was really competitive, with people solving questions at high speed. And liked the editorial(the idea of giving hints first).ThankYou
 » 15 months ago, # |   +14 I like this kind of editorial with spoiler hints
 » 15 months ago, # |   0 thx for good and fast editorial!
•  » » 15 months ago, # ^ |   0 unfortunately you still slow..
 » 15 months ago, # |   0 Didn't notice O(nm^2) fits into the solution.Was thinking of something else. Thanks for the round and a pretty fast editorial!
 » 15 months ago, # |   +51 Thanks for the great contest! Unfortunately, I think I saw problem G somewhere.
 » 15 months ago, # | ← Rev. 3 →   +8 Is there meant to be special-casing for $C \in \{3,6,7,15,23,43\}$ in problem H? For these values, the number of square-free integers in $[1..C]$ is strictly greater than $\lceil 0.65 \cdot C \rceil$, which Hint 2 suggests is impossible.EDIT: Whoops! I just noticed the unusual constraint $C \geq 100$, which is important for this reason.EDIT2: But in light of this, I don't understand the problem-setting reasoning behind making the problem interactive at all. Was it originally intended to be an easier problem?
 » 15 months ago, # | ← Rev. 2 →   +33 Why there are 700+ test cases for G... XD
•  » » 15 months ago, # ^ |   +6 Because author wanted to break Radewoosh's solution(random)
•  » » 15 months ago, # ^ |   +69 .
•  » » 15 months ago, # ^ |   +20 .
•  » » 15 months ago, # ^ |   +7 .
 » 15 months ago, # |   -9 Weak pretests on problem D2
•  » » 15 months ago, # ^ |   +62 your solution is weaker
 » 15 months ago, # |   +82 My G (the case with two edges without common endpoints):Paint each vertices in one of $c$ colors (I've chosen $c=5$). Now for each edge we know a pair $(a, b)$ ($1 \leq a \leq b \leq c$) which denotes the colors of it's endpoints. If for two edges and their pairs $(a, b)$ and $(x, y)$ each of $a \neq x$, $a \neq y$, $b \neq x$ and $b \neq y$ holds, then we know for sure that these edges have no common endpoints.For each pair maintain a multiset of edge values (and the largest one of them) and iterate over a pair of pairs. Then, we can with probability around $0.416$ (for $c=5$) find a correct answer. Do as many iterations as you can fit in the time limit.My H:Also gaussian eliminations for each group to find any solution. To find a solution with correct $n$, use hill climbing.
 » 15 months ago, # |   0 Chinese universe students with a morning lesson cryyyyy.
 » 15 months ago, # |   0 Thanks for such a good round and fast editorial
 » 15 months ago, # | ← Rev. 2 →   0 So in reality the $\lceil 0.65 n \rceil$ can be replaced with the number of squarefree numbers smaller than $n$? (in H)
 » 15 months ago, # |   0 After looking at the constraints again, Order Statistic Tree seems like an overkill for D1 and D2. My Submission
 » 15 months ago, # |   +1
 » 15 months ago, # |   +1 I think that the input in D2 is not easy to understand &_&
 » 15 months ago, # |   0 why not every contest tutorials are like this .. very well written tutorial and solution code thanks !
 » 15 months ago, # |   0 Help() Pleasehttps://codeforces.com/contest/1566/submission/128700326Here is my submission i'm trying to solve D1 with help of PBDA where the heck i'm wrong : ( Could'nt find any counter test case why I'm getting WA on Test Case 2
 » 15 months ago, # | ← Rev. 3 →   0 Merge Sort inversion cnt on D2: https://codeforces.com/contest/1566/submission/128722549
•  » » 15 months ago, # ^ |   0 128636145 is what I did in-contest (merge sort to count inversions).
 » 15 months ago, # |   +62 The first hint in problem E is incorrect, and here's a counter-example:  1 / \ 2 3 \ 4 / \ 5 6 Re-hanging 4 (bud) to 2 (leaf) won't decrease the number of leaves.
•  » » 15 months ago, # ^ |   0 Can you explain how answer is 2 in the third test case. I think it should be 3
 » 15 months ago, # | ← Rev. 4 →   0 shouldn't it be min instead of max? as we need here the ending index (j) of the second last segment? Or I am getting it wrong? Here is my accepted solution using the given idea but using min : 128769652
 » 15 months ago, # | ← Rev. 2 →   0 128624993 why I am getting tle on Question c although my solution is of O(1e5) and editorial of d2 which is of O(1e8) is still running.
 » 15 months ago, # |   0 I am unable to get how having a leaf connected with root will always reduce the size. Can anyone explain in detail for the third test case given in the question.
 » 15 months ago, # |   0 Problem D can actually be solved in O(n*m*log(m)) by using an ordered set to calculate the inconvenience of a person in log(m). Here is my solution using Policy Based DS in cpp.
 » 15 months ago, # |   0 So Fast!
 » 15 months ago, # |   +1 I think the difference in difficulty between E and F is too large.
 » 15 months ago, # |   0 I have a problem about PROBLEM B, 0002000 ,i think it ouput 1,but std output 2. Maybe I misunderstand the problem?
•  » » 15 months ago, # ^ |   0 I am sorry to make a stupid question, i have solve the problem:)
 » 14 months ago, # |   0 thanks for having a pictorial explanation of test cases...
 » 10 months ago, # |   0 Why this code of Problem C shows TLE on tests 2 ? It just used a for loop.
 » 10 months ago, # |   0 Test cases for D1 are way too weak.They only consider number of rows to be one. i passed the test cases with this trivial solution 145664036
 » 10 months ago, # |   0 thanks