DEF problems so HARD!

What does C mean, I have been unable to understand

How to solve D?

C was a really nice problem, ORZ to problem author

Problem F:

There are 5 types of spell combinations:

1. X and Y fixed
2. X and Y same
3. X and Y different
4. X free, Y fixed
5. X fixed, Y free

Note that in type 3, with the number of (1,2) and (2,1) fixed, their order does not affect the answer, we iterate that number. Then note that spells of type 2,4, and 5 are in the form of "11112222", you can iterate the partition point of type 2, and use two-pointers method to find the best partition point of type 4 and 5 individually.

Complexity: $$$O(N^2)$$$.

Problems C.

Why cannot we determine whether the distance is 1 or not by checking if $$$\lvert dist1[v] - dist2[v] \rvert = 1$$$ holds for every v > 2, where dist1[i] — the distance from node 1 to node i and dist2[i] — the distance from node 2 to i?

I tried this and got just one wrong test. https://atcoder.jp/contests/arc142/submissions/32608699

For problem B, at first I thought that random algorithm might work, but after coding, I found that even for n=8, it costs too much time. Then, I fix some integer i, and realized that if I could put [1,i-2] to some other cells that are not the "eight" ones, while only leaving i-1 to one of the "eight" ones, it should always work. It turns out that this is one of the approaches mentioned in the editorials.

The general idea in problem C is to obtain two arrays, d1[i] denoting the distance from node-1 to node-i, and d2[i] denoting the distance from node-2 to node-i. Then, with d2[i]=1, we could find the parent node and child nodes of node-2, and among them, the one which has the minimum distance to node-1 (by checking d1[i]) should be the parent of node-2. If we denote this index as idx, then the answer is d1[idx]+1. But this is the most simple case while I think there are several other cases which are very tricky. For instance, there is no d2[i]=1 (meaning that node-1 is just the parent of node-2 and node-2 has no child nodes), or, there is only one d2[i]=1 and d1[i]=2 (there are two cases, 1->2->x, and 1->x->y->3), and so on. I missed one of them which cost me one WA.

Finally, problems starting from D, are too crazy.

The problem statement of A was vague

I really disliked A. It had an unnatural statement and overall just wasn't very interesing.

B is pretty cool.

C seems somewhat forced. Even though it's really fun I'm not sure if it needed to be an interactive problem. I personally found B to be harder than C.

Could someone explain why I'm getting WA on 4 pretests of A?
Don't understand what I'm missing here.
Submission.
Thanks.

A different approach to C — Tree Queries:

1. Root the tree at 1.
2. Find all the vertices (except for 2) which are direct children of 1, and also all the vertices which have depth 2 (that is, query $$$d_{1,i}$$$ for each $$$i \in [3, N]$$$).
3. If 1 has at least two children, then we can take any two of them (say, $$$a$$$ and $$$b$$$), and find the answer as $$$d_{1,2} = max(d_{a,2}, d_{b,2}) - 1$$$.
4. If we found no children of 1, then 2 must be a child of 1, so the answer is 1.
5. Lastly, say that we have found only one child of 1 (let's call this child $$$a$$$). Then 2 must be either another child of 1, or a descendant of $$$a$$$. Query for $$$d_{a,2}$$$.
   • If $$$d_{a,2} \ne 2$$$, then 2 is for sure a descendant of $$$a$$$, and the answer is $$$d_{a,2} + 1$$$.
   • If $$$d_{a,2} = 2$$$, then we need to find a vertex $$$i$$$ of depth 2 that is adjacent to vertex 2, and query for $$$d_{a,i}$$$ (here, we will need results from step 2). If there is no vertex $$$i$$$ or it is not adjacent to $$$a$$$, then 2 must be a child of 1 (and the answer is 1). If $$$i$$$ is adjacent to $$$a$$$ ($$$d_{a,i} = 1$$$), then 2 is a child of $$$i$$$ (while $$$i$$$ is a child of $$$a$$$), so the answer must be 3.

The code is here.

In the worst case, this solution will take $$$2N - 3$$$ queries, like the one in the editorial. But in most cases, it will take at most $$$N - 1$$$ queries. On the downside, this approach is rather caseworky.

Is it rated?

Is it just me or is AtCoder rating not updated yet? Doesn't AtCoder normally update ratings very quickly 👀

How to solve D? The editorial is hard to understand..

(@*&$$$(*@#&$$$)!*&$$$)(!*#$$$)!(@*$$$#)(*!@$$$()*!(*)!@%!@%

just want to know when c++20?