4
$\begingroup$

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?

average time in seconds for different skews

  1. Why does the egg problem algorithm perform better (as in faster on average)?
  2. 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.

$\endgroup$
  • 1
    $\begingroup$ One thing is missing in your description. What is your objective? Are you trying to minimize the expected running time, under the constraint that you always make it? Are you trying to minimize some linear combination of expected running time and failure probability? Are you trying to minimize worst case running time? $\endgroup$ – Yuval Filmus Jul 2 '17 at 9:30
  • $\begingroup$ Oh I see yeah. I did state that I want the fastest, but was not clear on best/worst cases or consistency etc. To be honest with you, I don't know. I guess the constraint is to always make it in time. But my personal main question is, why is the algorithm for the egg problem is so much faster and more consistent than the skewed binary search. $\endgroup$ – LiveOverflow Jul 2 '17 at 12:01
  • 1
    $\begingroup$ I'm not sure what kind of answer you are looking for. Two algorithms perform differently because they are different algorithms. $\endgroup$ – Yuval Filmus Jul 2 '17 at 15:43
  • $\begingroup$ Intuitively I would have thought the modified binary search solves this problem as efficiently as possible with the given time constraints. Though it turns out the algorithm from the egg problem performs better. I don't understand why. So I came up with three questions. First, why is the sweet spot for the skew at ~0.22? Second, why is the egg algorithm better, I imagined the egg problem to approach binary search the more eggs you have. And third, is the egg algorithm already the fastest one, or is there a "better" one. I guess with "better" I mean average time required to find the number. $\endgroup$ – LiveOverflow Jul 2 '17 at 16:03
  • $\begingroup$ Please edit the question to clarify your question -- don't just leave clarifications in the comments. We want questions to stand on their own, so people don't have to read the comments to understand what you are asking. Perhaps more useful questions to ask would be: what is the expected running time of the skewed binary search algorithm? You can then compare that to the running time of the egg drop algorithm (which you already know). I'm not sure it will be possible to provide a better explanation than that. $\endgroup$ – D.W. Jul 2 '17 at 17:32
1
$\begingroup$

For simplicity of analysis I will say that 'too high' is the error condition, which is just the problem inverted, $64^{64}-n$. I also assume that requests are instant.

It takes some thinking, but waiting is never an optimal strategy. So we view the problem as just a series of guesses, done in blocks of 13 (unless we hit the 90 second timeout). Instead of timeouts our penalty will be losing guesses, and instead of minimizing time we will minimize guesses used. I write $V_2$ for the value of a guess (in bits) when we are in the state where we guessed too high twice in this block. Similarly I will write $V_1, V_0$. I write $g \in \{0\dots13\}$ for the number of guesses left in the block, including the current one.

I will evaluate a strategy where we pick three numbers $p_0$, $p_1$, $p_2$, where each $p$ encodes how skewed the binary search is for when we've guessed $0$, $1$ or $2$ wrong times in this block.

The expected value (in bits) of a guess $p \in [0, 1]$ (where $0$ is the lowest guess and $1$ is the highest) is the binary entropy function $H(p) = -p \log_2 p - (1 - p)\log_2(1-p)$.

However, for $V_2(g)$, if we guess wrong we lose the rest of this block and the next two blocks, $B$ is the value of a block in bits.

$$V_2(g) = H(p_2) - 2p_2B - p_2\sum_{k=1}^{g-1}V_2(k)$$

If we write $E_2(g)$ as the value in bits of being in state $2$ with $g$ guesses left:

$$E_2(g) = \sum_{k=1}^{g} V_2(k) = \sum_{k=1}^g \big( H(p_2) - 2p_2B - p_2E_2(k-1)\big ) $$ $$E_2(g) = g(H(p_2) - 2p_2B) - p_2 \sum_{k=1}^g E_2(k-1)$$

This recurrence can be solved:

$$E_2(g) = (H(p_2)/p_2 - 2B)(1-(1 - p_2)^g)$$

Similarly, if we guess wrong for $V_1$, we lose our advantage from state $1$:

$$V_1(g) = H(p_1) - p_1(E_1(g-1) - E_2(g-1))$$ $$E_1(g) = \sum_{k=1}^{g} V_1(k) = \sum_{k=1}^{g} \big( H(p_1) - p_1(E_1(k-1) - E_2(k-1))\big )$$

$$E_1(g) = g(H(p_1) - p_1E_2(g-1)) - p_1\sum_{k=1}^{g}E_1(k-1)$$

$$E_1(g) = (H(p_1)/p_1 - E_2(g-1))(1-(1 - p_1)^g)$$

And $E_0$ is directly analogous. Now, since $B = E_0(13)$ we have:

$$E_0(g) = (H(p_0)/p_0 - E_1(g-1))(1-(1 - p_0)^g)$$ $$E_1(g) = (H(p_1)/p_1 - E_2(g-1))(1-(1 - p_1)^g)$$ $$E_2(g) = (H(p_2)/p_2 - 2E_0(13))(1-(1 - p_2)^g)$$

Oh boy... With a CAS I found:

$$E_0(13) =\frac{1}{2P_0P_1P_2 + 1} \left(\frac{P_0H(p_0)}{p_0} - \frac{P_0P_1H(p_1)}{p1} +\frac{P_0P_1P_2H(p_2)}{p_2}\right)$$

where $P_0 = 1-(1-p_0)^{13}$, $P_1 = 1-(1-p_1)^{12}$ and $P_2 = 1-(1-p_2)^{11}$. This is the expression we want to maximize.

Numerically maximizing this expression gives $E_0(13) \approx 6.72$ bits with:

$$p_0 \approx 0.1854365,\quad p_1 \approx 0.1422816,\quad p_2 \approx 0.0000899$$

This means that in order to get $\log_2(64^{64}) = 384$ bits we expect to need 57.1 blocks, or 1714.3 seconds.


This isn't even optimal yet, though. $p_0, p_1, p_2$ should actually be functions of $g$ (consider that if you are on your last guess in state $0$, then you can be really greedy and not get punished). I will see if I can improve my answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.