wfe2017's blog

IOI 2016 practice task — Martian dna
By wfe2017, history, 8 years ago, In English

Does anyone have a solution to this problem, even just for part b?

The question is basically (for the highest sub-task) that you have to decode a length 1000 binary string, and you have 1024 queries of the form "is substring S present", on which an answer of Yes or No will be given.

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Here's a quick sketch of my 100 point solution (n+2*log(n) queries):

If there's no 0 inside the string the answer is just n 1s. Otherwise we can find the longest continuous 0 string using binary search (let's say this string has length l). Now starting from this string let's try to extend it to the right: Check if we can append a 1 — if that doesn't work, just take a 0 for now. In case we've appended more than l continuous 0s we're definitely out of bound (that is, beyond the right end). Once that happens we can apply another binary search to check how far off we actually are (how many 0s are actually needed). It just remains to extend our string on the left side. But that is simple, given that we know the number of characters needed.

I hope that gives you a general idea.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice solution! But lets S = "111..(50)" + "000..(100)" + "111..(850)". So you will find that there 100 zeros, then you will add 1 850 times, then start getting NO answers and add zeros 100 times, then binary search and adding left part of S, so you will have 850 + 100 + 150 queries + binary search. Don't I understood something or it's really a problem?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I agree that his solution will have a problem in this case.

      Also, I don't find it clear how is this done:

      "But that is simple, given that we know the number of characters needed."

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Growing the string to the left is easy, because if you have the suffix S from the first part you can query 0S and know if the previous character is 0 or 1.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Hmmm... how do you know for sure?

          If you query 0S and answer is "YES", how are you sure that the suffix is 0S, or the 0S just appeared somewhere in front?

          Please correct me if I'm wrong — as you can see, I'm just blue and you're red

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You start adding ones to the string 0000... (100), so the solution needs 850 + 100 + 50 + 2 binary search moves.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks for the clarification, but I still don't understand how to

        "It just remains to extend our string on the left side".

        how do you extend our string on the left side (given that we have the right side prefix).

        For example, if we know that our last 450 characters (different example!) are 00..00 (150) and 11...11 (300). A natural way to figure out the 452th-to-the-last character is by testing 1100..00 [150] 11..11 [300]. But you don't know if this is referring to the last 452 characters or just another continguous substring of 452 characters that happen to be the same (not necessarily at the end).

        At least, we reduced the problem to "given a 1000-length string with suffix x with length k, find the remaining 1000-k letters with around 1000-k moves (you don't have much allowance here, sadly, maybe give or take one or two)"

        Essentially, I'm still confused on how to do the last step (after the two binary searches) — finding the remaining after knowing the suffix as well as the length of the longest string of consecutive zeroes.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          To elaborate more: Suppose you have a 16-string, and you know that the longest consecutive sequence of zeroes is of length 3, and the suffix is 000101. Now we have to construct the first 10. Logically, we get that the last 7 are 1000101.

          How do we construct the first 10, then? The first algo that comes to my mind is to check 01000101, and if this does not work, we assume that the last 8 are 11000101. The harder part, though, is if this works, i.e. 01000101 returns "YES". The problem here is that the 16-string 0100010111000101 also has the substring "01000101". Maybe the algo I'm thinking isn't the correct / the one that vlad8 had in mind, though.

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          you don't know if this is referring to the last 452 characters or just another continguous substring of 452 characters that happen to be the same (not necessarily at the end)

          It necessarily is at the end, due to how the first part works. The first part ends when you can't extend the suffix anymore. If this substring occurred somewhere else, you would have been able to extend the suffix in the first part.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for your clarification. I get it already!

            → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you have an AC code for this? It'll really help. Thanks again!

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Ignore

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If I correctly understood problem statement the solution is follow: 1) Ask if "1" in S 2) If YES ask if "11" in S else ask if "01" in S 3) And do so, each time having NO answer swap last symbol, it's easy to see that we will decode such way, but there's one problem — when we get end of the string we won't know it. So you have to score NO and when you get 12 NO in row you should start deleting symbols one be one to know where is the end of string 4) And for this strategy you will decode correctly every time if there's no "000000000000" substring in S. So maybe it's better to add random symbol every time It's all. Does anyone has no-randomized algorithm?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem is that there is a roughly 1/4 chance for there to be a 000000000000 in S. (just a rough estimate)

    and the judges would obviously guard against such a solution by using a trivial 00.000 testcase.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      instead of always querying S+'0', you should with probability 0.5 ask S+'0' and with probability 0.5 ask S+'1', in this case if you get 19 consecutive 'NO's then with high probability you reached the end in the last 19 moves, you need only 5 queries to do binary search to get where is the end exactly, so this is only 19+5=24 extra queries.

      I have calculated the probability of failure on a single test-case, it is approximately 0.0009

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        It is nowhere mentioned that the system has to choose a string beforehand. It can adapt its string to your questions, hence no probabilistic solution should pass.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          in this case, as yeputons said in this comment, if they will not actually hide a fixed string they should mention that explicitly in the statement to make it more fair, specially if the story of the problem suggests that string is fixed for example if the story about finding the DNA of a creature, but if for example the story is about Alice and Bob are playing a game then Alice or bob might cheat in clever way.

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How would you generate adversarial answers in this particular case (short of reversing the rng)?

          → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How did you get the practice task? Please share the link.

→ Reply