red_coder's blog

how to solve this...
By red_coder, 12 years ago, In English

     A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can be deranged into {2,3,1} and {3,1,2}. We can modify this slightly for n numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers {1,1,2,2,3} could be deranged into {2,2,1,3,1}, {2,2,3,1,1}, {2,3,1,1,2}, and {3,2,1,1,2}. Write a program that takes a series of numbers and outputs the number of derangements of nums.

sample input: {0,0,0,0,0,0,0,1,1,1,1,1,1,1,2} sample output: 14

sample input: {0,5,4,2,3,6,6} sample output: 640

now how to solve it??? can anyone give a detailed solution..

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

»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

pls somebody help me

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Provide a link to original problem. What restrictions we have on input data?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    It is topcoder srm 176 div 1 500 points problem. Array contain between 1 and 15 elements inclusive. So it can be simple dp with mask.
    my solution.

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

yipeeee!!!!! finally solved it myself without any help by inclusion-exclusion principle. But still it can also be solved by memoized recursion. If anyone knows this method pls tell....

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

@goo.gl_SsAhv: It more looks like a theoretical problem than a programming one so I guess there are not any links in online judges or programming websites.

P.S. Lucky post number (4774) :D

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

    Petar- it is topcoder srm 176 div 1 500 points problem

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

      You're right. Fair enough. I just guessed. But it stills looks more theoretical.

      → Reply