accidentallygivenfuck's blog

340E — Iahub and Permutations : Linear Algorithm
By accidentallygivenfuck, 11 years ago, In English

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

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

»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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? :)

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

      actually，the second part is just like derangement

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

        Yes, I read about it, not here but here :). But I get WA : 4434242 :(
        It is obvious that my solution is incorrect (see 1) below) but I can't find where I made a mistake.

        1) (i-1)*y*dp[i-2] + (i-1)*(dp[i-2]+dp[i-1]) and (i-1)*(dp[i-2]+dp[i-1]) are not the same of course.
        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          think about it : part 2 has nothing to do with y

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

            we just need to put the limited numbers first

            1:put the numbers in unlimited positions 2:put the numbers in limited positions so the second part has nothing todo with y

            → Reply