EpicPartition

SRM 781 · 2020-03-19 · by sinus_070

SRM 781 · 2020-03-19 · by sinus_070 · Simple Math

Show categories

Class Name: EpicPartition

Return Type: String

Method Name: createPartition

Arg Types: (int)

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 6*N natural numbers. That is, S = {1, 2, ..., 6*N}. You have to partition S into three equally-large sets A, B, C. Additionally, this partition must be such that sum(C) = 2 * sum(A) = 2 * sum(B).

If there is no solution, return an empty String. Otherwise, return a String of length 6*N that describes any one valid solution. For each i, the i-th character (1-based index) of the return value should be 'a' if value i belongs to A, 'b' for B, or 'c' for C.

Constraints

N will be between 1 and 100, inclusive.

Examples

1
Returns: ""

2
Returns: ""

3
Returns: ""

4
Returns: "aaabababbbbabbcccccccaac"

A = {1,2,3,4,6,18,19,22}. Sum(A) = 75. B = {5,7,8,9,10,11,12,13}. Sum(B) = 75 C = {14,15,16,17,20,21,23,24}. Sum(C) = 150 Satisfies size(A) = 2 * 4, size(B) = 2 * 4, size(C) = 2 * 4. And union of A,B,C = {1,2,3,...6*4}. And sum(C) = 2 * sum(A) = 2 * sum(B)

5
Returns: ""

Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EpicPartition with a public method string createPartition(int N) · 100 test cases · 2 s / 256 MB per case