### Flamire's blog

By Flamire, history, 4 weeks ago,

2002A — Distanced Coloring

idea & solution: xcyle

Hint 1
Hint 2
Tutorial
Solution

2002B — Removals Game

idea & solution: xcyle

Hint
Tutorial
Solution

2002C — Black Circles

idea: Flamire, solution: le0n

Hint
Tutorial
Solution

idea & solution: xcyle

Hint
Tutorial
Solution (Check 1)
Solution (Check 2, LipArcanjo)

2002E — Cosmic Rays

idea: le0n, solution: Flamire

Hint 1
Hint 2
Tutorial
Solution
Solution (priority_queue)

2002F1 — Court Blue (Easy Version)

idea: Flamire, solution: le0n

Hint 1
Hint 2
Tutorial
Solution

2002F2 — Court Blue (Hard Version)

idea: le0n, solution: xcyle

Hint
Hint (alternate version)
Tutorial
Solution
Solution (dfs)

2002G — Lattice Optimizing

idea & solution: xcyle

We apologize for unintended solutions passing, and intended solutions failing with large constants. Brute force runs very fast on $n=18$, which forced us to increase constraints.

Hint 1
Hint 2
Tutorial
Solution
Solution (trie, LipArcanjo)

2002H — Counting 101

idea: le0n, xcyle, solution: le0n, xcyle

Hint 1
Hint 2
Hint 3
Tutorial
Solution (orzdevinwang)
• +125

 » 4 weeks ago, # |   +15 Woah, I solved A,B,C all through guessing and became purple!
•  » » 4 weeks ago, # ^ |   0 You really solved E first... :skull:
•  » » » 4 weeks ago, # ^ |   0 I got stuck for an hour trying to prove the earlier problems XD
•  » » 4 weeks ago, # ^ |   +2 I created video editorial for E: Cosmic Rays.
 » 4 weeks ago, # |   -15 Why this solution of mine for C is giving WA on test5? 275844339
•  » » 4 weeks ago, # ^ |   +6 Check for integer overflow sqrt can cause precision loss, i recommend you eliminate it completely
•  » » » 4 weeks ago, # ^ |   0 how will we check then?My approach : If after distance(d) time, if our destination points becomes part of any of the circle then the answer is NO otherwise YES.
•  » » » » 4 weeks ago, # ^ |   0 you can just compare the squared distance, you end up squaring it again after taking the square root anyways
•  » » » » » 4 weeks ago, # ^ |   0 thank you! it worked :)by the way, just want to understand how to identify such things?
•  » » » » » 4 weeks ago, # ^ |   0 For me, I used long double in C++ and it worked.
 » 4 weeks ago, # | ← Rev. 2 →   +5 lol, you can solve D1 in $O(N*Q)$ with pragmas: 275797240Also you can use segment tree too for E: 275831791
•  » » 4 weeks ago, # ^ |   0 I also tried spamming pragmas but I got TLE on pretest 13 :) https://mirror.codeforces.com/contest/2002/submission/275836926
•  » » 4 weeks ago, # ^ |   0 diko hacked it. Thanks
•  » » 4 weeks ago, # ^ |   +8 I solved E using stack, I think E is much easier than D1, D2 took me only 15 mins to solve E. https://mirror.codeforces.com/contest/2002/submission/276392625
 » 4 weeks ago, # |   0 Can someone try hacking my solution to E? I solve for each value separately and use RMQ to keep track of merging blocks, but I believe my code is O(N^2 log N) if one value appears lots of times, the first and last occurrence of that value have high a_i, and all intermediate occurrences have very low a_i. 275860315
 » 4 weeks ago, # |   -29 Only solve A, B.I am too weak. T^T
 » 4 weeks ago, # |   +1 In problem D2 check 1, can someone explain how the merge step works? ("merge the subtree of u into a large node with size siz_u") I don't understand why it is sufficient to just maintain "bad" children, instead of maintaining information for the entire subtree.
