AlienAndSetDiv2
SRM 605 · 2013-12-22 · by Witaliy
Problem Statement
Alien Fred wants to destroy the Earth. But before he does that, he wants to solve the following problem.
He has the set {1, 2, 3, ..., 2N}. He wants to split this set into two new sets A and B. The following conditions must all be satisfied:
- Each element of the original set must belong to exactly one of the sets A and B.
- The two new sets must have the same size. (I.e., each of them must contain exactly N numbers.)
- For each i from 1 to N, inclusive: Let A[i] be the i-th smallest element of A, and let B[i] be the i-th smallest element of B. The difference |A[i] - B[i]| must be less than or equal to K.
You are given the two
Constraints
- N will be between 1 and 50, inclusive.
- K will be between 1 and 10, inclusive.
2 1 Returns: 4
The initial set is {1, 2, 3, 4}. The following 6 pairs of subsets are possible in this case: A={1, 2} and B={3, 4} A={1, 3} and B={2, 4} A={1, 4} and B={2, 3} A={2, 3} and B={1, 4} A={2, 4} and B={1, 3} A={3, 4} and B={1, 2} The first option and the last option are both invalid. One of the reasons is that in both cases the difference between the smallest element in A and the smallest element in B is too large (3-1 = 2, which is more than 1). The other 4 options are valid. Note that order of the two sets matters: the option A={1,3} and B={2,4} differs from the option A={2,4} and B={1,3}.
3 1 Returns: 8
4 2 Returns: 44
10 10 Returns: 184756
10 1 Returns: 1024
Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlienAndSetDiv2 with a public method int getNumber(int N, int K) · 41 test cases · 2 s / 256 MB per case