### Artyom123's blog

By Artyom123, 3 years 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?
 » 3 years ago, # |   +28 Thx for fast editorial
•  » » 3 years ago, # ^ |   0 Nice profile picture:)
 » 3 years ago, # |   +50 Thanks for the round and fast editorial.
 » 3 years ago, # |   +7 Fastest Editorial I've ever seen
 » 3 years 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
•  » » 3 years ago, # ^ |   +5 that is why reading question is imp before solving it. :)
 » 3 years ago, # |   0 Got the logic for D2 but wasn't able to convert it to code :(
•  » » 3 years ago, # ^ |   0 solving lot of implementation questions helps! and generally it comes with time and consistency.
•  » » » 3 years ago, # ^ |   +2 Did i tell wrongly? Downvoters should comment the appropriate answer before degrading my answer.
 » 3 years ago, # |   +1 Feels bad to solve B and C but not A ):
 » 3 years 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.
•  » » 3 years ago, # ^ |   0 Yes, thank you. It will be fixed soon.
 » 3 years 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)
•  » » 3 years 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
•  » » 3 years 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).
•  » » 3 years 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
•  » » 2 years ago, # ^ |   0 Nice Approach
 » 3 years 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....
 » 3 years 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) 
•  » » 3 years 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).
 » 3 years ago, # |   +1 Constraints in D should've been stricter IMHO
•  » » 3 years 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.
•  » » 3 years ago, # ^ |   0 I completely agree. I myself used the Fenwick tree, not noticing that the constraints allow us to solve for a square.
•  » » 3 years 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.
•  » » » 3 years 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.
•  » » » » 3 years 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.
•  » » » » » 3 years 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
•  » » » 3 years 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 :)).
•  » » 3 years 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
 » 3 years 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 .
•  » » 3 years 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.
 » 3 years ago, # | ← Rev. 2 →   +6 Thanks for the great round!
 » 3 years 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
 » 3 years ago, # |   +14 I like this kind of editorial with spoiler hints
 » 3 years ago, # |   0 thx for good and fast editorial!
•  » » 3 years ago, # ^ |   0 unfortunately you still slow..
 » 3 years 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!
 » 3 years ago, # |   +51 Thanks for the great contest! Unfortunately, I think I saw problem G somewhere.
 » 3 years 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?
 » 3 years ago, # | ← Rev. 2 →   +33 Why there are 700+ test cases for G... XD
•  » » 3 years ago, # ^ |   +6 Because author wanted to break Radewoosh's solution(random)
•  » » 3 years ago, # ^ |   +69 .
•  » » 3 years ago, # ^ |   +20 .
•  » » 3 years ago, # ^ |   +7 .
 » 3 years ago, # |   -9 Weak pretests on problem D2
•  » » 3 years ago, # ^ |   +62 your solution is weaker
 » 3 years 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.
 » 3 years ago, # |   0 Chinese universe students with a morning lesson cryyyyy.
 » 3 years ago, # |   0 Thanks for such a good round and fast editorial
 » 3 years 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)
 » 3 years ago, # |   0 After looking at the constraints again, Order Statistic Tree seems like an overkill for D1 and D2. My Submission
 » 3 years ago, # |   +1
 » 3 years ago, # |   +1 I think that the input in D2 is not easy to understand &_&
 » 3 years ago, # |   0 why not every contest tutorials are like this .. very well written tutorial and solution code thanks !
 » 3 years 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
 » 3 years ago, # | ← Rev. 3 →   0 Merge Sort inversion cnt on D2: https://codeforces.com/contest/1566/submission/128722549
•  » » 3 years ago, # ^ |   0 128636145 is what I did in-contest (merge sort to count inversions).
 » 3 years 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.
•  » » 3 years ago, # ^ |   0 Can you explain how answer is 2 in the third test case. I think it should be 3
 » 3 years 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
 » 3 years 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.
 » 3 years 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.
 » 3 years 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.
 » 3 years ago, # |   0 So Fast!
 » 3 years ago, # |   +1 I think the difference in difficulty between E and F is too large.
 » 3 years ago, # |   0 For problem E, why we are subtracting 2*k, it is not clear to me. Can someone expalin?
 » 3 years ago, # |   0 I have a problem about PROBLEM B, 0002000 ,i think it ouput 1,but std output 2. Maybe I misunderstand the problem?
•  » » 3 years ago, # ^ |   0 I am sorry to make a stupid question, i have solve the problem:)
 » 3 years ago, # |   0 thanks for having a pictorial explanation of test cases...
 » 7 months ago, # |   0 Thanks for this editorial.However, I am not sure if it is a mistake or just because I am a beginner in English so I can not get it correctly.In the paragraph of the editorial of Question A, a sentence goes '..., which sums should be n ...', but the variable n is used to describe the length of given array, and the s is used to describe the sum of all elements of the array.Therefore, I think it might be '..., which sums should be s ...'.If I am wrong, please remark me and point the mistake out, thanks.