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.
I saw some videos related to Dihedral groups but I'm still unable to connect how that information will help us to quickly solve this problem?
Would you mind to explain or give some hints?