EQDIV - EDITORIAL

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

plz help me where i missed…
https://www.codechef.com/viewsolution/37873086

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. :+1:

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” :sweat_smile: :sweat_smile: .

3 Likes

There’s a different approach i found.

CHECK MY APPROACH : https://www.codechef.com/viewsolution/37780339

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?

I did the same ;D

1 Like

I passed this problem thanks to this post

The dp solution is intuitive. Although I could not solve, but people have simply used patterns.
Like for k=1, there is a pattern of length 4, with minimum difference in pattern 1 0 0 1
Similarly k=2, had a pattern of length 8, with difference with minimum pattern 1 0 0 1 for n>5 and the repeat for any number >16 would be. Answer of (n-8)+ pattern.
Similary k=3 had a pattern of 16 length and it repeated after 28 and k=4 had a pattern of 32 length.

How did you calculate for K = 4?