WinterAndSnowmen
SRM 601 · 2013-06-25 · by Witaliy
Problem Statement
It's winter time! Time for snowmen to play some games.
Two snowmen are playing a game. In this game, the first snowman must choose a subset of the set {1, 2, ..., N}, and the second one must choose a subset of the set {1, 2, ..., M}. The following two conditions must be fulfilled:
- The two sets have an empty intersection.
- The XOR of all elements in the first set is less than the XOR of all elements in the second set.
You are given two
Notes
- XOR (exclusive or) is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.
- For example 42 XOR 7 is performed as follows. First, the numbers are converted to binary: 42 is 101010 and 7 is 111. Then the shorter number is prepended with leading zeros until both numbers have the same number of digits. This means 7 becomes 000111. Then 101010 XOR 000111 = 101101 (the result has ones only in the positions where the two numbers differ). Then the result can be converted back to decimal notation. In this case 101101 = 45, so 42 XOR 7 = 45.
- The XOR of an empty set is 0.
Constraints
- N will be between 1 and 2000, inclusive.
- M will be between 1 and 2000, inclusive.
2 2 Returns: 4
The following 4 pairs of subsets are possible in this case: {} and {1} {} and {2} {} and {1, 2} {1} and {2}
1 1 Returns: 1
The only pair possible in this case is {} and {1}.
3 5 Returns: 74
7 4 Returns: 216
47 74 Returns: 962557390
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WinterAndSnowmen with a public method int getNumber(int N, int M) · 65 test cases · 2 s / 256 MB per case