•  » » 4 weeks ago, # ^ |   +2 Let's note the following $pos_x$ : position of $x$ in $p$$sub_x$ subtree size of xFor D1 consider some node $x$ , we call node $x$ valid if the positions of its children in the permutation are ${pos_x +1 , pos_x + t + 1}$ where t is the subtree size of one of the children.A dfs order is valid iff all nodes are valid and $p_1 = 1$So we can maintain a set for bad nodes $bad$ When we swap two values $p_x , p_y$ it only affects $p_x , p_y$ and their parents (because $pos_{p_x}$ becomes $y$ and vice versa)So we can check easily in D1For D2 you should maintain a set {$pos_{child} , child$} for each node $x$ . Node $x$ is valid iff (*) for each two adjacent positions of children $c_i$ , $c_{i+1}$ in the set $pos_{c_{i+1}} - pos_{c_i} = sub_{c_i}$ and $pos_{c_1} - pos_x = 1$ Thus we can maintain also a set of bad children (who don't satisfy (*)) in each node And when we update we only remove and insert new values in the setFinally if the set of bad children of a node is empty than erase this node from $bad$ otherwise insert it.
•  » » » 4 weeks ago, # ^ |   0 Thanks! While going through others' implementations I discovered that Um_nik's submission implements this idea nicely.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I suppose, this part is just about proving that subtree dfs log places next to the parent node dfs log. So there's no merging part when talking about solution.Actually, I don't understand how to keep tracking "bad" nodes with sets on D2. I would be glad if someone would explain this part. Can't understand author's code ideas.P.S.: Sorry, don't refresh the page too long , thaks for explaining!
 » 4 weeks ago, # |   0 the image in c's tutorial is not visible
 » 4 weeks ago, # | ← Rev. 3 →   +1 Why this solution of mine for D1 is giving TLE on test9 and it's O(n*q)? My Solution
•  » » 4 weeks ago, # ^ |   +5 Because n*q is too big
•  » » » 4 weeks ago, # ^ |   0 i thought that too, but i asked bcos i see people saying they solved it in O(n * q)
 » 4 weeks ago, # |   0 I am really dumb .But Why CD = AD in tutorial of C . I don't understand thatcould anyone explain that pls.
•  » » 4 weeks ago, # ^ |   0 I think that CD = AD represent the point where we intersect with a circle since our starting point A has the same distance to D as does the circle's center C.
•  » » 4 weeks ago, # ^ |   0 understand it in a way that the speed of expansion of circles is same as walking speed of the guy and thus the circles radius at any instant would be same as the distance covered by the guy till that instant which implies AD=CD
 » 4 weeks ago, # | ← Rev. 5 →   +3 Alternative (possibly wrong?) solution for D2: Firstly, check that for each $i$ from $2$ to $n$ $p_{i - 1}$ is the parent of $p_i$ except the case when $p_{i - 1}$ is a leaf. Also check that for each $i$ the position of $i$ in $p$ is greater than the position of its parent. Check that the multiset $S = \{ LCA(p_1, p_2), LCA(p_2, p_3), \cdots, LCA(p_{n - 1}, p_n) \}$ matches with such multiset of any valid DFS order (intuition: virtual trees). It can be easily checked by maintaining the multiset hash. Here is my implementation: 275842859. Feel free to uphack it.UPD. It seems that the second condition is unnecessary: 275927827. Now my solution looks similar to the Check 2 in the editorial as songhongyi pointed below (thanks for it). I think the first condition is a "weaker" version of Check 2 and the third condition makes my solution work somehow by making the first one "stronger". I still don't know how to prove it though.UPD 2. Actually the second condition is necessary but the first one isn't. Now it seems less similar to Check 2.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 This solution is very similar to check2. I suspect it's correct and should be provable in a similar way. Factle0n failed to hack it so it must be true.
•  » » 4 weeks ago, # ^ |   +8 The check2 is actually equivalent to $p_1=1$ and $\operatorname{LCA}(p_i,p_{i+1})=fa(p_{i+1})$ forall $1\le i\le n$. Your third condition is actually $\{ {\operatorname{LCA}(p_i,p_{i+1})} \} =\{fa(p_{i+1})\}$, which is obviously weaker than check2. But I'm sure it is equivalent to check2 with your second condition.
 » 4 weeks ago, # |   0 Could anyone write out the proof by induction in B? I'm not sure how to prove it...
