Saturday, January 11, 2014

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.

7 comments :

vexorian said...

fun stuff: My solution is fast because there is no branching. In able0 there is only at most one move that yields (x,y) multiple of 3.

This is also what allows the "mathematical" solution. Always pick the move that turns both numbers multiple of 3.

Rafal Szymanski said...

What do you mean "undo" the first step? I can't go back to (0,0) after step 0, since in step 1 I need to move by 3, no? Also, what's in your arrays dx and dy?

vexorian said...

usual {0,0,1,-1}, {1,-1,0,0}

Undo was bad wording. It is actually doing it, but (x,y) actually represent the relative position of the objective point instead of the objective point it self.

So after making an UP move at step k, your position changes to (0,1), but the relative position changes from (x,y) to (x,y-1).

Newbie said...

Div2 medium problem was similar to Div1 easy except,in each step we could only add 3^k steps.For possible input,I formulated possible cases for x and y.Is my approach correct?

1. x=0 and y=0.

2. x=0 and y%3=0.

3. x%3=1 and y can be expressed as sum of series 3^n(geometric progression) or y%3=1 and x can be expressed as sum of G.P.


http://ideone.com/zaFFCj



P.S.-Your editorials and blog are very helpful to us beginners.Kudos!

Newbie said...

For clarity,if inputted values of x and satisfy any of these cases,the output should be 'possible',else 'impossible'.

Marco said...

Can you give me other idea for 1000 div2 problem?,.. I thought of a dynamic programming solution.


My states are curNode(current root), pos(position in curNode's adjacency list ), and k(number of foxes), So, the semantics is, How many ways I can built a connected component when "curNode" is already part of the solution and only I can give out k foxes in the curNode'subtreesChilds from pos to L[node].size() - 1???...


(Assuming that L = Adjacency list, and never visit again curNodes'parent)


It's hard to explain but this is my accepted solution http://ideone.com/sborA4 (curNode in my code is node xd)

Thanks for advance!!.

anon said...

Div1 500, try all possible ways of rooting the tree, and for each, count the minimum cost of arranging the foxes such that there is one
fox at the root.


f(i,k) : minimum cost of arranging foxes such that there are k extra foxes at the root.
g(i,k): minimum cost of arranging foxes between i and its left sibling-subtrees such that there is a fox at each of their roots (if there is a fox in the subtree) and overall there are k extra foxes on the roots.


f(i,k) = g(right(i),k+1) + k+1 if there is no fox at i,
g(right(i),k) + k otherwise.