SRM 615: Recursive, recursive

Already reached the half of this python experiment. This time , python hasn't really helped me and it wasn't an obstacle either. Quite mundane, really.

Div1 250: The one with ameba

First of all, this is a 7:00 AM match so I had a bit of issues getting brain to work at first. I didn't really understand the statement very well initially. Then the problem itself is quite special, ad hoc and cool. So it took a while. Even so, I was surprised when it turned out that tons of people had a much better score than I.

The problem (after tons of translation) is as follows:

An amoeba has size `s` , a integer. There is a list `X` of amounts of gel it met in chronologically order, so first it met `X[0]` gel, then `X[1]` gel, etc. `X` has at most 200 elements. Whenever the amoeba meets a gel with size exactly equal to its current size `s`. The ameoba is forced to eat the gel and thus double its size. `s' = 2s`. We don't know the initial size `s_0`, but we wonder how many integers `u` exist such that the final size of the ameoba cannot be equal to `u`.

All integers that do not belong to `X` are possible final sizes. For example, take a integer `a` that is not in `X` and make it the starting size. Since none of the gels the amoeba will meet is exactly `a`, the amoeba will never double its size and the final size is `a`.

So we should only care about the integers that are already in `X`. For each of those integers, answer: "Can the final size be equal to `X[i]`?".

Given a integer `a`, how do you know if it is a possible final size? Focus on the last integer in the sequence: `X[n-1]`. There are two possibilities in which the final size is `a`:

• The size was already equal to `a` before the amoeba met gel `X[n-1]` and the amoeba didn't eat it. This requires two conditions to be true:
  • `a != X[n-1]`, because the amoeba must not eat it.
  • It is possible for the amoeba to reach size `a` after meeting the first `n-1` gels.
• The size of the amoeba became `a` after meeting `X[n-1]`:
  • This means that `2X[n-1] = a`.
  • And also `X[i]` should be a possible size after meeting the first `n-1` gels.

So we have a recursive idea. The issue is that `n = 200`, so let's get clever. First find the set of impossible integers for the first 1 elements (easy), then use that set to build the set of impossible integers for the first 2 elements, then the first 3 elements and so and so. E.g: If you know the set of impossible elements for the first `n-1` elements, it is easy to know if `a` or `X[i]` are impossible or not to have after meeting the first `n-1` elements. This yields an `O(n^2log(n))` solution if you use a logarithmic set or `O(n^2)` if you use a hash table.

class AmebaDiv1:
 def count(self, X):
    impossible = { X[0] }
    for i in range(1, len(X)):
        impossible2 = set()
        # which are impossible for X[:i+1] ?
        for j in xrange(0,i+1):
            a = X[j]
            # is a possible?
            # a) ignore X[i],
            poss = False
            if X[i] != a and a not in impossible:
                poss = True
            # b) use X[i] to double
            if 2*X[i] == a and X[i] not in impossible:
                poss = True
            if not poss:
                impossible2.add(a)
        impossible = impossible2
    
    return len(impossible)

So I said python didn't help that much. It is a very procedural algorithm and well, I think that if I did it in c++ it would take the same amount of lines. There are possibly much better python implementations.

The rest

Tried the other problems, not very thrilled about having to write editorial because div1 550 seems hard and div1 950 is incredibly complex in what it asks for. Currently waiting for the challenge phase to end. Blog post will be posted automatically once it does so.

While watching the challenge phase, I learned a new solution and the reason everyone had such fast scores. Remember that either `a` is possible in the first `n-1` or `X[i]` is possible. It follows that the only starting integers you should try and simulate are those already in `X[i]`, if you test each of those integers as the starting one, you can easily find which `X[i]` are possible. The solution is then to simply do that.