No more link spam, for now

It seems that feedly is sort of a good replacement for google reader. It actually uses google reader as a back end, and it seems that the sharing feature is still accessible through external services. Lo, and behold, the external picks tab is back and my biased links will no longer plague the blog's feed.

Update: Lol, now feedly has stopped allowing sharing. That's right, just 4 days after I began using their service, they removed exactly the one reason that made me use them.

It is a relief to be honest, I wasn't getting used to their interface. It has tons of issues like requiring tons of clicks and not allowing you to setup a default format option.

SRM 526: The killing wait for results

While I wait for results, here is my perspective on this algorithm contest.

It began with issues, it had to be postponed 15 minutes. TC has been misbehaving in the technical side lately.

So, let us return to a simple contest with the usual strategy to try to solve the medium problem first.

Div1 500: PrimeCompositeGame

Let us begin with a dynamic programming solution that runs in O(N*K) time. It is kind of standard but is not fast enough. The good news is that it is possible to turn it into O(N*log(N)).

It is the usual game theory approach for dynamic programming. Let us think of a recurrence F(T, N), it will give the result (negative # of steps if first player loses, positive if he wins) in the sub-case where it is Player T's turn (for convenience the first player is player 0, and the second is 1). If there are N stones.

To evaluate a given state F(T, N), pick all the K possibilities of the stones to remove (You can remove from 1 to K stones). And find F( !T, N - removed_amount). Then player #T would pick the most convenient number of rocks to remove based on that solution. Note that some of the moves are not valid and if no valid moves exist, the player just lost.

We now need to turn it into O(N*log(N)). Just notice that when solving F(T, N), we need to consider the previous values F(! T, x) where x is between (N-K and N-1). Of them, we would need to find, depending on the player , the values of F(!T, x) that are negative or positive and also depending of the player, the maximum and minimum of those values. By using a std::set you can do this if you add the appropriate values to the appropriate set after each evaluation for a value of N. Just make sure to remove values of x that are smaller than N-K if you find them.

The following code is awful and could get plenty of fixes, but it shows the idea, I think.

bool iscomposite[474748]; 
int  dp[2][474748]; 
struct PrimeCompositeGame 
{ 
    int theOutcome(int N, int K) 
    { 
        memset(iscomposite,0, sizeof(iscomposite)); 
        for (int i=2; i<=N; i++) { 
            if (! iscomposite[i]) { 
                for (int j=i+i; j<=N; j+=i) { 
                     iscomposite[j] = true; 
                } 
            } 
        } 
        dp[0][1] = -1; 
        dp[1][1] =  1; 
 
                        
        set< pair<int,int> > primePositive[2]; 
        set< pair<int,int> > primeNegative[2]; 
        set< pair<int,int> > compoPositive[2]; 
        set< pair<int,int> > compoNegative[2]; 
 
        for (int n=2; n<=N; n++) { 
         for (int cplayer=0; cplayer<2; cplayer++) { 
            //player 0 
            if (cplayer==0) { 
                    //look for a positive dp[!cplayer][x] in the range n-K <= x <= n-1 
                    // if it exists, return the minimum. 
                    bool found = false; 
                    int pick = 0; 
                    { 
                        set< pair<int,int> > & tm = primePositive[!cplayer]; 
                        while(! tm.empty() ) { 
                            set<pair<int,int> >::iterator q = tm.begin(); 
                            if ( q->second < n-K ) { 
                                tm.erase(q); 
                            } else { 
                                found = true; 
                                pick = q->second; 
                                break; 
                            } 
                        } 
                    } 
                     
                    // if it does not exist, return the minimum negative dp[!player][x] 
                    if (! found ) { 
                        set< pair<int,int> > & tm = primeNegative[!cplayer]; 
                        while(! tm.empty() ) { 
                            set<pair<int,int> >::iterator q = tm.begin(); 
                            if ( q->second < n-K ) { 
                                tm.erase(q); 
                            } else { 
                                found = true; 
                                pick = q->second; 
                                break; 
                            } 
                        } 
                    } 
                     
                    if(found) { 
                        if (dp[!cplayer][pick] < 0) { 
                            dp[cplayer][n] = dp[!cplayer][pick] - 1; 
                        } else { 
                            dp[cplayer][n] = dp[!cplayer][pick] + 1; 
                        } 
                    } else { 
                        dp[cplayer][n] = -1; 
                    } 
            } 
            // player 1 
            if (cplayer==1) { 
                    //look for a negative dp[!cplayer][x] in the range n-K <= x <= n-1 
                    // if it exists, return the maximum 
                    bool found = false; 
                    int pick = 0; 
                    { 
                        set< pair<int,int> > & tm = compoNegative[!cplayer]; 
                        while(! tm.empty() ) { 
                            set<pair<int,int> >::reverse_iterator q = tm.rbegin(); 
                            if ( q->second < n-K ) { 
                                tm.erase( tm.find(*q) ); 
                            } else { 
                                found = true; 
                                pick = q->second; 
                                break; 
                            } 
                        } 
                    } 
                     
                    // if it does not exist, return the maximum positive dp[!player][x] 
                    if (! found ) { 
                        set< pair<int,int> > & tm = compoPositive[!cplayer]; 
                        while(! tm.empty() ) { 
                            set<pair<int,int> >::reverse_iterator q = tm.rbegin(); 
                            if ( q->second < n-K ) { 
                                tm.erase( tm.find(*q) ); 
                            } else { 
                                found = true; 
                                pick = q->second; 
                                break; 
                            } 
                        } 
                    } 
                     
                    if(found) { 
                        if (dp[!cplayer][pick] < 0) { 
                            dp[cplayer][n] = dp[!cplayer][pick] - 1; 
                        } else { 
                            dp[cplayer][n] = dp[!cplayer][pick] + 1; 
                        } 
                    } else { 
                        dp[cplayer][n] = 1; 
                    } 
 
            } 
         } 
            // add to the sets 
            for (int cplayer=0; cplayer<2; cplayer++) { 
                assert(dp[cplayer][n] != 0); 
                if( iscomposite[n] ) { 
                    if (dp[cplayer][n] > 0) { 
                         compoPositive[cplayer].insert( make_pair(dp[cplayer][n], n) ); 
                    } else { 
                         compoNegative[cplayer].insert( make_pair(dp[cplayer][n], n) ); 
                    } 
                } else { 
                    if (dp[cplayer][n] > 0) { 
                         primePositive[cplayer].insert( make_pair(dp[cplayer][n], n) ); 
                    } else { 
                         primeNegative[cplayer].insert( make_pair(dp[cplayer][n], n) ); 
                    } 
                } 
            } 
        } 
 
         
        cout<<dp[0][N]<<endl; 
         
        int y = dp[0][N]; 
        if (y > 0) { 
            return y - 1; 
        } else { 
            return y + 1; 
        } 
    } 
}; 

During the match I had many problems implementing this. Which should be clear by the size of the code and the amount of repetition in it. I had to debug many problems and change the code a lot during the match.

DuckAligment

I will admit that by the time I opened this problem, I was confident about my 500. Its algorithm is correct after all, and its main risk was memory/time limits and I tested the largest case.

I checked the division summary, and it seemed anything above 230 was going to be a great score and seemed doable. So, I actually scored 230 points...

In problems like this, it is best to verify that the target solution space is rather small. There are at most O(N) columns/rows. And in each column/row, the first point of the line of ducks can be one of O(N) values. This means that the final setup of ducks can be one of O(N*N), we can just iterate through them all.

Once the final position is fixed, it will either be a line of ducks in a row or in a column. We can treat each case separately and they are in fact, symmetric (After solving for rows, just rotate your logic to solve for columns). So, given a row, and the cell in that row in which the line of ducks will begin - What is the minimum cost to move the ducks to those positions?

Now, let us think about the ducks themselves. Note that since the row in each of the target cells is always the same, the vertical cost will always be the same for a duck at a row y, no matter what cell we choose it to go. (The cost is y - i, where i is the number of the picked row). So we should only care about minimizing the horizontal distances. This is solvable with a greedy approach:

Let us say we have a row of ducks:
..*.*...**..*.*.*.
(This is the row after we move each duck to a position in the row, without accounting for horizontal moves).

And we want to turn it into:
....*******.......
(The target row).

Then you have to notice that the optimal way to move the left-most duck is to the left-most target cell. The second duck to the left, should move to the second target cell to the left. And so and so. We can simply sort the ducks by horizontal coordinate and move the i-th duck in the sorted list to the i-th cell in the target setup.

For columns , do exactly the same, just sort the ducks by row instead of column.

    int minimumTime(vector <string> grid) 
    { 
        int w = grid.size(); 
        int h = grid[0].size(); 
        int n = 0; 
         
        vector< pair<int,int> > ducks; 
         
        for (int i=0; i<w; i++) { 
            for (int j=0; j<h; j++) { 
                if (grid[i][j] == 'o' ) { 
                    ducks.push_back( make_pair(j,i) ); 
                } 
            } 
        } 
        n = ducks.size(); 
        sort(ducks.begin(), ducks.end() ); 
         
        int res = 1000000000; 
         
        // a row 
        for (int x=0; x<w; x++) { 
            for (int y=0; y+n <= h; y ++) { 
                int cost = 0; 
                for (int i=0; i<n; i++) { 
                    cost += abs( ducks[i].second - x) + abs( ducks[i].first - (y+i) );  
                } 
                res = std::min(res, cost); 
            } 
        } 
         
        // a column 
        for (int i=0; i<n; i++) { 
            swap( ducks[i].first, ducks[i].second ); 
        } 
        sort(ducks.begin(), ducks.end() ); 
        for (int y=0; y<h; y++) { 
            for (int x=0; x+n <= w; x ++) { 
                int cost = 0; 
                for (int i=0; i<n; i++) { 
                    cost += abs( ducks[i].second - y) + abs( ducks[i].first - (x+i) );  
                } 
                res = std::min(res, cost); 
            } 
        } 
         
        return res; 
         
    } 

Outcome

I passed system tests on both problems and got a very good position.

The admins are considering whether to make the match rated or not. I don't think it makes any sense to cancel the ratings in this match. The expected rating change for a coder that participates in a match is 0. Therefore, coders that were unable to participate did not lose (or gain) any rating unfairly. It is lame that they had to lose the match, and I hope the admins make a new December SRM. But the objective of the ratings is to measure performance objectively, and the ratings of the match do exactly that , because they consider only the coders that participated.

Codeforces round #96 (division 2)

Day for another contest. This time I had to do it from my reliable, but small netbook since the big one was busy. I didn't think it would matter, and it turns out it didn't.

I had issues entering the site for the first three minutes of the contest. Apparently they got fixed themselves.

Problem A - HQ9+
An easy one, the only characters that do any printing are H, Q and 9. So, just make a loop to detect them.

I actually spent a lot of time getting my setup to run and test stuff for some reason.

Problem B - Unary
Just at the bottom of the statement, it finally explains that the unary system just writes 1 n times. The length of a number n when represented in unary is thus exactly n.

Then we need to find the actual number n. It is the result of the concatenation of a (possibly large) amount of 4 bits numbers in binary. Three things:
- Consider the binary blocks as decimal numbers directly, for example consider < to be 8 right away.
- To concatenate 1000 with 1010 is the same as doing: 1000 * 10000 + 1010. In decimal it translates into 8 * 16 + 10.
- So, to concatenate the (n-1) first symbols with a new one, find the result X for the n-1 first symbols then do: (n-1)*16 + new.
- The actual number may be very large (400 bits). But the problem asks for the result modulo 1000003. We can just exploit some modular arithmetic . (X * Y + Z) mod 1000003 is equal to ( (X mod 1000003) * (Y mod 1000003) + Z ) mod 1000003. This way, we need only to remember the partial results modulo 1000003.

const int MOD = 1000003; 
 
int translate(char ch) 
{ 
    switch(ch) { 
    case '>': return 8; 
    case '<': return 9; // →  1001, 
    case '+': return 10;//   →  1010, 
    case '-': return 11; // →  1011, 
    case '.': return 12; // →  1100, 
    case ',': return 13; // →  1101, 
    case '[': return 14; // →  1110, 
    case ']': return 15; // →  1111.          
    } 
} 
 
int solve(string x) 
{ 
    int res = 0; 
    for (int i=0; i<x.size(); i++) { 
        res = (res << 4) % MOD; 
        res += translate(x[i]); 
        res %= MOD; 
    } 
    return res; 
} 

Problem C - Turing tape
* Keep in mind the integer value of the previous printed character. For i=0, this is 0, else it is the (i-1)-th character of the input string.
* The conversion is: rev[ (x - rev(last) ) mod 256 ], it is simple to revert, first, reverse the i-th printed character, then solve the modular equaton, yes, once again modular arithmetic.

I was going to explain more problems but I will go take lunch, will update this soon.

Problem D - Piet
Oh, this is such an evil problem. Anyway, since n can be 10^7, you'd probably like to do each step in O(1). In order to do each step in O(1) you need to precalculate various things that you can use in each step. First, find the blocks and which block each cell belongs to.

What I did was to also precalculate the corner cells of each block (A look at the statement reveals that every move involves moving from a corner of a block to another).

To represent the directions (DP), I use a integer from 0 to 3. The offsets (change of coordinates) are left, down, right, up - ordered in clockwise order. CP will then be the offset in the direction index from DP and is -1 or 1.

The implementation of the logic takes some work of thought. In my case, I need to convert DP and CP into a corner of the current block. Then from that corner, move according to DP and find the next block. If it is black or outside the board, you would need to rotate DP and CP according to the statement.

int m; 
int n; 
string board[50]; 
 
int blockn; 
int cellBlock[50][50]; 
int blockCornerX[2500][2][2]; 
int blockCornerY[2500][2][2]; 
 
char solve() 
{ 
    //a) let us save a block id for each square in the grid 
    memset(cellBlock,-1,sizeof(cellBlock)); 
    blockn = 0; 
    int w = m; 
    int h = board[0].size(); 
    //get info about our beloved blocks. 
    for (int i=0; i<w; i++) { 
        for (int j=0; j<h; j++) { 
            if ( (board[i][j] != '0') && (cellBlock[i][j]==-1) ) { 
                int a = i; 
                while ( (a<w) && (board[a][j] == board[i][j] ) ) { 
                    a++; 
                } 
                int b = j; 
                while ( (b<h) && (board[i][b] == board[i][j] ) ) { 
                    b++; 
                } 
                for (int x=i; x<a; x++) { 
                    for (int y=j; y<b; y++) { 
                        cellBlock[x][y] = blockn; 
                    } 
                } 
                for (int x=0; x<2; x++) { 
                    for (int y=0; y<2; y++) { 
                        blockCornerX[blockn][x][y] = i + (a-1-i)*x; 
                        blockCornerY[blockn][x][y] = j + (b-1-j)*y; 
                    } 
                } 
                blockn++; 
            } 
        } 
    } 
    int BP = 0; 
    int dx[4] = {0, 1,  0, -1}; 
    int dy[4] = {1, 0, -1, 0 }; 
    int DP = 0; 
    int CP = -1; 
    for (int t=0; t<n; t++) { 
        //cout << "t"<<t<<" : "<<BP<<" ; "<<dx[DP]<<","<<dy[DP]<<" ; "<<CP<<endl; 
        int nx = dx[DP] + dx[ (DP+CP+4) % 4 ]; 
        int ny = dy[DP] + dy[ (DP+CP+4) % 4 ]; 
        if (nx == -1) { 
            nx = 0; 
        } else { 
            nx = 1; 
        } 
        if (ny == -1) { 
            ny = 0; 
        } else { 
            ny = 1; 
        } 
        int cx = blockCornerX[BP][nx][ny]; 
        int cy = blockCornerY[BP][nx][ny]; 
        nx = cx + dx[DP]; 
        ny = cy + dy[DP]; 
        if ( (nx<0) || (nx>=w) || (ny<0) || (ny>=h) || (board[nx][ny]=='0') ) { 
            //black 
            if (CP == -1) {//left turns into right 
                CP = 1; 
            } else { 
                //right turns into left, but DP rotates 90 degrees. 
                DP = (DP+1)%4; 
                CP = -1; 
            } 
        } else { 
            BP = cellBlock[nx][ny]; 
        } 
 
    } 
    //    cout << "t"<<n<<" : "<<BP<<" ; "<<DP<<" ; "<<CP<<endl; 
 
    return board[blockCornerX[BP][0][0]][blockCornerY[BP][0][0]]; 
} 
 

Problem E - Logo turtle
At first I was excited but then figured the problem has little to do with LOGO. It took me a while to understand that T - turn around means a 180 degrees turn. Anyway, the problem is solvable with dynamic programming.

Take for instance a recurrence F(p, n, d, minimize). If minimize is true, the function will find the minimum possible position offset if we only use commands higher than or equal to p, must change n commands, and d is 0 if we are facing right or 1 if we are facing left. At each recursive step, we can decide to alter the p-th character or not. If we do, we increase (d is 0) or decrease (d is 1) the position, or turn the direction and then will move F(p+1, nn, nd, minimize) positions.

The base case is when p is equal to the number of commands, there are no commands to make. However, remember that we must do n changes. If n is even, we can waste the changes by repeating all of the changes on a single command (and thus changing nothing). Else we return -INFINITE (if minimize is false) or INFINITE (if it is true).

Why do we need to minimize and maximize the result? Because the largest distance can be at some point that is negative. So, if the minimum value we can find is negative, we can negate it and find a possible max distance.

Edit: seems I passed system tests in all the problems. Good. Hopefully I will only do division 1 problem sets from now (unless the contest is div2 only, I guess).

Edit: Here is the code for E.

string commands; 
 
bool knownAnswer[101][51][2][2]; 
int  answer[101][51][2][2]; 
 
const int INF = 1000000; 
 
// Returns the minimum/maximum change in distance starting at command p. If we must 
// do n changes. The current direction is d (0 : positive, 1: negative). 
// 
int rec(int p, int n, int d, int wantMinimum) 
{ 
    int & res = answer[p][n][d][wantMinimum]; 
    if (! knownAnswer[p][n][d][wantMinimum]) { 
         
        res = (wantMinimum ? INF : -INF); 
         
        if (p==commands.size()) {  //if there are no more commands left, we 
                                   //cannot decide to change any more commands 
            if (n % 2 == 0) { 
                res = 0;      //won't move anything, the only possible offset is 0. 
            } 
        } else { 
            for (int doChange = 0; doChange < 2; doChange++) { 
                if ( (doChange==0) || (n > 0) ) { //can we actually change this? 
                    int nn = n; 
                    int nd = d; 
                    char com = commands[p]; 
                    if (doChange) { 
                        com = ( (com=='T') ? 'F' : 'T' ); 
                        nn--; 
                    } 
                    int x = 0; 
                    if (com == 'T') { 
                        nd = ! d; 
                    } else { //move forward (depending on your direction). 
                        if (d == 0) { 
                            x++; 
                        } else { 
                            x--; 
                        } 
                    } 
                    if (wantMinimum) { 
                        res = std::min(res, x + rec(p+1,nn,nd, wantMinimum) ); 
                    } else { 
                        res = std::max(res, x + rec(p+1,nn,nd, wantMinimum) ); 
                    } 
                } 
            } 
        } 
         
         
        knownAnswer[p][n][d][wantMinimum] = true; 
    } 
         
    return res; 
} 
 
int solve(int n) 
{ 
    memset(knownAnswer,0,sizeof(knownAnswer)); 
     
    int minim = abs( -rec(0,n,0, true) ); //minimum offset from this starting point 
    int maxim = abs( -rec(0,n,0, false) ); //maximum... 
    return std::max( minim, maxim); 
}