We will hold AtCoder Regular Contest 142.

- Contest URL: https://atcoder.jp/contests/arc142
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220619T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: m_99
- Tester: maspy, satashun
- Rated range: — 2799

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

We are looking forward to your participation!

DEF problems so HARD!

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.

What does C mean, I have been unable to understand

What is an interactive task and how to deal with it

See the practice contest, it is made to answer beginner questions.

thanks, but

`Permission denied.`

,I can't access.You have to register for the practice contest before viewing the tasks.

thanks, now I can access it

How to solve D?

The english editorial is now released: https://atcoder.jp/contests/arc142/editorial/4165

C was a really nice problem, ORZ to problem author

Problem F:

There are 5 types of spell combinations:

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

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

4

1 4

4 3

3 2

Thank you!

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.

I agree to you, stranger...

Could someone explain why I'm getting WA on 4 pretests of A?

Don't understand what I'm missing here.

Submission.

Thanks.

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.

A different approach to C — Tree Queries:

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 👀

Was this contest rolled back?It's quite unusual.

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

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

just want

~~to know when~~c++20~~?~~ok, got it, math doesn't needs c++20