EasyPartition
SRM 781 · 2020-03-19 · by sinus_070
Problem Statement
Ramanujan loved partitions. And he also loved natural numbers. So, yay! He has a problem for you.
The set S consists of the first 8*N natural numbers: S = { 1, 2, 3, ..., 8*N }. You have to find a subset W of S with the following properties:
- W contains exactly 2*N numbers.
- The sum of W is 4*N*N.
If there is a subset W satisfying the mentioned condition, find any one such subset. Return a string of size 8*N, where the ith character (1-indexed) is '1' if i belongs to W, and '0' otherwise. Any valid solution will be accepted.
Return an empty string if it is impossible to construct a valid subset for the given N.
Notes
- W is a subset of S, hence all elements of W must be distinct.
Constraints
- N will be between 1 and 50, inclusive.
1 Returns: "10100000"
W = {1,3} satisfies our conditions.
2 Returns: "0110110000000000"
4 * N * N = 16. W={2,3,5,7} Other possible solutions are {1,3,5,7}, {1,2,6,7}, {1,2,5,8} etc.
3 Returns: "010110110100000000000000"
W = {2,4,5,7,8,10} satisfies.
4 Returns: "01010110110101000000000000000000"
5 Returns: "0101010110110101010000000000000000000000"
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EasyPartition with a public method string getPartition(int N) · 50 test cases · 2 s / 256 MB per case