TopCoder

SRM 700 DIV II 450

My DFS solution during contest, which passed all system tests except TLE for one. As a result, I received zero points.
This is not the first time that I am tempted to use a brutal force solution for a 450 / 500 problem that seemingly work but
ultimately fail due to inefficiency.

class XMarksTheSpot {
    int result;
public:
    void dfs(vector<string> board, int i, int j, int rs, int cs) {
        if (i == rs - 1 && j == cs - 1) {
            if (board[i][j] == '?') {
                board[i][j] = 'O';
                compute(board);
                board[i][j] = '.';
                compute(board);
            } else {
                compute(board);
            }
            return;
        }
        int ni, nj;
        if (j + 1 < cs) {
            ni = i;
        } else {
            ni = i + 1;
        }
        nj = (j + 1) % cs;
        
        if (board[i][j] == '.' || board[i][j] == 'O') {
            dfs(board, ni, nj, rs, cs);
        } else {
            board[i][j] = '.';
            dfs(board, ni, nj, rs, cs);
            board[i][j] = 'O';
            dfs(board, ni, nj, rs, cs);
        }
    }
    
    void compute(vector<string> board) {
        int rs = (int)board.size();
        int cs = (int)board[0].size();
        int t = INT_MAX, b = INT_MIN, l = INT_MAX, r = INT_MIN;
        for (int i = 0; i < rs; ++i) {
            for (int j = 0; j < cs; ++j) {
                if (board[i][j] == '.') continue;
                t = std::min(i, t);
                b = std::max(i, b);
                l = std::min(j, l);
                r = std::max(j, r);
            }
        }

        for (int i = t; i <= b; ++i) {
            for (int j = l; j <= r; ++j) {
                ++result;
            }
        }
    }
    
    int countArea(vector<string> board) {
        result = 0;
        int rs = (int)board.size();
        int cs = (int)board[0].size();
        dfs(board, 0, 0, rs, cs);
        return result;
    }
}

Actually even with brutal force, there is better approaches without recursing (which is the root of many evils of time outs during contest).
We can just iterate through all the states explicitly and calculate the results at higher level while iterating. Here is a good example on how to do so.

USACO

USACO 2.4 Fractions To Decimals 

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <unordered_map>
#include <sstream>

using namespace std;

int N, D;
int outCnt = 1;
void format(ofstream &output) {
  ++outCnt;
  if (outCnt == 76) {
    output << endl;
    outCnt = 0;
  }
}

int main() {
  ifstream fin("fracdec.in");
  ofstream fout("fracdec.out");
  fin >> N >> D;
  
  ostringstream os;
  int d = N / D;
  fout << N / D;
  while (d / 10) {
    ++outCnt;
    d %= 10;
  }
  int r = N % D;
  
  if (!r) {
    fout << ".0" << endl;
    outCnt += 2;
    return 0;
  } else {
    fout << ".";
    ++outCnt;
  }
  
  vector<int> ds;
  unordered_map<int, int> map;
  
  while (r && map.find(r) == map.end()) {
    map[r] = (int)ds.size();
    r *= 10;
    ds.push_back(r / D);
    r %= D;
  }
  
  if (r) {
    for (int i = 0; i < map[r]; ++i) {
      fout << ds[i]; format(fout);
    }
    
    fout << "("; format(fout);
    
    for (int i = map[r]; i < ds.size(); ++i) {
      fout << ds[i]; format(fout);
    }
    
    fout << ")"; format(fout);
  } else {
    for (int i = 0; i < ds.size(); ++i) {
      fout << ds[i]; format(fout);
    }
  }
  
  fout << endl;
  return 0;
}
USACO

USACO 2.4 Bessie Come Home

Pretty straightforward solution with Floyd all pair shortest path algorithm: we simply compute every path and pick up the shortest one between a cow and the barn. One catch is to prepare all the input data. In particular, there is test data where for same pair of pastures, say A and B, distance between AB and BA is different. So need a check to select the smaller one, if distance AB and BA is different. This is very annoying, though it sounds legitimate test data, and maybe intentionally crafted in such a way.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <climits>
#include <iomanip>

using namespace std;

int N;
vector<vector<int>> dist(52, vector<int>(52, INT_MAX));

int char2index(char c) {
  if (c >= 'a') {
    return c - 'a' + 26;
  }
  return c - 'A';
}

int main() {
  ifstream fin("comehome.in");
  ofstream fout("comehome.out");
  
  fin >> N;
  for (int i = 0; i < N; ++i) {
    char c1, c2; int d;
    fin >> c1 >> c2 >> d;
    int m = char2index(c1), n = char2index(c2);
    if (d < dist[m][n]) {
        // Need this check because sometimes dist[m][n]
        // read from input does not equal to dist[n][m]!!
        dist[m][n] = d; dist[n][m] = d;
    }
  }
  
  for (int k = 0; k < 52; ++k) {
    for (int i = 0; i < 52; ++i) {
      for (int j = 0; j < 52; ++j) {
        if (dist[i][k] + dist[k][j] < dist[i][j] &&
            dist[i][k] != INT_MAX &&
            dist[k][j] != INT_MAX) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  
  for (int i = 0; i < 52; ++i) {
    dist[i][i] = INT_MAX;
  }
  
  int ret = INT_MAX; int index = 0;
  for (int i = 0; i < 26; ++i) {
    if (dist[i][25] == INT_MAX)
        continue;
    if (ret > dist[i][25]) {
        ret = dist[i][25];
        index = i;
    }
  }
  
  cout << (char)('A' + index) << " " << ret << endl;
  fout << (char)('A' + index) << " " << ret << endl;
}