Problem 364988 · hard · Level 03 Linear Management & Searching

The Witness Who May Lie Once

binary search · interactive · searching with errors · potential function

A detective knows that the code to a safe is a whole number between 1 and n. A witness knows the code and answers questions of one kind: at_most(k) is the witness's answer to "is the code at most k?" (True or False). The witness may lie once: at most one answer in the whole interview is false, and you are not told which one, or whether there was one at all.

Write find_secret(n, at_most, limit) that returns the code. You may ask at most limit questions, where limit is the smallest q with n * (q + 1) <= 2**q, plus one (it is passed to you; for example limit is 8 for n = 10 and 37 for n = 10**9). One question too many raises TooManyQuestions. Asking every question twice or three times does not fit.

The tests run with_witness(find_secret, n, seed, style) with one of three witnesses:

  • "honest" never lies;
  • "once" lies on one question, chosen at random;
  • "cunning" has not fixed the code: it picks each answer to make your job as hard as possible, keeping only the promise that some code fits all its answers with at most one of them false. When you answer, it names a code that fits and differs from yours if one exists. So your answer must be the only number that fits the answers with at most one lie.

Try it with Run: print(with_witness(find_secret, 100, 1, "cunning")).

Examples

Input:  with_witness(find_secret, 10, 1, "honest")   (limit 8)
Output: {"answer": ..., "questions": ..., "limit": 8, "secret": ..., "style": "honest", "witness_lied": False}
        correct when answer == secret

Input:  with_witness(find_secret, 1, 2, "cunning")   (only one possible code; limit 1)
Output: {"answer": 1, "questions": 0, "limit": 1, "secret": 1, "style": "cunning", "witness_lied": False}

Constraints

  • 1 <= n <= 10**9
  • at most limit questions (limit as above); k must be an integer
  • the witnesses use their own random generator seeded by the test, never the clock

Goals

  • Search when one answer may be false, without paying for every answer twice
  • Use a weight that is conserved by every question to choose the next question
  • Prove a lower bound on the number of questions any strategy needs
Starting Python…