a bit of topcoder: SRM 631

TOPCODER SRM 631
Div 2 - 500

Problem Statement:
On a one dimensional array, at position[i] there are count[i] cats. In a unit time, each cat can stay on its position, move 1 block to the left, or move 1 block to the right. Given time \(t\), check whether it is possible for all cats to occupy different cells at time \(t\).

Solution:
Firstly sort the pairs (position[i], count[i]) and starting from lowest position[i]:
     The cats can occupy any position in \([ \text{position[i] - time}, \text{position[i] + time} ] \).
     We greedily place the cats to the left-most orientation so as to leave more spaces for the remaining cats.
     If this is not possible, return "Impossible".

/* Did not manage to think about sorting during the match... :( haha oh well!  */


Div 2 - 950

Problem Statement:
Given a number N, find the number of ways to represent N in "binary" representation such that each "bit" is made up of 0, 1, or 2.

Solution:
First, represent N in terms of its normal binary representation in an array/vector<int> called rep. Then establish the following recursion:

typedef long long Long;
map<vector<int>, Long> dp;

Long count(vector<int> rep, int n){
  rep.resize(n+1);
  vector<int> cur = rep;
  if(dp.find(cur) != dp.end()) {
   // printf("called\n");
    return dp[cur];
  }
  if(n == 0){
    if(rep[0] <= 2) return 1;
    else return 0;
  }
  if(rep[n] > 3) return 0;
  
  Long ret = 0;
  while(rep[n]>=0){
    if(rep[n] <= 2){
      ret += count(rep, n-1);
    }
    rep[n-1] += 2;
    --rep[n];
  }
  dp[cur] = ret;
  return dp[cur];
}

The function count counts the number of ways of equivalent representation of rep using the first n+1 bits. It returns early when rep[n] is bigger than 3, since any equivalent representation of such will have at least one of its bits to be more than 2. Furthermore, we use a map to cache the result from calculations, which is important to bring down the exponential time of this algorithm to a polynomial one. :D
/* of course I did not think about this during the contest either but pretty happy I can solve it now :D */

Div 1 - 250
Problem Statement:
Given an NxN board with 'B' and 'W', you can either paint a whole row 'B' or 'W' in each turn. Find the minimum number of turns such that there is no more than \(N/2\) consecutive cells with the same color in every column.

This problem is all about bruteforce, but it needs one important observation: You only need at most 2 painting to eliminate consecutive cells with the same colors in any column into parts of length less than \(N/2\). As such, the problem can be "easily" (yeah in a sense that you don't have to think too much, just implement) solved by trying to paint the board once ('W' or 'B') or twice (one 'W' one 'B'). Don't forget to check the case where we don't even need to paint anything though.