SRM 574: Stupid "dp sense"

It has been a long week, I got chicken pox and had to wait a week to get better. I was lucky that there were no SRMs or anything important going on school-wise during this week. But it was still quite awful and boring.

I had some difficulties starting up the arena, was the first time in a week I used my big computer. And it was acting up. I could only open the medium problem around 10 minutes late...

Div1 450: The one with a polygon

You have a polygon of at most 18 points. Numbered in clockwise order from 1 to 18. A guy drew segments visiting points: points[0], points[1], ... , etc. You have to complete the tour of points so that all points in the polygon are visited, and the last segment finishes back to points[0]. So for example you will use segments: points[0] -> points[1] -> points[2] -> -> x > y > z > points[0]. Each point must belong to exactly two segments. And each of the new segments you add must cross a previous segment.

For most of the time I was thinking that with N <= 18, the solution was exponential dp: O(N * (2^N)). The slight issue was how to find out, from just the set of already-visited points, whether or not a new segment you add will cross an already visited segment.

Turns out that it was not so hard. Let us say you currently are at point p, and that you have a set mask of points that were already visited. Can you create a segment between p and another point q? The segment p -> q will split the polygon in two parts. The trick is that if each of the two parts contains points that where already visited, then (p -> q) will intersect with something, and if either of the parts does not contain a visited point, then (p -> q) will not intersect anything. The demonstration relies on the fact that all points that were already visited HAVE to be connected, so if these two parts contained visited points, there has to be a connection between the parts.

using namespace std;
typedef long long int64;
#define long int64

struct PolygonTraversal
{
    vector<int> points;
    long dp[1<<18][18];
    
    long rec(int N, int mask, int p)
    {
        long & res = dp[mask][p];
        if (res == -1) {
            if (__builtin_popcount(mask) == N) {
                int d1 = ( (points[0]-1) - p + N) % N;
                int d2 = (p - (points[0]-1) + N) % N;
                res = ( d1 != 1 && d2 != 1);
            } else {
                res = 0;
                for (int q=0; q<p; q++) {
                    if ( ! (mask & (1<<q) ) ) {
                        // q+1, q+2, ... p-1
                        int side1 = ( ( ( 1<<(p - q - 1) ) - 1) << (q+1));
                        int side2 = ( (1<<N)-1 ) - side1 - (1<<p) - (1<<q) ;
                        if ( (side1&mask) && (side2&mask)) {
                            res += rec(N, mask | (1<<q), q);
                        }
                    }
                }
                for (int q=p+1; q<N; q++) {
                    if ( ! (mask & (1<<q) ) ) {
                        int side1 = ( ( ( 1<<(q - p - 1) ) - 1) << (p+1) );
                        int side2 = ( (1<<N)-1 ) - side1 - (1<<p) - (1<<q) ;
                        if ( (side1&mask) && (side2&mask)) {
                            res += rec(N, mask | (1<<q), q);
                        }
                    }
                }
            }
        }
        return res;
    }
    
    long count(int N, vector <int> points)
    {
        this->points = points;
        memset(dp, -1, sizeof(dp));
        int mask = 0;
        for (int i=0; i<points.size(); i++) {
            mask |= ( 1 << (points[i]-1) );
        }
        return rec(N, mask, (*points.rbegin()) - 1 );
    }
};
#undef long

So we can use a dynamic programming approach with state (p, mask) p, is the current point and mask the set of already-visited points. There is a catch, and it is that you need to verify if the two parts split by q are correct without using an extra loop. It is possible with bit operations if you are clever...

Div1 275: The one with the number game

I tried to solve div1 1050, seemed hard. So I waited till there were 10 minutes left before opening div1 275. After looking to the division scores, it seemed unlikely I would be able to solve this problem in under 10 minutes, but I have to be consistent with my strategy if I want to improve...

