Flamire's blog

EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) Editorial
By Flamire, history, 3 days 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
  • +119
  • Vote: I do not like it

»
3 days 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
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You really solved E first... :skull:

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

      I got stuck for an hour trying to prove the earlier problems XD

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

    I created video editorial for E: Cosmic Rays.

    → Reply
»
2 days 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
  • »
    »
    2 days 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
    • »
      »
      »
      47 hours 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
      • »
        »
        »
        »
        47 hours 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
        • »
          »
          »
          »
          »
          47 hours 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
        • »
          »
          »
          »
          »
          43 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
2 days 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
»
2 days 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
»
2 days ago, # |
  Vote: I like it -21 Vote: I do not like it

Only solve A, B.

I am too weak. T^T

→ Reply
»
2 days 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
  • »
    »
    2 days 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
  • »
    »
    2 days 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
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

the image in c's tutorial is not visible

→ Reply
»
2 days 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
  • »
    »
    2 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Because n*q is too big

    → Reply
    • »
      »
      »
      2 days 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
»
2 days 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
  • »
    »
    2 days 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
  • »
    »
    2 days 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
»
2 days 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
  • »
    »
    2 days 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
  • »
    »
    2 days 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
»
2 days 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
  • »
    »
    2 days 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
  • »
    »
    29 hours 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
»
2 days ago, # |
  Vote: I like it +14 Vote: I do not like it

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

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

My Insights for A,B,C

A
B
C
Fun Fact
→ Reply
  • »
    »
    2 days 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
    • »
      »
      »
      2 days 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
»
2 days 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
»
2 days ago, # |
  Vote: I like it +1 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
»
2 days ago, # |
  Vote: I like it 0 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
»
2 days 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
  • »
    »
    2 days 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
»
2 days 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
»
47 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved ABCD1 and became specialist.

→ Reply
»
45 hours 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
»
37 hours 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
»
36 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

why was E placed after D?

→ Reply
»
32 hours 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
  • »
    »
    31 hour(s) 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
»
30 hours 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
»
26 hours 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
»
25 hours ago, # |
  Vote: I like it +8 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
  • »
    »
    10 hours ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    It's just check2 written in another form.

    → Reply
  • »
    »
    7 hours ago, # ^ |
      Vote: I like it 0 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