SRM 592, D2, 500-Pointer (LittleElephantAndPermutationDiv2)

James S. Plank

Thu Aug 27 00:32:54 EDT 2020

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh: MD5 Hash: 04039f6e7a131ae8f6da4c05829c7d05
answers.txt: MD5 Hash: 8b3bb49d150e90ea3f1bae1f95e0894e
Problem Given in Topcoder: 2013
Competitors who opened the problem: 997
Competitors who submitted a solution: 490
Number of correct solutions: 378
Accuracy (percentage correct vs those who opened): 37.9%
Accuracy (percentage correct vs those who submitted): 77.1%
Average Correct Time: 31 minutes, 34 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a number N and a number K.
Consider the vectors A and B, each of which contain integers and are the same size. I'm going to define a function called magic(A,B), which is the sum of max(A[i],B[i]) for all i.
Your job is to return the number of pairs (A,B) such that both A and B are permutations of the numbers from 1 to N, and magic(A,B) ≥ K.
The topcoder constraints are the N is between 1 and 10, and K is between 1 and 100.

Examples

Suppose N is 2 and K is 4. Then there are four potential A/B pairs:

A	B	magic(A,B)
(1,2)	(1,2)	3
(1,2)	(2,1)	4
(2,1)	(1,2)	4
(2,1)	(2,1)	3

So the answer is 2. Here are the other topcoder examples:

#  N  K  Return Value
-  -- -- ----------------------- 
0  1  1  1
1  2  1  4
2  3  8  18
3  10 47 13168189440000

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt, and the time of the shell script should be under 7 seconds (mine was 5.7 seconds).

Hints

Let's consider the worst case: when N is 10. Then, there are 10! = 3,628,800 permutations of the numbers from 1 to 10. We can enumerate them and stay within Topcoder's time limits; however, we can't enumerate all potential A and B, because that would be (3,628,800)*(3,628,800), which is way too big!

Fortunately, we don't have to enumerate all A and B. Let's instead just use A = { 1, 2, ..., N }, and enumerate all possible B. Suppose the number of (A,B) pairs where magic(A,B) ≥ K is equal to X. Then, I will contend that if we consider A to be any permutation of the numbers from one to N and enumerate all possible B, then the number of (A,B) pairs where magic(A,B) ≥ K will also equal X.

Let's illustrate this with an example. Suppose N is 3 and K is 8. This is example 3. Then, let's consider A = { 1, 2, 3 } and all possible B:

A         B         magic(A,B)       >= 8?
(1,2,3)   (1,2,3)   6                No
(1,2,3)   (1,3,2)   7                No
(1,2,3)   (2,1,3)   7                No
(1,2,3)   (2,3,1)   8                Yes
(1,2,3)   (3,1,2)   8                Yes
(1,2,3)   (3,2,1)   8                Yes

So, X is 3. I contend that for any single setting of A, if you look at all potential B, the number of B's for which magic(A,B) ≥ 8 is three. The reason is that there will be a one-to-correspondence betwen magic({1,2,3},B) and magic(A,B). Let me continue the example. Suppose we set A to be { 2, 1, 3 }. Then:

magic({2,1,3},{1,2,3}) is equivalent to magic({1,2,3},{2,1,3}) = 7.
magic({2,1,3},{1,3,2}) is equivalent to magic({1,2,3},{3,1,2}) = 8.
magic({2,1,3},{2,1,3}) is equivalent to magic({1,2,3},{1,2,3}) = 6.
magic({2,1,3},{2,3,1}) is equivalent to magic({1,2,3},{3,2,1}) = 8.
magic({2,1,3},{3,1,2}) is equivalent to magic({1,2,3},{1,3,2}) = 7.
magic({2,1,3},{3,2,1}) is equivalent to magic({1,2,3},{2,3,1}) = 8.

As you can see, the number (A,B) pairs such that magic(A,B) ≥ 8 is as before: 3.

What's the upshot of this? It's that you can calculate X for A = { 1, 2, 3, ..., N }, and all possible B, and that will take N! iterations. Then, you simply multiply X by (N!), because X will be the same for every permutation of A, and there are (N!) permutations.

You should program this up, and use next_permutation() from the C++ algorithms library to generate all of the permutations.