Tags: ppc

Rating:

# Hitcon 2016 Quals - Beelzemon
### PPC - 150 pts

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)

This problem is pretty easy to understand. We got this set : ![set](ensemble.gif) and we need to split it in two part of same size in order to follow the rule ![rule](condition.gif)

This partition problem is well known and we can find many solutions for positive sets (i.e all elements in the set are >= 0)
Therefore we take the following algorithm and will change it a bit :
python
def find_partition(int_list):
"returns: An attempt at a partition of int_list into two sets of equal sum"
A = set()
B = set()
for n in sorted(int_list, reverse=True):
if sum(A) < sum(B):
else:
return (A, B)


Here we are gonna make the split on modified sets, we elevate every element of the int_list to the power of k
Then, to avoid the problem of non positive elements in this algorithm we add ![2^n](2n.gif) to every element in the int_list
Due to the shape of the input set (being a range of integers without missing numbers in between), making equal size sets is pretty straightforward. We just need to put the last element (which will add 0 to the sum and therefore change nothing in our partition) to the partition having the less elements to make equal size partitions.

This problem takes a certain amount of time when (n,k) equals (16,16) but nothing impossible. My algorithm gets the flag in about 9 minutes. This is a lot, and yes a C++ implementation could be faster, but that's not too much here. *(Edit : process is a lot faster now thanks to elbae. It takes about 10 seconds)*

Here is the final code giving us the flag we want :
python
'''
Pod for Team Fourchette Bombe
'''
import socket
import re
import operator
import time

def find_partition(int_list,n,k):
len_A=0; len_B=0; sum_A=0; sum_B=0
Aret = ""; Bret = ""

for i in range(0,len(int_list)):
int_list[i] += 2**n
int_list=int_list[::-1]
for nb in int_list:
if nb == 0:
if len_A < len_B:
len_A+=1
Aret+= str(-2**n)+ " "
else:
len_B+=1
Bret+= str(-2**n)+ " "
else:
if sum_A < sum_B:
sum_A+=(nb**k)
len_A+=1
Aret+=str(nb-(2**n))+ " "
else:
sum_B+=(nb**k)
len_B+=1
Bret+=str(nb-(2**n))+ " "
return (Aret)

def main():
begin = time.time()
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('52.198.217.117', 6666))
while True:
data = s.recv(2048)
if len(repr(data)) <=2 :
break;
mgex = re.search('([0-9]+) ([0-9]+)', repr(data))
if mgex != None:
n = long(mgex.group(1));
k = long(mgex.group(2));
mySet = range(-2**n,2**n);
partition = find_partition(mySet,n,k)
s.send(partition+'\n');

print "Connection closed."
s.close()
print "Process duration :", time.time() - begin

main()


And this process gives us the flag : hitcon{8Ee121m0n kNow3 ev1l Num8e2}

*EDIT : Thanks to elbae for his remark concerning time improvement. As I said, I did not search much for improvement as far as it was still reasonable. But with more cases to perform, this improvement could have been a must have to flag this challenge !*

Original writeup (https://github.com/JulesDT/ctfWriteUps/tree/master/Hitcon%20Quals%202016/Beelzemon%20-%20PPC%20-%20150%20pts).