SRM BrushUp: ReversalChain

We -- A friend of mine and I try the past SRMs every Sunday-- have started challenging division 1. It seems 500-pointer problems in div.1 is almost as same level as 1000-pointer problems in div.2. And I don't think they're far beyond our abilities.

Today I solved a 500 problem we were not able to solve the last weekend.

Once I read the editorial, there's nothing difficult. All you have to do is recursive and memorize return values not to exceed the time limit.

The problem is like this:

You are given two strings, init and goal.

You can choose a pair of indices{i, j}, and reverse the string init within the range of {i, j}.

Starting from init, how many times you have to do the operation above to get the string goal. Return the minimum possible value. If it's impossible return -1.

The approach to the problem is quite simple. Just check the head and the tail of each string.

If none of them have their equivalent, you cannot make the objective string.

If some have their equivalent, then move to the next recursion.

My source is like this: (It takes lots from ACRush's source code.)

class ReversalChain {
public:
    int solve(string init, string goal) {
        if (init.length() == 1) {
            if (init == goal) return 0;
            else return INF;
        }
        if (memo.count(init+"-"+goal))
            return memo[init+"-"+goal];

        int ret = INF;
        char i0 = init[0], in = init[init.length()-1];
        char g0 = goal[0], gn = goal[goal.length()-1];

        if (i0 == g0)
            ret = min(ret, solve(init.substr(1), goal.substr(1)));
        if (in == gn)
            ret = min(ret, solve(init.substr(0, init.length()-1),
                    goal.substr(0, goal.length()-1)));

        string rev = init;
        reverse(ALL(rev));
        if (i0 == gn)
            ret = min(ret, 1+solve(rev.substr(0, rev.length()-1),
                    goal.substr(0, goal.length()-1)));
        if (in == g0)
            ret = min(ret, 1+solve(rev.substr(1), goal.substr(1)));

        return memo[init+"-"+goal] = ret;
    }

    int minReversal(string init, string goal) {
        memo.clear();
        int ret = solve(init, goal);
        return ret==INF ? -1 : ret;
    }
private:
    map<string, int>memo;
};