•  » » 4 weeks ago, # ^ |   +5 I didn't really understand the subarray thing in the editorial. The way I see it is:Suppose Bob can mimic Alice's move when there are $n$ elements. There are only two ways for this to happen (let $A = a_1 \dots a_n$, $B = b_1 \dots b_n$): We have $a_1 = b_1$ and $a_n = b_n$. If Alice takes $a_1$ Bob can take the same element, i.e., $b_1$. If Alice takes $a_n$ Bob can take $b_n$. We have $a_1 = b_n$ and $a_n = b_1$. If Alice takes $a_1$ Bob can take the same element, i.e., $b_n$. If Alice takes $a_n$ Bob can take $b_1$. If any of the above cases happen, nothing has changed in the game and we keep going, now with $n-1$ elements.If at any moment none of the cases above match, it means Alice has at least one endpoint element which Bob does not (let it be $x$). Bob cannot pick $x$ right after Alice, so he takes any one of his endpoint elements (let it be $y \neq x$). Now Alice can easily win by picking all her left elements except $y$, because at the end of the game, Alice will have $y$ left but Bob already deleted it, so the last elements cannot be equal.If the game keeps going with one of the two cases described initially, Bob can always mimic Alice's move, so Alice cannot win. These two cases can only happen when the whole arrays $A$ and $B$ are equal or one is the reverse of the other.
•  » » » 4 weeks ago, # ^ |   0 Thank you so much!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I wish they had elaborated why the interval condition was "intuitive to see".Here is my proof. If there is a pair of neighbors in array A that are not neighbors in B then Alice wins. She just needs to remove the elements until only those two elements remain. Then after Bob's move his remaining two elements would not be the same as the two Alice's elements, and on the following move Alice can leave an element that Bob does not have. So, for Bob to win every pair of neighbors in A need to be neighbors in B. It is easy to show that it can only happen if B is equal to A or its reverse, depending on the order in B of the first two elements of A.
 » 4 weeks ago, # |   +14 What is $fa$ mentioned in Problem-D Check 2? Ref$fa(p_{i+1})$ must be ancestor of $p_i$.
•  » » 4 weeks ago, # ^ |   +2 the father(parent) of $p_{i+1}$ on the tree.
 » 4 weeks ago, # | ← Rev. 2 →   +6 My Insights for A,B,C AObserved that answer is $\min(n,k) \cdot \min(m,k)$ Cases ObservationInput Output ----- ------ 3 3 2 4 =(2*2)=k*k 5 1 10000 5 =(1*5)=n*m 7 3 4 12=(4*3)=m*k 3 2 7 6=(2*3)=n*m 8 9 6 36=(6*6)=k*k 2 5 4 8=(2*4)=n*k Total complexity is $\mathcal{O}(1)$ Codefrom math import * def solve(): n,m,k=map(int,input().split()) print(min(n,k)*min(m,k)) for _ in range(int(input())): solve()  BSince We're performing optimally we'll keep removing from left or right thus $\displaystyle [ \color{red}{a_1,a_2,.....,} \color{blue}{a_{n/2}} \color{red}{,....,a_n} \color{black}]$ $\displaystyle [ \color{red}{b_1,b_2,.....,} \color{blue}{b_{n/2}} \color{red}{,....,b_n} \color{black}]$Thus Bob can win only and only if $a$ is the same as $b$ or $a=b^{-1}$ i.e. $b$ reversed.Total complexity is $\mathcal{O}(n)$ Codefrom math import * def solve(): n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) if(a==b or a==b[::-1]): print("Bob") else: print("Alice") for _ in range(int(input())): solve()  CThe $mindist$ that is possible is $\min_{i=1}^n \sqrt{x_i^2+y_i^2}$ overall points , and the distance needed to connect $(x_s,y_s)$ and $(x_t,y_t)$ is $\sqrt{(x_s-x_t)^2+(y_s-y_t)^2}$ , let's call it $d$ , we must have $\text{mindist} \le d$ so that it's possible to connect $(x_s,y_s)$ and $(x_t,y_t)$ without intersection of circles.Don't use square root for avoiding square root errors , it's enough to store $(\Delta x)^2+(\Delta y)^2$Total complexity is $\mathcal{O}(n)$ Codefrom math import * def solve(): md=float('inf') n=int(input()) p=[] for i in range(n): x,y=map(int,input().split()) p.append([x,y]) x1,y1,x2,y2=map(int,input().split()) for a,b in p: d=(a-x2)**2+(b-y2)**2 md=min(md,d) sd=(x1-x2)**2+(y1-y2)**2 if(md<=sd): print("NO") else: print("YES") for _ in range(int(input())): solve()  Fun FactI didn't solve any of BC without guessing (I proved them) ; If I guessed them then specialist was in hand for real.
