### maroonrk's blog

By maroonrk, history, 2 months ago,

We will hold AtCoder Regular Contest 142.

The point values will be 300-400-500-800-900-1000.

We are looking forward to your participation!

• +61

 » 2 months ago, # |   +13 DEF problems so HARD!
•  » » 2 months ago, # ^ |   -21 Actually I found C also hard. I had basically all observations listed in the tutorial, but still not able to implement it right. Given that an interactive problem has basically no example testcases, it becomes mostly guessing to get such a casework right.
 » 2 months ago, # |   -21 What does C mean, I have been unable to understand
•  » » 2 months ago, # ^ |   -21 What is an interactive task and how to deal with it
•  » » » 2 months ago, # ^ |   -21 See the practice contest, it is made to answer beginner questions.
•  » » » » 2 months ago, # ^ |   0 thanks, but Permission denied. ,I can't access.
•  » » » » » 2 months ago, # ^ |   0 You have to register for the practice contest before viewing the tasks.
•  » » » » » » 2 months ago, # ^ |   0 thanks, now I can access it
 » 2 months ago, # |   +26 How to solve D?
•  » » 2 months ago, # ^ |   0 The english editorial is now released: https://atcoder.jp/contests/arc142/editorial/4165
 » 2 months ago, # |   -12 C was a really nice problem, ORZ to problem author
 » 2 months ago, # |   +61 Problem F:There are 5 types of spell combinations: X and Y fixed X and Y same X and Y different X free, Y fixed 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)$.
 » 2 months ago, # |   +3 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
•  » » 2 months ago, # ^ | ← Rev. 3 →   +17 I also did that at first, but I realized for the following test case, this solution fails. 4 1 4 4 3 3 2
•  » » » 2 months ago, # ^ |   0 Thank you!
 » 2 months ago, # |   0 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.
 » 2 months ago, # |   +1 The problem statement of A was vague
 » 2 months ago, # |   +7 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.
•  » » 2 months ago, # ^ |   +13 I agree to you, stranger...
 » 2 months ago, # |   0 Could someone explain why I'm getting WA on 4 pretests of A? Don't understand what I'm missing here. Submission. Thanks.
•  » » 2 months ago, # ^ |   +1 I also got WAs for the same 4 pretests for A. During the contest, my suspicion was that 1420 142 gives 3, but 1420 241 should give 0.This is because 241 is not the minimum. I added such check. After that, I got AC.
 » 2 months ago, # |   +8 A different approach to C — Tree Queries: Root the tree at 1. 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]$). 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$. If we found no children of 1, then 2 must be a child of 1, so the answer is 1. 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.
 » 2 months ago, # |   0 Is it rated?
 » 2 months ago, # |   +16 Is it just me or is AtCoder rating not updated yet? Doesn't AtCoder normally update ratings very quickly 👀
 » 2 months ago, # |   0 Was this contest rolled back?It's quite unusual.
 » 2 months ago, # |   0 How to solve D? The editorial is hard to understand..
 » 7 weeks ago, # | ← Rev. 2 →   +10 (@*&$(*@#&$)!*&$)(!*#$)!(@*$#)(*!@$()*!(*)!@%!@%
 » 7 weeks ago, # |   +5 just want to know when c++20?
•  » » 7 weeks ago, # ^ |   +3 ok, got it, math doesn't needs c++20