We will hold AtCoder Regular Contest 132.

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

The point values will be 400-400-600-700-800-900.

We are looking forward to your participation!

Reminder that the last AtCoder contest of 2021 is in around 30 minutes!

Good luck!

orz

How do you solve C, I've tried a 5 state DP but couldn't get the third sample right. Basically my idea is to erase all the positions in which $$$a_i$$$ initially matches $$$p_i$$$ and work with the rest. Since we are working with permutations no two elements coincide and choices on the $$$i_{th}$$$ position are affected only by its closest (on the left) five neighbors. So I maintain $$$dp[i][j][k][l][m]$$$ in which $$$i$$$, $$$j$$$, $$$k$$$, $$$l$$$, and $$$m$$$ are the differences between each $$$p_k$$$ and the respective $$$a_k$$$ for the last 5 elements. This should work in $$$O(n\cdot10^5)$$$ but I keep missing something or the whole idea is wrong lmao. What would be the correct approach?

You'll actually need to account for 10 neighbors. For example, both p[1] and p[11] can be 6 if d = 5, so to consider p[11]'s value you need to pay attention to p[1]'s value too. However, you're pretty close: you'll only need to account for which values from p[i] — 5 to p[i] + 5 have been taken. This implies a bitmask dp of sorts with dp[i][mask] being how to fill the first i positions and mask represents which values from p[i] — 5 to p[i] + 5 have been taken, which works in O(10 * n * 2^10).

That helps, appreciate it!

I had some bitmask DP (exactly the same as dimashicpc2023 described) (you actually need at most 11 neighbors, the values in range [pos — 5, pos + 5])

Here is my code: Problem C code

Thank you for the contest , fascinating and pleasing problems (<=D , didn't read EF)

My solution for F had intended complexity but a terrible constant it seems. First I computed answer mod 998244353 which was fast enough but I got WA. Then I realized that I need to print the real answer but my code got TLE with long longs :/.

I found the reason for TLE, leaving it here so that people reading don't ever make the same mistake.

This has to be one of the dumbest reasons for TLE I encountered in a long time.

I decided that instead of using

I should use

Changing the later to former makes my code 2 times faster it seems.

I should have known that division slows my code down by a lot. But it is a bit easier for me to work with the slower version, and it has never let me down before so I didn't know the effect is that big. So it has became a habit and I do it automatically QaQ.

I have tried to explain the first 3 problems here. Anyone having difficulty with these 3 problems can try it out.

I didn't understand problem A, even after seeing the editorial. Can anyone help? That'd be much appreciated.

In the example where N is 5, initially the matrix looks like:

We can start by determining that the entire row where it has 5 '#'s are determined. Same for column:

Based on the above, we also know the entire row where it has 1 '#'s are determined. Same for column:

After handling 5 and 1, the next targets are 4 and 2. First do it for 4:

Then fill in the dots based on 2:

Lastly, it is the 3:

My solution did not use the formula where most people used. My implementation is: submission

Think about a case that r={1,2,...,n} and c={1,2,...,n}.

Then the solution obviously looks like this:

So arrays r and c can be seen as sorting the rows/columns of this matrix to make a new one.

Like when you swap row 1 and 2, you get:

and so on. Ultimately you'll get the matrix you want.

The editorial mentions, that that a cell {x,y} is '#' if row[y] + col[x] >= n + 1. I thought about the following example: n = 3, rows = 2 1 1 and cols = 2 1 1 The cell {0, 0} fulfills the requirement, but there is the following possibility to construct the matrix:

.XX

X..

X..

What is the intuition why the formula mentionend in the editorial is correct?

[2, 1, 1] is not a permutation of [1, 2, 3]. The problem statement says that

"Given are two permutations of 1,...,n"Does the problem B — Shift and Reverse somehow relate to Dihedral group or am I just tripping?

I think it does, as a matter of fact.