•  » » 4 weeks ago, # ^ |   0 How did you come up with the conclusion of A? I turn to solve B/C instead.
•  » » » 4 weeks ago, # ^ |   0 I tried to come up with something related about multiplication of numbers You can see the cases like this Cases ObservationInput Output ----- ------ 3 3 2 4 =(2*2)=k*k 5 1 10000 5 =(1*5)=n*m 7 3 4 12=(4*3)=m*k 3 2 7 6=(2*3)=n*m 8 9 6 36=(6*6)=k*k 2 5 4 8=(2*4)=n*k I think the observing the thing described in the spoiler is enough to come up with $\displaystyle \min(n,k) \times \min(m,k)$
•  » » » » 4 weeks ago, # ^ |   0 smart!
 » 4 weeks ago, # | ← Rev. 4 →   0 My idea for D1 was that it looks like a segment tree: Store in each node if that subtree makes sense or not, and the maximum index in that subtree, and of course the index of the node in the permutation. Then on update query, it takes at most O(log n) updates like a segment tree, by moving up and calling combine function on the 2 children of the current node until reaching root. Then the root has the answer, by just checking if it makes sense. Combine function: to get maximum index just max the maximum index of both children and your index, to see if it makes sense one of the children's index must be 1 more than the node's index, and then the other's index must be 1 more than the maximum index of the first child so it forms a dfs order that makes sense, and of course both subtrees must make sense (AND them together). Time complexity: O(n + q log n)
 » 4 weeks ago, # |   +4 In D check 1 the editorial specifies this condition: For every $u$, all of its children $v$ satisfy $[pos_v, pos_v+siz_v-1] \in [pos_u, pos_u+siz_u-1]$ In the code solution, a different, easier check is made: int chk(int x) { return son[x].empty() ? 1 : (q[x] < *son[x].begin() && *--son[x].end() + siz[p[*--son[x].end()]] <= q[x] + siz[x]); } Here son[x] includes ordered indices of $x$'s children in the permutation. Therefore, it is only checking the editorial condition for the furthest child in the permutation, and that the closest child in the permutation has an index not less than the one $x$ itself has. Can someone explain how these conditions are equivalent to the editorial? In fact I tried to check the editorial condition directly in my code but got TLE probably due to constant factor.
