EQDIV - EDITORIAL

editorial
, , , , ,
21

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
22

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

23

Was this a programming competition or a Math Olympiad?

14 Likes
24

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.

25

Is this space left blank intentionally??

UPD: Please give an update soon, if there is an alternate explanation. Thanks in advance. :+1:

26

Which numbers can be broken down into sum of kth powers…the limit upto which dp has to be applied

27

There is no, as I am not sure at all other solution exist.

1 Like
28

It is just powers of 2, isn’t it?

29

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
31

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
32

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
33

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
34

Can you please provide me proof of why the answer would be 0 or 1 for large value of N (N>2^(k+1))

35

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.

36

This is exactly what is written in editorial.

1 Like
37

can you please explain the algorithm in detail?

38

I did the same ;D

1 Like
39

I passed this problem thanks to this post

40

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.

41

How did you calculate for K = 4?