A special case of a NP-Hard problem.
Problem Description:
Beelzemon gives you two integers 1 <= k <= n <= 20.
It wants to know if you can split a set
{a | -(2**n) <= a <= (2**n) - 1}
into two sets A, B s.t. |A| = |B| and
sum({a**k | a in A}) = sum({b**k | b in B}).Give Beelzemon either A or B to save your life. (separate the numbers by space)
Basically the server will repeated send you a number n and a number k. Then you need to partition the set [- 2^n , 2^n) into two sets that has the same cardinality, and so that for each set, if you raise all the elements in it to a power of k, and then sum them, the sum is the same for both sets.
This is a special case of the famous Partition Problem, which is well known to be NP-Hard. This implies that this special case will not be NP-Hard because the problem size can be as large as 2²¹.
I spend quite an amount of time drawing on the whiteboard and eventually I figured out that, give the solution to n=x, k=x, I can efficiently generate the solution of n=x+1, k=x+1. Also using a similar technique, given the solution of n=k, I can easily generate the solution of n>k. And most importantly, although this problem is looking for the power sum to be the same, I can do all these without a single power or sum operation!
To make things easier to understand and easier to prove, we shift the range to all non-negative integers first, and we will show that the partition still holds when you shift it back to half negative half non-negative.
The solution for n=1, k=1 is trivial. Let A, B denote the two sets.
// n = 1, k = 1
A = {0, 3}
B = {1, 2}To generate the solution for n=2, k=2, we take every element in B, add 4 to it and append it to A. Then we take every element in the original set A (before appending), add 4 to it and append it to set B. And we just got the solution for n=2, k=2! (You can verify that.)
// n = 2, k = 2
A = {0, 3, 5, 6}
B = {1, 2, 4, 7}Likewise, we can get the solution for n=3, k=3 by doing the same thing but instead of adding 4, we add 8 to each element to be appended.
// n = 3, k = 3
A = {0, 3, 5, 6, 9, 10, 12, 15}
B = {1, 2, 4, 7, 8, 11, 13, 14}In general, given solution for n=x, k=x, we can easily generate the solution of n=x+1, k=x+1 by adding 2^(x+1) to each element of the other set and append them to this set.
This is a proof for that:
Following a similar technique, you can prove that if you have a partition for [0, 2^(n+1)), when you shift it left to [-2^n, 2^n), it is still a valid partition. (You can prove that by shifting 1 by 1 and do induction on it.)
Now we can generate all solutions to n=k for 1 ≤ n ≤ 20. We can generate solution to n=k+1 by taking the solution to n=k, and for each set, take each of the elements, add 2^(k+1) to it and append it to the set itself.
For example, given solution to n=2, k=2, we can generate n=3, k=2:
// n = 3, k = 2
A = {0, 3, 5, 6, 8, 11, 13, 14}
B = {1, 2, 4, 7, 9, 10, 12, 15}Repeating this method we can generate all solutions for n>k! You can prove this by using a similar technique as the proof above.
Now we are able to generate all solutions to the challenge without doing a single powering or summing on the elements!
The code that we used to obtain the flag, it only takes 9 seconds to get the flag. That’s because I pre-computed all solutions for 1 ≤ n=k ≤20. It turns out that the maximum n that the server gives is only 16, if I compute n=k cases on demand and do memoization, it returns the flag in less than 3 seconds.
Here’s a screenshot:
