We will hold AtCoder Regular Contest 112.

- Contest URL: https://atcoder.jp/contests/arc112
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210213T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: nuip, potetisensei
- Testers: latte0119 reew2n
- Rated range: — 2799

The point values will be 300-400-500-600-700-900.

We are looking forward to your participation!

Will the round only be rated upon submission? (as usual)

Yes.

Really liked third problem. Fresh and new concept used.

How to solve it?

You can refer editorial. https://atcoder.jp/contests/arc112/editorial/746

I did almost the same way.

Can you link your solution . I thought of almost same solution but was unable to code it down . :(

I am curious, which?

Is it more difficult than a CF Div2?The first ARC I participate make me doubt my ability:(

You can compare first three problems of ARC to that of typical CF div2 (B/C/D)/E.

Thank you for the good contest! The problem is very interesting and challenging (really like problem B&C!

Is there a neat, less case-worky solution for 2nd problem? :(

You can calculate negative min max range and positive min max range. You have to take care of only one case this way which includes zero.

I calculated two intervals, one of type [-b — a1, -b + a2] and other [b — a2, b + a3] and then merged the intervals if they overlap.

Only three cases, b>0,b=0,b<0

For each case, you can do the operations in 4 ways:

Code

I have something that I think is less case-worky in code, although the proof itself seems to be as case-worky as the editorial's. Note: I assume $$$[a, b]$$$ is the closed interval over the integers with endpoints $$$a, b$$$.

With $$$B > 0$$$, it is easy to show that the solution is some subset of $$$[-B - n, B + n] \cup [B - n, B + n]$$$, by assuming that the first operation costs 0. Without the restriction $$$B > 0$$$, we can say that the solution is some subset of $$$[-B' - n, B' + n] \cup [B' - n, B' + n]$$$ where $$$B' = |B|$$$.

If we imagine that $$$[-B' - n, B' + n]$$$ and $$$[B' - n, B' + n]$$$ are disjoint, then operation 1 just switches between them. Hence we never need to use operation 1 more that twice. This conclusion holds even if the two sets are not actually disjoint.

If we use operation 1 zero times, we can get anything in the range $$$r_1 = [B - n, B]$$$. If we use it once, we can get the ranges $$$r_2 = [-B, -B + n']$$$ and $$$r_3 = [-B - n', -B]$$$ by using it at the start or at the end, where $$$n' = (C-1) / 2$$$. Finally, if use the operation twice, we get the range $$$r_4 = [B, B + n"]$$$. The nice thing is that this is independent of the sign of $$$B$$$.

The answer is then $$$|r_1 \cup r_2 \cup r_3 \cup r_4$$$.

You can consider b>0 and b<0 separately without intersections. From b>0 it is better to move to zero. From b<0 it is better to move to +/-INF;

Sample

Ah.. that was neat, thanks!!

After getting 3 WA,I inserted b=0 and c=1 case and in problem B and it passed :D.

Is the answer to D, the connected components in a graph of '#' + min(rows never visited[1,n-1],columns never visited[1,m-1]) ?

I tried this and got 30 correct and 7 wrong

You need to place '#' at (0,0), (h-1,0), (0,w-1), (h-1,w-1) and you will get AC because we can go there from any position.

Darn, I tried to handle cases where '#' occurs in the outer square seperately. It works now, thanks!

Who else did brute force for B and observed the patterns to get accepted!

Can u give link to ur submission?

Here is my solution https://atcoder.jp/contests/arc112/submissions/20164175 and here is the brute force solution I used to arrive at it — https://pastebin.com/q22jWKHi

It's the first time I participate in ARC, the problems are much harder than I thought, and I only solve two of them.

Since the editorial came out as soon as the contest ended, I think ARC is much better than ABC:)

Hope everyone can be better at solving problems and have fun during the contest, like I did!

It was the first ARC for me. Is ARC usually a little harder than a CF Div2?

Yesss

It's also my first ARC. Solving only 2 problems, I think it's definitely harder than div.2 :(

Can someone please explain the problem D, the 1st sample case, not able to get the problem statement.

How to solve problem $$$C$$$ ? I am not able to justify the solution in editorial and not able to get how to implement it .

Is following observation correct : Suppose player $$$2$$$ is on vertex $$$v$$$ and is going to decide to which children he should move . If he moves to child $$$u$$$ such that subtree at $$$u$$$ has even size , then when piece will return to $$$v$$$ back , the turn will be of $$$2nd$$$ player only.

`(This is an abridged version. The full version will be ready in a few hours.)`

Waiting for the full version of the editorial :(

One simple question about

F. Die Siedler.Why do numbers of the form $$$q = 2^k k! -1$$$ only have divisors which are either small or large? ($$$\min(d,\frac{q}{d})$$$ is no more than $$$1214827$$$ when $$$k\le 16$$$ in actual fact, according to which a simple big-small solution works in this task.)

Is it reasonable or just by coincidence?

BTW thanks very much for interesting problems. :)

It's a coincidence. I don't think this will holds also for large $$$k$$$.

btw still you can guess that this $$$q$$$ has only small or large factors. If a number has many small prime factors, then it will have some "medium" factor. But $$$q$$$ is not divisible by any prime number less than $$$16$$$ because $$$q+1$$$ is a multiple of $$$16!$$$, so it's likely to have large prime factors.

I see. Thanks.

It really doesn't hold for large $$$N$$$. Already for $$$N = 18$$$, the smallest prime divisor is $$$23,063,137$$$. I expect divisors to be

relativelysmall, but that's not what matters for time complexity here.Can we solve

CwithDP on trees??in Problem D

when Input is something like this, when we start from (2,2), we can go anywhere, one-direct. when we start from (1,1) we cann't approach (2,2). we cann't go everywhere. is this problem real okay to start from anywhere?

problem statement say that it should be efficient for "every" square. it was my misunderstood.

Can anyone pls tell what's the difficulty level of ABC and ARC in comparison to codeforces DIV2

`(This is an abridged version. The full version will be ready in a few hours.)`

Still the full version is not uploaded. maroonrk, Can you please look into it.

Who knows how to solve E?

The last operation must move either $$$a_1$$$ to the left or $$$a_N$$$ to the right. Pick one of those elements. Then, for any previous operation, we have 2 choices that don't matter — put this element to the left/right, or $$$2(N-1)$$$ choices in a smaller problem with the final sequence that doesn't contain this element. An $$$O(N^2M)$$$ DP solution is obvious from that.

Let's say that in the end, we'd move $$$l$$$ leftmost elements of $$$a$$$ to the left (in the moves that affect them last) and $$$r$$$ rightmost elements to the right. There are two things to think about: - The remaining elements in between, of course, must be in the same order as in the original permutation. - OTOH all cases $$$l+r=N$$$ correspond to distinct sequences of moves.

We have $$$l+r$$$ significant operations — those that move some element for the last time. There are $$$l+r \choose r$$$ ways to choose their order. If there were $$$c_k$$$ "insignificant" operations immediately after the $$$k$$$-th of them, where $$$\sum_{k=1}^{l+r} = M-l-r$$$, the number of possible sequences would be $$$\prod_{k=1}^{l+r} (2k)^{c_k}$$$. We can count them all with a DP, where states are $$$(l+r, \sum c_k)$$$, in $$$O(NM)$$$.

Finally, check all pairs $$$(l, r)$$$ and for those that are valid, get the DP value for $$$(l+r, M-l-r)$$$, multiply by $$${l+r \choose r}$$$ and sum that up to get the answer in $$$O(N^2+NM)$$$.

can you please explain

" $$$2(N−1)$$$ choices in a smaller problem with the final sequence that doesn't contain this element"what I think/understood is you are saying about the case when this element(that we choose to be the last move ) is chosen at an earlier moment, but I don't get from where $$$2(n-1)$$$ came ?

Let's say you made a sequence that has $$$a_N=N$$$ by moving $$$N$$$ to the right in the last ($$$M$$$-th) operation. In each previous operation, you can either move one of the elements $$$1, 2, \ldots, N-1$$$ to the left/right or move element $$$N$$$. There are $$$2(N-1)$$$ possible operations of the first type and the sequence you'd get by performing only these operations on the initial sequence $$$(1, 2, \ldots, N-1)$$$, i.e. ignoring all operations that move element $$$1$$$, must be $$$a_1, a_2, \ldots, a_{N-1}$$$.

If you're dumb like me and can't see the smart math ideas, you can also just speed up to $$$\mathcal O(N^2 \log N)$$$ using FFT.

There's a lot of problems I've solved with dumb ideas too. Especially sqrt decompositions. This isn't a hard thing to realise though — just that we need only $$$l+r$$$ for states, not $$$(l, r)$$$.