Блог пользователя vivek_shah

Need Help for AtCoder DP Problem
Автор vivek_shah, история, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится 
      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
      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Here

→ Ответить