Two guys are playing a game. Each guy has a string (number) of up to 9 characters. In each turn, a player can either reverse his string, or remove the last character from it (divide the number by 10). The first player wins if the two strings become equal at any point of the game before 1000 turns. If after 1000 turns, the strings are still not equal, the first player loses.

After doing contests, specially TopCoder contests for a while, you develop a "dp sense" you can quickly notice when a problem can be solved using dynamic programming. And this is one of those problems. But I also knew that the dynamic programming approach would have been very long to code. I also suspected there was going to be a simpler approach... But with 10 minutes, I didn't have much time to think (I think I was wrong, it was possible to think of the simpler, faster to code approach in 10 minutes, I think). So I started coding the dynamic programming approach. I was too slow. I could only finish debugging it after the intermission phase...

string sa, sb;
char dp[1002][9][10][9][10][2][2];

bool rec(int t, int a1, int a2, int b1, int b2, int ad, int bd)
{
    char & res = dp[t][a1][a2][b1][b2][ad][bd];
    if (res == -1) {
        // compare
        res = 0;
        if (a2 - a1 == b2 - b1) {
            res = 1;
            for (int i=0; i < a2 - a1; i++) {
                char ch1 = sa[a1 + i];
                char ch2;
                if (ad ^ bd) {
                    ch2 = sb[ b2 - 1 - i];
                } else {
                    ch2 = sb[ b1 + i];
                }
                res &= (ch1 == ch2);
            }
        }
        if (res != 1) {
            if (t < 1001) {
                if (t % 2 == 1) {
                    if( (a1 != a2) ) {
                        if (!ad) {
                            res |= rec(t+1, a1, a2-1, b1,b2, ad,bd);
                        } else {
                            res |= rec(t+1, a1+1, a2, b1,b2, ad,bd);
                        }
                    }
                    res |= rec(t+1, a1, a2, b1,b2, !ad,bd);
                } else {
                    res = 1;
                    if( (b1 != b2) ) {
                        if (!bd) {
                            res &= rec(t+1, a1, a2, b1,b2-1, ad,bd);
                        } else {
                            res &= rec(t+1, a1, a2, b1+1,b2, ad,bd);
                        }
                    }
                    res &= rec(t+1, a1, a2, b1,b2, ad,!bd);
                }
            }
        }
    }
    return res;
}

string determineOutcome(int A, int B)
{
    { ostringstream st; st << A; sa = st.str(); }
    { ostringstream st; st << B; sb = st.str(); }
    memset(dp, -1, sizeof(dp));
    return rec(1,0,sa.length(), 0, sb.length(), 0,0) ? "Manao wins" : "Manao loses";
}

As you can see, the approach is VERY complicated.

The simpler approach is nicer: 1000 steps is a lot of time. It is enough for player 1 to remove all of the digits of the string. (Note that at any time, the strings in the game are substrings (possibly reversed) of the original strings).

Imagine if the second player's string (or its reverse) was a substring of the first player's string. The first player can eventually remove enough characters. The second player cannot stop the first player from winning. If the second player removes a character, the second string will still be a substring. If it is reversed, it will also still be a substring. The first player will eventually be able to remove enough characters and reverse if necessary.

In the other case, if the second player's string is not a substring and neither a reverse of a substring of the first player's string, the second player can just constantly reverse his own string. The first player can never reach a good string, because the second player will always have some extra characters.

A STL implementation of this solution looks like this:

string determineOutcome(int A, int B)
{
    string s, t;
    { ostringstream st; st<<A; s = st.str(); }
    { ostringstream st; st<<B; t = st.str(); }
    bool r = 0;
    if ( s.find(t) != string::npos ) {
        r = 1;
    }
    reverse(t.begin(), t.end());
    if ( s.find(t) != string::npos ) {
        r = 1;
    }        
    return (r ? "Manao wins" : "Manao loses" );
}

Outcome, Comments? Etc.

I passed div1 450. I got 38 rating points. It is nice that I am actually winning rating points using the "suicidal" strategy. This was a good problem set, although I think the unusual problem scores were not necessary.