Will You Please provide a test case for k=2 where it fails so that I can understand it more.
1 Like
This was a good problem…i was very close to this…well i tried my best…
2 Likes
Its a prank i guess XD 
1 Like
@longtimenoshe2 @bohdan Okay Got it 
Actually I was greedily grouping no.s which will work only in case of k=1 because there all no.s are continuous (1,2,3,…,n).
But that solution won’t work for other values of k like for k=2 (1,4,9,16,25,…) because In that case no.s are not continuous so can’t do grouping greedily
1 Like
I figured out that pattern and then I precalculated small values.
def solve_2():
array = [[0, ''], [1, '0'], [3, '01'], [4, '001'], [2, '0001'], [3, '01001'], [1, '001001'], [0, '0010110'],
[0, '01101001'], [1, '000011001'], [1, '0100100101'], [0, '01000111010'], [0, '000000001101'],
[1, '0000000110110'], [1, '00000011100110'], [0, '000000101011001'], [0, '0000100011100110'],
[1, '00000000111011100'], [1, '000000000001110110'], [0, '0000000001001111100'],
[0, '00000000001011100101']]
for _ in range(int(input())):
N = int(input())
if N <= 20:
print(array[N][0])
print(array[N][1])
else:
rem = N % 8
rem += 8
q = (N - rem) // 8
print(array[rem][0])
print(array[rem][1] + '01101001' * q)
def solve_3():
array = [[0, ''], [1, '0'], [7, '01'], [18, '001'], [28, '0001'], [25, '00001'], [7, '010001'], [26, '0001110'],
[4, '00110110'], [5, '011010110'], [1, '0000000101'], [12, '00001101001'], [0, '001011100110'],
[1, '0000010000011'], [1, '01011001101001'], [0, '001011001101001'], [0, '0110100110010110'],
[1, '00010110111110010'], [1, '010011010101011010'], [0, '0011001001011000011'],
[0, '00000001010101100110'], [1, '000010010010110010110'], [1, '0000000000000001000111'],
[0, '00000000011010001100011'], [0, '000000000000101011110001'], [1, '0000000000001101011110010'],
[1, '00000000001101001101101010'], [0, '000000000001001111110111000'], [0, '0000000000100100010010110110'],
[1, '00000000000001101000001111001'], [1, '000000000001000011010011011010'],
[0, '0000000000011001101001010001011']]
for _ in range(int(input())):
N = int(input())
if N < 32:
print(array[N][0])
print(array[N][1])
else:
rem = N % 16
rem += 16
q = (N - rem) // 16
print(array[rem][0])
print(array[rem][1] + '0110100110010110' * q)
def solve_4():
final = {1: [1, '0'], 2: [15, '01'], 3: [64, '001'], 4: [158, '0001'], 5: [271, '00001'], 6: [317, '000001'], 7: [126, '0000001'], 8: [34, '00101110'], 9: [253, '000001110'], 10: [13, '0101001001'], 11: [92, '00000101001'], 12: [30, '001101010110'], 13: [47, '0010110101001'], 14: [31, '00000001111010'], 15: [2, '011110001010110'], 16: [0, '0000111000001110'], 17: [1, '00000010110010110'], 18: [13, '000000110100001110'], 19: [0, '0001100111111001001'], 20: [0, '00001010110111011100'], 21: [9, '000000000100100100011'], 22: [1, '0000100101101110000011'], 23: [0, '00000011011000111011100'], 24: [0, '000000100111111111100001'], 25: [1, '0000000010101011110000011'], 26: [5, '00010100000100010000110101'], 27: [0, '000000101010110011001101001'], 28: [0, '0000000010001100101111111000'], 29: [5, '11101111111011001110111010001'], 30: [1, '000000000010100011011110101100'], 31: [0, '0000000000001011111101111010100'], 32: [0, '01101001100101101001011001101001'], 33: [1, '001101001100101101001011001101001'], 34: [1, '1010101110111111111011101111101000'], 35: [0, '01000111001011010111111101111110000'], 36: [0, '000000000000100001111011111010111000'], 37: [1, '1111111010111011111110111111111000100'], 38: [1, '10010100100101011111110111111101110000'], 39: [0, '000000100100010111110111111111111010000'], 40: [0, '0000001001001100010111111111111111100000'], 41: [1, '01000101010110011111111111011111111100000'], 42: [1, '011111101111111010111110101111111111100000'], 43: [0, '0001010011000001110111111111111011111100000'], 44: [0, '00000100000101011110111111111111110111100000'], 45: [1, '001111101111101111111010111111111110111100000'], 46: [1, '0110010100010101010110111111111111111101100000'], 47: [0, '01010100000101010111101111111111111111111000000'], 48: [0, '000011100000111001101001100101101001011001101001'], 49: [1, '0000001011001011001101001100101101001011001101001'], 50:[1, '01010100000100000000010101010001010101000111101010'], 51: [0, '000110011111100100101101001100101101001011001101001'], 52: [0, '0000101011011101110001101001100101101001011001101001'], 53:[1, '00110000100001100001000101010011000101010001010101110'], 54: [1, '000010010110111000001101101001100101101001011001101001'], 55: [0, '0000001101100011101110001101001100101101001011001101001'], 56: [0, '00000010011111111110000101101001100101101001011001101001'], 57: [1, '000000001010101111000001101101001100101101001011001101001'],58:[1, '1111001100000000000001010001000110010111110101010001010101'], 59: [0, '00000010101011001100110100101101001100101101001011001101001'], 60: [0, '000000001000110010111111100001101001100101101001011001101001'],61:[1, '1010100010010010000011010000010101010101000101010101110101010'], 62: [1, '00000000001010001101111010110001101001100101101001011001101001'], 63: [0, '000000000000101111110111101010001101001100101101001011001101001'], 64: [0, '0110100110010110100101100110100101101001100101101001011001101001']}
for _ in range(int(input())):
N = int(input())
if N < 64:
print(final[N][0])
print(final[N][1])
else:
rem = N % 32
rem += 32
q = (N - rem) // 32
print(final[rem][0])
print(final[rem][1] + '01101001100101101001011001101001' * q)
K = int(input())
if K == 1:
solve_1()
elif K == 2:
solve_2()
elif K == 3:
solve_3()
else:
solve_4()
`
7 Likes
Was this a programming competition or a Math Olympiad?
14 Likes
Can someone please tell why this isn’t working for k=2?
https://www.codechef.com/viewsolution/37492022
Im giving n^k to A then till B doesn’t exceed A, give everything to B then again to A and so on .
Ik its a greedy solution but I can’t figure out a TC where it wouldn’t work for k=2.
Is this space left blank intentionally??
UPD: Please give an update soon, if there is an alternate explanation. Thanks in advance. 
Which numbers can be broken down into sum of kth powers…the limit upto which dp has to be applied
There is no, as I am not sure at all other solution exist.
1 Like
It is just powers of 2, isn’t it?
From mine point of view, almost every competitive programming problem is more or less math related (besides data structure problems, but putting more than 1-2 DS problems to contest is very strange for me). So what’s the point of your comment?
6 Likes
I am sorry if it was pointless, actually, I was quite surprised to see a lot of math in this contest.
This long was really “long” 
.
3 Likes
There’s a different approach i found.
CHECK MY APPROACH : CodeChef: Practical coding for everyone
I just made a recursive program to find best solution and the found pattern in the solution. But for k =4, i couldn’t figure out some numbers.
1 Like
It is not different, it is the same, just with hardcoding everything ( I guess your recursion is either bruteforce or similar to dp).
1 Like
Can you please provide me proof of why the answer would be 0 or 1 for large value of N (N>2^(k+1))
This sequence may be used to find how can the Kth powers of any 2K+1 consecutive numbers be divided into two groups such that both the groups have equal sum.
This is exactly what is written in editorial.
1 Like
can you please explain the algorithm in detail?