•  » » 4 weeks ago, # ^ |   0 editorial should have cared to explain that. Nevertheless, here we go. Lets prove it for any node $u$. Assume that condition is satisfied for all immediate children $v$ of $u$. it means, for any immediate child $v$ of $u$, the range $[posv,posv+sizv−1]$ will contain whole subtree of $v$, and nothing else. So, the point is, for any two immediate child $v1$ and $v2$, their range is non intersecting. ($[posv1,posv1+sizv1−1]$ & $[posv2,posv2+sizv2−1]$). If the ranges are non intersecting, then we can just check the first and last range, and if they are contained within $[posu,posu+sizu−1]$, then all other are forced to contain within it.
•  » » » 4 weeks ago, # ^ |   0 Please correct me if I'm wrong, but I think you're only proving one side of the equivalence, namely editorial check implies code check. In fact we would be more interested in the other implication ( code check implies editorial check ), since the code check at first glance looks like a weaker condition. That is, for a single node it doesn't make much sense for the checks to be equivalent, but rather the fact that this weaker check works for all nodes at the same time might be what actually makes it equivalent.
•  » » » » 4 weeks ago, # ^ |   +3 May be, I should have also cared to explain more., I didnt prove editorial check implies code check, that is noobest thing i can comment. what I have proved above?Given that code check is satisfied for any $u$, and all nodes in its subtree, then it implies that Exactly all nodes in subtree of u are within [posu,posu+sizu−1], and nothing else. And this is not just for u, but also for all nodes in subtree of u. Which also equivalent to editorial check. How I have proved that?By induction. Lets say code check is satisfied for all nodes in subtree of $u$, except $u$, we didnt check for $u$ yet. So we assume that for each immediate child $v$ of $u$, all nodes in their subtree are within $[posv,posv+sizv−1]$, and nothing else. which means each of those ranges by immediate child of $u$ are non intersecting and continous. This is the key part. Now we are coming for $u$, Say $vl$ as leftmost position having $v$ out of all immediate child of $u$ and $vr$ as rightmost. And if $posvl$ and $posvr+sizvr-1$ are within $[posu,posu+sizu−1]$, then it indirectly implies that all other $[posvm,posvm+sizvm−1]$ are also within the $u$ range, as $posvl$ <= Unable to parse markup [type=CF_MATHJAX] <= $posvr$ and $posvm+sizvm-1$ cant intersect and cross the $vr$. Now, due to size constraint, if all $v$ ranges are within $[posu,posu+sizu−1]$, it means they are completely filling the range $[posu,posu+sizu−1]$ and nothing else can be inside it.By, induction this will propagate until root node. editorial checkchecking for all immediate child $v$ of $u$, whether $[posv,posv+sizv−1]$ contained within $[posu,posu+sizu−1]$ code checkchecking only for first and last $v$.
•  » » » » » 4 weeks ago, # ^ |   +3 Ok I guess I didn't understand the induction right. I got it now. Thank you!
 » 4 weeks ago, # |   -8 How is F2 harder than F1? I don't see any difference, only tighter time limits maybe. Can someone explain why F2 is considered harder than F1?
 » 4 weeks ago, # | ← Rev. 3 →   0 Quoting editorial for D2: Then, for each pair of adjacent elements $p_i,p_{i+1}$, $fa(p_{i+1})$ must be an ancestor of $p_i$ Can you tell me what does the notion $fa(p_{i+1})$ mean? I don't think I have seen it being declared anywhere in the tutorial. Thank you in advance.
•  » » 4 weeks ago, # ^ |   +4 It means the father of $p_{i+1}$. Apparently it's not as widespread as I thought. I've added an explanation.
•  » » » 4 weeks ago, # ^ |   0 I see, thanks.
 » 4 weeks ago, # |   0 Can anybody explain the proof for C? I get the part where CD = AD and the CD > CB-DB part, but everything else kinda just falls apart... I've forgotten everything about proofs from geometry class
•  » » 3 weeks ago, # ^ |   0 I can't understand this proof either, but if you look at the conclusion directly, it will be obvious that if the distance from the center of the circle to the target is less than or equal to the distance from the starting point to the target, it is obvious that the boundary of the circle will be touched before (and when you reach this point).
 » 4 weeks ago, # |   0 Solved ABCD1 and became specialist.
 » 4 weeks ago, # | ← Rev. 3 →   0 what does this line mean in editorial of $H$? Let b_i be the number of operations that has the element equal to v after block y_i as its center I couldn't understand the rest of the editorial because of that
 » 4 weeks ago, # |   0 WOW!You are very good! But could you give me some exegesis in the H code?
 » 4 weeks ago, # |   +3 why was E placed after D?
•  » » 4 weeks ago, # ^ |   0 https://mirror.codeforces.com/blog/entry/132346?#comment-1182297D1 is much easier than E, D2 is also not much harder imo but D1 is sufficient reason anyways
•  » » » 4 weeks ago, # ^ |   0 but shouldn't the point sums be nondecreasing? just by convention maybe there's definitely been instances where F1 is easier than E and such
 » 4 weeks ago, # | ← Rev. 3 →   +1 for the following test case for D2, 1 7 2 1 1 7 2 3 3 1 3 7 4 6 2 5 3 5 5 3 check 1 outputs NO NO but check 2 (and other ACs) output NO YES and i think it should be NO YES. the way siz is calculated in check 1 makes siz[1] = 6 and siz[3] = 3 but shouldn't they be siz[1] = 7 and siz[3] = 4?Edit: nvm the constraint ai < i is not satisfied for this tree so it's a wrong tc
