niklasb's blog

Reconstruct contiguous sequence of numbers after digit removal
By niklasb, 11 years ago, In English

Earlier this day I came across a delightfully interesting question about an algorithm problem: http://stackoverflow.com/questions/23490944/recreate-the-sequence

Basically it asks:

Alice has written N consecutive, positive integers on a blackboard. E.g. "99, 100, 101, 102". Bob has erased all digits, but one, from each number, so the sequence now reads e.g. "9, 0, 0, 1".

So for every number in the sequence, Bob leaves over exactly one digit, and the position of that digit can vary between the numbers.

You are given the list of remaining digits and you should reconstruct the smallest starting value (in this case, 99) that could have resulted in the given sequence of digits.

OP claims there exists an algorithm. I suggested an algorithm for a starter, but I'm convinced we can do better. Any ideas?

  • Vote: I like it
  • +24
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This task appeared at the Baltic Olympiad in Informatics 2014:

http://www.boi2014.lmio.lt/tasks.html (task Sequence)

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

    Interesting. It's always hard to get the source out of the question posters, because they are often afraid that asking is against the rules of the contest (which I believe it is not in this case, because it's over). Do you happen to know the solution? Seems like only one person solved it during the contest.

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

      The basic idea in the model solution was to check all possibilities for the last digit of the first number in the original sequence (10 possibilities). Each choice yields a subproblem of size n/10 and can be solved recursively. However, I don't know the details because I haven't thought over the solution myself.

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

        Hm, maybe this brings down the constant factor of an O(n^2) solution, but I don't see how it would yield a subproblem of size n/10. I would definitely be interested in hearing more about this :)

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 4   Vote: I like it +13 Vote: I do not like it

          I hope what I understood a solution. So we check all possible last digits, then we have the subproblem of size n / 10. How we can reduce our problem to subproblem with size n / 10, with the fixed last digit? We can split our sequence by groups of size 10 (the first and the last one can be smaller, it depends on the value of the current last digit). In each of these groups some conditions will be satisfied by the last digit, and some not. But we can see what all positions which are not satisfied by the last digit, must contain the same number. So we can represent one group of size 10 using one number. I hope my explanation is not very confusing). And complexity will be O(n log n).

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

            "But we can see what all positions which are not satisfied by the last digit, must contain the same number" What do you mean by that?

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

              Let's take a sequence from 117 to 130:

              117 118 119 | 120 121 122 123 124 125 126 127 128 129 | 130

              Note that within every group of 10 (I divided them with |), the only digit that changes is the last one. So let's say we fix the last digit and remove all digits that are satisfied by it, in the second group every '2' that remains can be related to the second digit, and every '1' can be obtained by taking the first digit.

              In other words, for every group, the exact sequence of digits is irrelevant. We only care whether a certain digit appears in it or not.

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

                Ah and then we have a subproblem after collapsing every group into a single value, but it's not quite the same problem as the original. In fact we might have more than one digit. Makes sense :) This looks very good.

                → Reply