Algorithm

Problem Statement for KeysInBoxes

Problem link- https://community.topcoder.com/stat?c=problem_statement&pm=8202&rd=11125

Problem Statement
    

There are N boxes numbered from 1 to N and N keys numbered from 1 to N. The i-th key can only be used to open the i-th box. Now, we randomly put exactly one key into each of the boxes. We assume that all configurations of keys in boxes occur with the same probability. Then we lock all the boxes. You have M bombs, each of which can be used to open one locked box. Once you open a locked box, you can get the key in it and perhaps open another locked box with that key. Your strategy is to select a box, open it with a bomb, take the key and open all the boxes you can and then repeat with another bomb.

Return the probability that you can get all the keys. The return value must be a string formatted as "A/B" (quotes for clarity), representing the probability as a fraction. A and B must both be positive integers with no leading zeroes, and the greatest common divisor of A and B must be 1.
 

Definition
    
Class: KeysInBoxes
Method: getAllKeys
Parameters: int, int
Returns: String
Method signature: String getAllKeys(int N, int M)
(be sure your method is public)
    
 
 

Constraints
- N will be between 1 and 20, inclusive.
- M will be between 1 and N, inclusive.
 

Examples
0)  
     
2
 
1
 
Returns: "1/2"
When box 1 contains key 2, you can get all the keys.
1)  
     
2
 
2
 
Returns: "1/1"
When N=M, you can always get all the keys.
2)  
     
3
 
1
 
Returns: "1/3"
There are 6 possible configurations of keys in boxes. Using 1 bomb, you can open all the boxes in 2 of them:
  • box 1 - key 2, box 2 - key 3, box 3 - key 1;
  • box 1 - key 3, box 2 - key 1, box 3 - key 2.
3)  
     
3
 
2
 
Returns: "5/6"
Now, when you have 2 bombs, you are only unable to get all the keys in the following configuration: box 1 - key 1, box 2 - key 2, box 3 - key 3.
4)  
     
4
 
2
 
Returns: "17/24"

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

long long str[21][21], fact[21];

class KeysInBoxes {
public:
  string getAllKeys(int N, int M) {
    str[0][0] = 1;
    for(int i = 1; i < 21; ++i)
      for(int j = 0; j <= i; ++j)
        str[i][j] = str[i - 1][j - 1] + i * str[i - 1][j];

    fact[0] = 1;
    for(int i = 1; i < 21; ++i)
      fact[i] = fact[i - 1] * i;

    long long res = 0;
    for(int i = 0; i < M; ++i)
      res += str[N - 1][i];

    long long gcd = __gcd(res, fact[N]);

    return to_string(res / gcd) + "/" + to_string(fact[N] / gcd);
  }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
1

Output

x
–
+
cmd
"1/2"
Advertisements

Demonstration

TopCoder Solution SRM391-D1-500 Statement for KeysInBoxes C,C++, Java, Js and Python ,SRM391-D1-500,TopCoder Solution