SRM 604: More slow

Hmnn, another SRM in which speed in 250 can break or make it for a yellow coder. And I am too slow lately... I couldn't solve 550

Div1 250: The one with powers of 3

You start at `(0,0)`, in each step `(k >= 0)`, you can add/subtract `3^k` from exactly 1 of the coordinates. Is it possible to reach `(x,y)` in any number of steps? (possibly 0?)

First of all, `(0,0)` can be reached in 0 steps, disregard this special case. Otherwise, we assume that we make at least 1 step. How about we undo the first step? The one in which we only moved by 1 unit? Try the 4 possible directions for this first step and undo them. This modifies the problem to: Can we reach `(x,y)` using steps of length `3^k`, but this time `(k > 0)` ? Now since all steps changed a coordinate by a power of 3 different to 1, then both `x` and `y` must be multiples of 3. If that isn't the case, this is invalid. Else since both `x` and `y` are multiples of 3, we can actually just divide them to by 3. This converts all moves `3^k` to `3^(k-1)` which means that the problem is now exactly as it was initially, using moves `3^0, 3^1, ....`, so we can solve it recursively.

We stop recursion whenever we reach `(0,0)` or when multiples of 3 are needed and some of `x` or `y` is not a multiple of 3. This recursion *seems* to work in time.

I tested with what I think gives the maximum number of branching: {-348678440, 116226147} and it works just fine. I think it is unlikely it will time out. But I am unsure. High coders used a completely different approach.

bool able1(int x, int y)
{
    if (x == 0 && y == 0) {
        return true;
    }
    // can we if the first step is 3, second is 9, and so and so?...
    // (all must be a power of 3) greater than 1.
    if ( (abs(x) % 3 != 0) || (abs(y) % 3 != 0) ) {
        return false;
    }
    return able0(x / 3, y / 3);
}
bool able0(int x, int y)
{
    bool good = ( (x==0) && (y==0) );
    for (int i = 0; i < 4; i++) {
        good |= able1(x + dx[i], y+dy[i]);
    }
    return good;
}

string ableToGet(int x, int y)
{
    return able0(x,y) ? "Possible" : "Impossible";
}

Div1 medium, the one with a tree

I initially thought of a dynamic programming solution, and began to code it but took too long. 5 minutes before the end of the match, I noticed some issues with this idea. It was too slow and I wasn't sure how to handle a special case.

I now think of a slightly different dp, but my thoughts are not complete.

So?

A bad day, I just hope the 250 passes system tests.