Time is also good for central asia

Why still no editorial for ABC 193????... Please provide it, or else can anyone explain Problem E ??

Just commented here so that author can see this

Thanks for all the problems and Good Luck!

satashun is my direct senior in the same faculty, and I’m so sad to hear this may be the last contest ;-;

I’m looking forward to solving his interesting problems and hope many contestants!

https://kenkoooo.com/atcoder/#/table/

My $$$O(nm)$$$ solution I failed to finish in time:

Consider $$$ans_i$$$ to be the answer for $$$n = i$$$. We seek $$$ans_n$$$.

Let us say that we add the ending element $$$x$$$ to a sequence. Then, we have three cases:

1. We have never seen this element before. Then we need to add 1.
2. We have seen this element before, say at index $$$k$$$. All the elements from $$$k$$$ to $$$i$$$ are $$$> x$$$. Then we need not add anything, because we could paint it with a range
3. We have seen this element before, say at index $$$k$$$. There is an element between $$$k$$$ and $$$i$$$ such that it is $$$< x$$$. Then, we need to add 1, because we cannot paint a range

So, to get $$$ans_i$$$, for every $$$x$$$, we need to add 1 for all combinations where points 1 or 3 apply. The number of such combinations is a sum $$$S_x = m^{i-1} - \sum_{k = 1}^{i-1} (m-x)^{i-1-k} \cdot m^{k-1}$$$. The latter part of this equation counts the instance where we have only elements $$$>x$$$ between $$$k$$$ and $$$i$$$.

So, $$$ans_i = \sum_{x = 1} ^{m}ans_{i-1} + S_x$$$. By using the previous value for $$$S_x$$$ and updating it every iteration, we can solve it in $$$O(nm)$$$.

Submission

Got stuck on A's 13th Test Case (1 WA/15). How does enumeration work, though? I didn't even attempt it because of the 2^15+ apparently possible permutations.

I just did read the editorial of C. It seems I did not get how the operation works.

I thought that the operation allways needs exactly that much steps as there are distinct elements in X. But in editorial they construct some graph...and things.

Can you explain what the operation does, and why we need that graph thing?

I've also got my O(N*M*logN) solution TLE and the Editorial says O(M*N) [since we can incrementally calculate the powers]. I pre-calculated powers in memory in order to get O(M*N) solution with Haskell, but it TLE'ed again for me, so I Wolfram|Alpha-ed the sum through N to get O(MlogN).

Wait for a couple of weeks before it arrives.

https://atcoder.jp/posts/21

I had the same complexity and it got passed under 200ms https://atcoder.jp/contests/arc114/submissions/20940288

I find my bug and that was seriously stupid! poooof!

I am doing almost similar thing. Take GCD of the given numbers. If GCD != 1 then we have got our answer. Else find minimum factor of each number & store in set (so that numbers remain unique). Then finally print multiplication of the stored numbers in the set.

But its giving WA can you help? My Submission

(Seriously I cannot understand how <spoiler> works...Could anyone tell me how to use it?)

Edited: Okay it seems to work although I did not really change anything...Whatever

Thank you for the lovely solution. I was looking for a similar dp but was not able to see the trick of the one only adding if it is the last one. I however stumbled across this solution. I am not sure how to prove all the steps but it went something like this:

let $$$X = min(A_{l...r})$$$. Thus considering the immediate neighbours there are three cases to consider

Thus we calculate $$$dp[length][type]$$$ in $$$O(mn)$$$ using the above formulas. We then iterate over all $$$i$$$ and $$$j$$$ st $$$1 \le i \le j \le n$$$ and add the corresponding dp to ans resulting in something like this

Consider red and blue edges as 0s and 1s, and on each vertex write xor of edges connecting to it.

