Yes.

How to solve it?

I am curious, which?

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

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.

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

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

1. only operation 2
2. do operation 2, then do operation 1
3. do operation 1, then do operation 2
4. do operation 1, then do operation 2, then 1

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

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.

Can u give link to ur submission?

Yesss

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

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.

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 relatively small, but that's not what matters for time complexity here.

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

I read somewhere that ABC is Div2 , with A being way too easier.ARC is Div1- , and AGC is Div1

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