Tryss wrote:

Yeah, problems 1 & 2 were a joke, you don't even need a computer to solve them.

For the problem 1, 165498416436549879654 = 000200200200020000002 + 165298216236529879652 , For the fisrt number, replace all non 4 by 0 and all 4 by 2, and for the 2nd number, all 4 by 2

For the problem 2, EEESSESSSEEESSSSESS -> SSSEESEEESSSEEEESEE , Invert the S and E

Third problem was more interesting, even if the easy case could be "bruteforced" (you could test all prime numbers in the range). There still possible complications if it start by something like ABABCDE.

Hmm, I also thought problem 2 was trivial, but your solution is even simpler than mine.

For problem 3 the trick was to realize that if you have A*B and B*C, you can use the GCD algorithm to get B. From there you can get all the other primes just through division. It gets a little tricky beceause you might have the plaintext starting with something like "CCCCC" or "ABABABAB", so you have to look for the point in the ciphertext where you have two different numbers, do the GCD once, and work forwards and backwards. The main problem I had was that they wouldn't link my C++ program with libgmp, so I rolled my own string-based bignum division. Ugh.

For Problem 4 I only got the first set of inputs right. It's a binary search. Let's say you are testing eight bits: you send 11110000, and after the response you will know exactly how many bits are missing in the first and in the second half. So, repeat again with 11001100 and so on. That gets the job done exactly in the number of steps allowed.

I suppose you could do better: if you know that there are at most 3 bits missing, you might be able to send 11100011. Now you have three sub-regions, and would still be able to work out from the response what's going on inside them. But I couldn't quite convince myself that this would be good enough in all cases and didn't submit a solution.