$$$E[turns] = E[horizontal cuts + vertical cuts] = E[horizontal cuts] + E[vertical cuts]$$$. . $$$E[horizontal cuts]$$$ = $$$\sum_{i}P(i).1$$$ where $$$P(i)$$$ is probability that $$$i'th$$$ row is cut in some turn. To calculate this sum iterate over each row and find probability that this row is deleted. Let's consider the two given black cells have rows $$$r$$$ and $$$y$$$ where $$$r < y$$$. Make a square having two black cells as opposite ends. Whenever we cut any lines in this square game ends immediately. Let's call total lines in this square as $$$T$$$. Consider each line above $$$r$$$, to find $$$P(r)$$$ notice that we have to cut this line first from a set of rows which should have every row from this row to $$$y$$$ and all columns in the square we drawn above which is equal to $$$S=y-i+T$$$. $$$P(i<r) = 1/S$$$. Now you can similarly consider other two cases where row resides in square and row lies below square. Also do the same for vertical lines.

I'm pretty sure it's solvable in $$$O(M \log N)$$$. We're basically counting $$$\sum (N-d-1) M^{N-d-2} (m-1)^2 ((M-m+1)^d-(M-m)^d)$$$ or simpler, which can be reduced to sums in the form $$$\sum (m/M)^d (N-d-1)$$$ and that can be converted to closed form using generating functions for fixed $$$m$$$. It's a lot of careful algebra.

Supposing we know $$$a$$$ (we do, these are the initial positions of the tokens) and $$$b$$$ (we don't, these are the final positions of the tokens): if the XOR (symmetric difference) of these two sets is $$$T$$$, then at least we know the answer exists, and $$$b$$$ is one such possibility.

The intuition here is the following:

• When we move a token from position $$$a$$$ to position $$$b$$$, moving the token directly from $$$a$$$ to $$$b$$$ ($$$a \rightarrow b$$$) is equivalent (albeit with different cost) to $$$a \rightarrow INF \rightarrow b$$$ (since the path $$$a \rightarrow b$$$ is traversed once, the path $$$b \longleftrightarrow INF$$$ is traversed twice, so the edge colors in this latter part are un-affected)
• Writing the move above ($$$a \rightarrow b$$$) in terms of applying "XOR" to a range, this is doing XOR $$$1$$$ in the range $$$[a, b)$$$, which is the same as doing both XOR $$$1$$$ in range $$$[a, INF)$$$ and XOR $$$1$$$ in range $$$[b, INF)$$$ (given the rationale described previously that these two are "equivalent").
• Jumping ahead a bit, let's look at $$$T$$$. If for each position $$$t \in T$$$ we XOR 1 the range $$$[t, INF]$$$, and given that $$$|T|$$$ is even, you can notice that we will get the alternating 0 — 1 — 0 ... — 0 sequence of edge segments. (think about why this only works for even $$$|T|$$$).
• Each of the XOR 1 $$$[t, INF]$$$ (for all $$$t \in T$$$) operations above can be done an odd number of times. You will still get the alternating 0 — 1 — 0 ... — 0 sequence of edge segments.
• Remember how in our second bullet point we showed that doing the move $$$a \rightarrow b$$$ (XOR $$$1$$$ in the range $$$[a, b)$$$) is equivalent to $$$a \rightarrow INF \rightarrow b$$$ (XOR $$$1$$$ in range $$$[a, INF)$$$ and XOR $$$1$$$ in range $$$[b, INF)$$$)? That means that our desired set of XOR ranges (XOR 1 $$$[t, INF]$$$ (for all $$$t \in T$$$)) can correspond back to some $$$a$$$ and $$$b$$$. We know $$$a$$$, so we need to find $$$b$$$.

Now, from $$$a$$$ and $$$T$$$ we can recover $$$b$$$. Because:

• $$$a \oplus b = T$$$ (from the previous paragraph)

• $$$a \oplus T = b$$$.

It should be the case that $$$|a| \geq |b|$$$. Otherwise, we need more final positions than # of initial tokens we had.

Note that when we recover $$$b$$$ from $$$a \oplus T$$$, it could be that $$$|b| \leq |a|$$$.

Finally, we do the following DP. $$$dp[i][j]$$$: The minimum cost of matching the first $$$i$$$ positions in (sorted) $$$a$$$ with the first $$$j$$$ positions in (sorted) $$$b$$$. For each transition, we might decide to pair $$$(i, j)$$$ or pair $$$(i, i + 1)$$$ (since there are not enough $$$b$$$s). The answer is when everything has been paired ($$$dp[|a|][|b|]$$$).