maroonrk's blog

AtCoder Regular Contest 132 Announcement
By maroonrk, history, 3 years ago, In English

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!

  • Vote: I like it
  • +191
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -40 Vote: I do not like it

orz

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like 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

    → Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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 :/.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    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<<bit here

    I should use

    for(int bit = 1; bit < (1<<(2*k)); bit *= 2)
//use bit here

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    [2, 1, 1] is not a permutation of [1, 2, 3]. The problem statement says that "Given are two permutations of 1,...,n"

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the problem B — Shift and Reverse somehow relate to Dihedral group or am I just tripping?

→ Reply