This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle.

Problem description:

• A random number N between 0 and 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815 (~3.9*10^115) is selected
• You have to find the correct number N
• You can take a guess X, and get a response whether the number X is greater or lower than N
• The twist:
• you can only perform 13 guesses in 30s without hitting a 90s timeout - 13/30
• if your guess was lower, then you get an error and you can only have 2 errors in 30s without a 90s timeout - 2/30
• you have only 2240s time to find the correct value

I had a short discussion with the challenge creator about the solution and he solved it like the broken egg problem. His algorithm basically runs in constant time - 1920s. I think the problem is not equivalent to the egg problem, but somehow the algorithm performs here really really well.

I chose a skewed binary search. Instead of splitting the search field into 50:50, I skew to one side 2/13=0.15 15:85. This way the probability of hitting the punishing error condition is pretty unlikely. My intuition tells me, that this should be the most efficient algorithm, but apparently it's not.

1. I thought the 0.15 skew would be the best ratio, but after analysing the time it takes with different ratios, the most efficient value seems to be around ~0.22. My calculation is obviously wrong, but what would have been the correct calculation to find ~0.22?

2. Why does the egg problem algorithm perform better (as in faster)?
3. What is the most efficient algorithm here, and why is it not based on a skewed binary search?

Any thoughts and comments are welcome.

This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle.

Problem description:

• A random number N between 0 and 39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815 (~3.9*10^115 or 64^64) is selected
• You have to find the correct number N
• You can take a guess X, and get a response whether the number X is greater or lower than N
• The twist:
• you can only perform 13 guesses in 30s without hitting a 90s timeout - 13/30
• if your guess was lower, then you get an error and you can only have 2 errors in 30s without a 90s timeout - 2/30
• you have only 2240s time to find the correct value

I had a short discussion with the challenge creator about the solution and he solved it like the broken egg problem. His algorithm basically runs in constant time. As max number is 64^64, he divides the problem in 64 buildings with 64 floors. And a broken egg is an error. This means it takes overall pretty constant 1920s. I think the problem is not equivalent to the egg problem, but somehow the algorithm performs here really really well.

I chose a skewed binary search. Instead of splitting the search field into 50:50, I skew to one side 2/13=0.15 15:85. This way the probability of hitting the punishing error condition is pretty unlikely. My intuition tells me, that this should be the most efficient algorithm, but apparently it's not.

1. I thought the 0.15 skew would be the best ratio, but after analysing the time it takes with different ratios, the most efficient value seems to be around ~0.22. My calculation is obviously wrong, but what would have been the correct calculation to find ~0.22?

2. Why does the egg problem algorithm perform better (as in faster on average)?
3. What is the on average fastest algorithm here? And why is it not based on a skewed binary search?

Any thoughts and comments are welcome.