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 dimachine 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.