maroonrk's blog

AtCoder Regular Contest 142 Announcement
By maroonrk, history, 3 years ago, In English

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!

  • Vote: I like it
  • +61
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

DEF problems so HARD!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

What does C mean, I have been unable to understand

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

How to solve D?

→ Reply
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

C was a really nice problem, ORZ to problem author

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

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

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

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +17 Vote: I do not like it

    I also did that at first, but I realized for the following test case, this solution fails.
    4
    1 4
    4 3
    3 2

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

The problem statement of A was vague

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

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated?

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

just want to know when c++20?

→ Reply