vivek_shah's blog

Need Help for AtCoder DP Problem
By vivek_shah, history, 6 years ago, In English

Hi all, I need help in solving this DP problem from Atcoder.
The editorial for this problem is not available in English and hence I can't even get a bit of it.
Some thoughts which came into my head after reading the problem :-
1) Oh, this is another counting problem and the constraints are too low, surely it's a DP problem.
2) The constraints on W <= 8, may be it has something to do with bitmasks ?

But, I can't figure out the state of DP and transition of DP states. It would be great help if anyone could give me some hints on how to approach this DP problem. Please explain the state and DP transition. I would love to implement the problem on my own.

A help would be appreciated. Thanks!

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that: state = [at_V_line(100)][ball_at_which_H_line(8)][which_H_lines_are_set(1<<8)] then generate all subsets of 8, and update next V line position if they are valid. An invalid would be if ball has fallend down before K, ball has not fallen after K or we have next line starting at H which we have current H line ending at. So time complexity 100*8*(2^8)*(2^8) = 52,428,800 , I think should pass

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

    Can you please elaborate in detail the recurrence relation for DP?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
      REP(v,V+1)REP(h,H+1)REP(h_mask,(1<<H))REP(new_mask,(1<<H)) {
if((new_mask&h_mask)>0) continue;//we have matching adjacent lines
//also check if ball falls and if needs to fall,
//leaving it as exercise for reader
//now if all is ok:
DP[v+1][new_ball_position][new_mask]+=DP[v][h][h_mask];//mod it too
}
//result is sum of DP[V][0:H][0:1<<H], which is every valid subset and position when reaching end
      → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Here

→ Reply