•  » » 4 weeks ago, # ^ |   0 $1 \le a_i \lt i$, but in your case $a_3 = 7$ so it's invalid.
 » 4 weeks ago, # |   0 Solution 3 in problem F2 is interesting. Despite $L = 50$ is already hacked, higher $L$ should still yield an AC (with the cost of praying that one's code wouldn't TLE).A loose upperbound by me, with $L = 125$: 276065570I wonder how far could the uphack raise up "cheeseable" lowerbound value for $L$.
 » 4 weeks ago, # |   0 Could anyone explain how we are supposed to preprocess GCD as mentioned in F1 solution?
•  » » 3 weeks ago, # ^ |   0 I didn't preprocess GCD, my solution got passed
•  » » » 3 weeks ago, # ^ |   +8 My F1 also passed using the normal one. But for F2, I had to use custom binary gcd function (which I copied from one of the CF blogs). That's why I asked if it was possible to preprocess the gcd and then find them in constant time. It will be a huge optimization, nearly 20 times for the given constraints.
 » 4 weeks ago, # |   +14 For problem D, the following check is also sufficient: for every $i$ : $lca(p[i-1], p[i]) = parent(p[i])$
•  » » 4 weeks ago, # ^ |   +12 It's just check2 written in another form.
•  » » 4 weeks ago, # ^ |   +3 Hey, can you explain me how can I use segment tree to solve the problem D2. The authors solution mentions that we can impose some check on each node in the permutation.Specifically, For every u, all of its children v satisfies $[pos_v, pos_v + siz_v-1] \subseteq [pos_u, pos_u + siz_u-1]$And, we can maintain this check by keeping track of the number of u which violates this condition, and check for each u using sets.First of all, how can we do this using sets, and how can we do this using segment tree. I tried thinking a lot, but I could only think of maintaining a segment tree using dfs entry time. So each segment node in the segment tree contains a set/vector containing entry times for each tree node in this segment. And for swapping part, I could do it like replacing the entry time for swapped nodes in the set of their respective segments.Then how can I perform verifying this check for each node using this segment tree? This is where I'm getting stuck. Can you help me out, Please.
•  » » » 4 weeks ago, # ^ |   0 Editorial should have mentioned that, they compare only smallest and largest $posv$ to see if they are within $[posu,posu+sizu−1]$, rather than all its childs. see: https://mirror.codeforces.com/blog/entry/132569?#comment-1182635
•  » » » » 4 weeks ago, # ^ |   0 Yeah, I get it that checking the first and last child range is equivalent to checking all of children of u. Because the set stores the position of each node in sorted order.And we can easily perform swapping by first deleting the position of a node from its parent's children set and then add the swapped node position to it, and again the set would maintain all the positions in sorted order. The number of good nodes are decreased for now, as we need to check again after swap if they become good nodes.Now after swap, we only need to check for the (parent(a), a) and (a, children(a)) for all children of a. Similarly for (parent(b), b) and (b, children(b)) for all the children of b, for the condition of a good node. Because we want to see if after swap, the node is still contained in its parent range, and the node still contains all of its children within its range. If yes, then the number of good nodes increases by one each time for all these 4 pairs, otherwise not. And after each query, we check if all n nodes are good nodes or not. And we print the answer accordingly.
 » 4 weeks ago, # | ← Rev. 2 →   0 Can someone explain why this solution for D is timing out? 276371875I am trying to implement Um_nik's idea from his submission: 275817851
•  » » 4 weeks ago, # ^ |   0 Interesting, submitting your solution in GCC 7-32 yielded TLE while GCC 13-64 yielded RTE.Huge red flag of undefined behaviors right here, though I can't yet tell where it was.
 » 3 weeks ago, # |   0 Alternative (maybe easier) solution for D : let s[x] = {{j1,u1}, {j2,u2},... } be the set of indices and node id of the children of the node x, pos[x] the position of node x in P, and siz[x] the size of the subtree of node x.It suffices to check that for all i from 1 to n : pos[x] = min(s[x]) + 1 , and for all i from 1, s[x].size() — 1 : Ji+1 — Ji == siz[Ui] meaning the positions of the children of x when sorted should have the difference of siz[u] where u is the node with smaller pos.
 » 10 days ago, # |   0 Ask a question to the time complexity of G.this formula $2^{2B}+2^{2-B}$but you use some calculus you know B=1/3 it's minimum. not B=2/3