### maroonrk's blog

By maroonrk, history, 13 months ago,

We will hold AtCoder Regular Contest 132.

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

We are looking forward to your participation!

• +191

| Write comment?
 » 13 months ago, # |   +99 Reminder that the last AtCoder contest of 2021 is in around 30 minutes!
•  » » 13 months ago, # ^ |   +43 Good luck!
 » 13 months ago, # |   -40 orz
 » 13 months ago, # |   +11 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?
•  » » 13 months ago, # ^ |   +24 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).
•  » » » 13 months ago, # ^ |   0 That helps, appreciate it!
•  » » 13 months ago, # ^ |   +5 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
 » 13 months ago, # |   +10 Thank you for the contest , fascinating and pleasing problems (<=D , didn't read EF)
 » 13 months ago, # |   +31 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 :/.
•  » » 13 months ago, # ^ |   +31 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 for(int bit = 0; bit < 2*k; bit+=2) //use 1<
 » 13 months ago, # |   +12 I have tried to explain the first 3 problems here. Anyone having difficulty with these 3 problems can try it out.
 » 13 months ago, # |   0 I didn't understand problem A, even after seeing the editorial. Can anyone help? That'd be much appreciated.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 13 months ago, # ^ |   0 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.
 » 13 months ago, # | ← Rev. 2 →   0 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?
•  » » 13 months ago, # ^ |   0 [2, 1, 1] is not a permutation of [1, 2, 3]. The problem statement says that "Given are two permutations of 1,...,n"
 » 13 months ago, # |   0 Does the problem B — Shift and Reverse somehow relate to Dihedral group or am I just tripping?
•  » » 13 months ago, # ^ |   0 I think it does, as a matter of fact.