nilesh8757's blog

By nilesh8757, history, 20 months ago, In English,

I was trying to solve this problem form recent Atcoder's beginner contest , but after scratching my head for almost 2h I could not come up with the solution.Then I tried to look for the editorials but this time they were not in English. square1001 has provided solution there which I find uses some kind of DP. Can anyone who has solved this problem explain DP recurrence behind this ?

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

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I also want to know the recurrence

»
20 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Short Answer

dp[k][h] := the answer if (K, H) = (k, h); W is fixed
dp[k][h] can be calculated by dp[k-1][h-1], dp[k][h-1] and dp[k+1][h-1]

Full Answer

dp is written as A in editorial.
We want to calculate dp[K][H].

I'll call horizontal line that lies on a-th and b-th vertical line (a, b).

First, dp[1][0] = 1, dp[2][0] = dp[3][0] = ... = dp[W][0] = 0 because there's no horizontal line.

Second, think when calculating h = i. Note that we already know dp[any][i - 1].
For each k = a, there's 3 choices; go straight, go right, or go left.

go straight

We can make neither (a, a + 1) nor (a - 1, a).

dp[a][i] += dp[a][i-1] * (no. of ways to make pairs that doesn't affect the above pairs; editorial call it Y)

NOTE : Y is no. of ways to make pairs whose y-coordinate = i. The others (whose coordinate < i) are counted by dp[a][i - 1].

go left

We should make (a - 1, a), and can make neither (a - 2, a - 1) nor a(a, a + 1).

dp[a-1][i] += dp[a][i-1] * (no. of ways to make pairs that doesn't affect the above pairs; editorial call it X)

go right

same as left. Define Z similarly.


Okay, now we want to calculate X, Y and Z for each k.

X, Y and Z can be calculated by brute force ( O(2 W)).

You can get AC now.

Editorial introduce the way to speed up using Fibonacci sequence.

Speeding up that my solution uses is like it.

Main idea of DP is same.

https://beta.atcoder.jp/contests/abc113/submissions/3715464

I wrote some comments in English to clarify.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Luma what does you DP[k][h] signify? does it mean number of ways to get to K'th vertical wall and at the H'th horizontal position?