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

340E — Iahub and Permutations : Linear Algorithm
Автор accidentallygivenfuck, 11 лет назад, По-английски

Problem link : 340E - Iahub and Permutations
Can anyone prove following: 

dp[i] = (y+i-1)*dp[i-1] + (i-1)*dp[i-2];

This is an AC solution by problem-solved : 4384292

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

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

dp[i] — in how many ways can we fill (i + y) free positions if we have i bad numbers (numbered 1 to i) and y good numbers (numbered i + 1 to i + y)
dp[0] = y!
dp[1] = y * y! — y places to put 1 bad number
dp[i] = y * dp[i - 1] + (i - 1) * (dp[i - 1] + dp[i - 2])
1) y * dp[i - 1] — put a good number to position i:
we waste 1 good number, but now i become good, so stay y good numbers and (i - 1) bad numbers
2) (i - 1) * dp[i - 1] — put 1 of (i - 1) bad numbers to position i and put i to one of the positions (i + 1...i + y)
(i - 1) * dp[i - 2] — put 1 of (i - 1) bad numbers to position i and put i to one of the positions (1...i - 1)
We do not need other multipliers, because we only should to fix number at the position i.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    2) (i - 1) * dp[i - 1] — put 1 of (i - 1) bad numbers to position i and put i to one of the positions (i + 1...i + y)

    (i - 1) is for choosing a bad number. But why dpi - 1 ?
    Put 1 bad number to pos i (in (i - 1) ways), then put i to one of positions (i + 1...i + y) (in y ways).
    And we have y good and (i - 2) bad numbers left, which can be permuted in dpi - 2 ways.

    So I get (i-1)*y*dp[i-2].

    And...

    (i - 1) * dp[i - 2] — put 1 of (i - 1) bad numbers to position i and put i to one of the positions (1...i - 1)
    Lets say I choose j from (i - 1) bad numbers. If I put i to jth position then there are dpi - 2 ways to do so (we would have y good and i - 2 bad numbers). If I don't, then i becomes bad (as jth pos becomes forbidden pos of i) and I can permute them in dpi - 1 ways.

    I get (i-1)*(dp[i-2]+dp[i-1]).

    Can you please explain whole part 2 clearer and tell me where I am making mistake? :)

    → Ответить