Flamire's blog

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) Editorial
By Flamire, history, 4 months ago, In English

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

2002D1 — DFS Checker (Easy Version) and 2002D2 — DFS Checker (Hard Version)

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)
  • Vote: I like it
  • +125
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Woah, I solved A,B,C all through guessing and became purple!

→ Reply
»
4 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Why this solution of mine for C is giving WA on test5? 275844339

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    1. Check for integer overflow

    2. sqrt can cause precision loss, i recommend you eliminate it completely

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you can just compare the squared distance, you end up squaring it again after taking the square root anyways

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you! it worked :)

          by the way, just want to understand how to identify such things?

          → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For me, I used long double in C++ and it worked.

          → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

lol, you can solve D1 in $$$O(N*Q)$$$ with pragmas: 275797240

Also you can use segment tree too for E: 275831791

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Only solve A, B.

I am too weak. T^T

→ Reply
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Let's note the following $$$pos_x$$$ : position of $$$x$$$ in $$$p$$$

    $$$sub_x$$$ subtree size of x

    For 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 D1

    For 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 set

    Finally if the set of bad children of a node is empty than erase this node from $$$bad$$$ otherwise insert it.

    → Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the image in c's tutorial is not visible

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Why this solution of mine for D1 is giving TLE on test9 and it's O(n*q)? My Solution

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Because n*q is too big

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i thought that too, but i asked bcos i see people saying they solved it in O(n * q)

      → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am really dumb .

But Why CD = AD in tutorial of C . I don't understand that

could anyone explain that pls.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 months ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

Alternative (possibly wrong?) solution for D2:

  1. 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.

  2. Also check that for each $$$i$$$ the position of $$$i$$$ in $$$p$$$ is greater than the position of its parent.

  3. 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.

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    This solution is very similar to check2. I suspect it's correct and should be provable in a similar way.

    Fact
    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone write out the proof by induction in B? I'm not sure how to prove it...

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

What is $$$fa$$$ mentioned in Problem-D Check 2?

Ref
→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

My Insights for A,B,C

A
B
C
Fun Fact
→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you come up with the conclusion of A? I turn to solve B/C instead.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to come up with something related about multiplication of numbers

      You can see the cases like this

      Cases Observation

      I think the observing the thing described in the spoiler is enough to come up with

      $$$\displaystyle \min(n,k) \times \min(m,k)$$$
      → Reply
»
4 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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?
        How I have proved that?
        editorial check
        code check
        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Ok I guess I didn't understand the induction right. I got it now. Thank you!

          → Reply
»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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?

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It means the father of $$$p_{i+1}$$$. Apparently it's not as widespread as I thought. I've added an explanation.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved ABCD1 and became specialist.

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WOW!You are very good! But could you give me some exegesis in the H code?

→ Reply
»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

why was E placed after D?

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$1 \le a_i \lt i$$$, but in your case $$$a_3 = 7$$$ so it's invalid.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$: 276065570

I wonder how far could the uphack raise up "cheeseable" lowerbound value for $$$L$$$.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain how we are supposed to preprocess GCD as mentioned in F1 solution?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't preprocess GCD, my solution got passed

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

For problem D, the following check is also sufficient:

  • for every $$$i$$$ : $$$lca(p[i-1], p[i]) = parent(p[i])$$$
→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    It's just check2 written in another form.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain why this solution for D is timing out? 276371875

I am trying to implement Um_nik's idea from his submission: 275817851

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for f1, if you let p be the largest prime <= n, then x<=p or y<=p is possible.

→ Reply