2016-07-31

SRM 181 DIV-1 1000 KiloManX

This is another very interesting problem that can be solved using graph search. The problem itself looks
like an optimization problem and should be solvable using ‘traditional’ dynamic programming technique (which
is true), but with some observations we can turn this into a graph search problem:

The problem can be reduced to a search problem.
The search space is the set of states where each state is a combination of ‘boss defeated so far’ and ‘shots used’.
For each boss, the state of ‘defeated’ equals to the presence of its weapon.
The state transfer function looks like: given the set of boss defeated and the shots taken, what would be the set of bosses
that we could defeat next and the corresponding shots we would use to defeat those boss?
So we represent each state as a node in a graph and the state transfer function as edges between graph nodes.
The problem now is reduced to find shortest path between two nodes: the start node where no boss is defeated and the end
node where all bosses have been defeated.

typedef struct GNode {
    int weapon;
    int shot;
    GNode() : weapon(0), shot(0) {}
} node;

class Compare {
public:
    bool operator() (const GNode &n1, const GNode &n2) {
        return n1.shot > n2.shot;
    }
};

class KiloManX {
public:
    int leastShots(vector<string> damageChart, vector<int> bossHealth) {
        int N = (int)damageChart.size();
        const int CAP = 1 << N;
        vector<bool> visited(CAP, false);
        GNode node;
        priority_queue<GNode, vector<GNode>, Compare> pq;
        pq.push(node);

        int ret = INT_MAX;
        while (!pq.empty()) {
            auto node = pq.top();
            pq.pop();

            if (visited[node.weapon])
                continue;
            visited[node.weapon] = true;

            if (node.weapon == CAP - 1) {
                ret = min(ret, node.shot);
            }

            for (int i = 0; i < N; ++i) {
                if ((node.weapon >> i) & 1)
                    continue;
                int best = bossHealth[i];
                for (int j = 0; j < N; ++j) {
                    if (i == j) continue;
                    if (((node.weapon >> j) & 1) && damageChart[j][i] != '0') {
                        int damage = damageChart[j][i] - '0';
                        int shot = bossHealth[i] / damage;
                        if (bossHealth[i] % damage)
                            ++shot;
                        best = min(best, shot);
                    }
                }
                GNode newNode;
                newNode.shot = best + node.shot;
                newNode.weapon = (node.weapon | (1 << i));
                pq.push(newNode);
            }
        }
        return ret;
    }
}

2016-07-23

TopCoder

SRM 211 DIV-1 500 grafixMask

Problem Statement

This is a typical problem that is easily solvable using Flood Fill / BFS / DFS. The first challenge is to digest the problem quickly, and implement the code to parse input and extract interested information (in this case, the graph representation.). The second challenge is to to make sure only visit a node once.

vector<int> parseString(string input) {
  istringstream iss(input);
  vector<string> tokens{istream_iterator<string>{iss},
    istream_iterator<string>{}};
  vector<int> ret;
  for (auto &str : tokens) {
    ret.emplace_back(stoi(str));
  }
  return ret;
};

class grafixMask {
public:
    vector <int> sortedAreas(vector <string> rectangles) {
      const int ROWS = 400, COLS = 600;
      vector<vector<bool>> bitmap(ROWS, vector<bool>(COLS, false));
      vector<int> ret;
      for (auto &rec : rectangles) {
        auto vec = parseString(rec);
        for (int i = vec[0]; i <= vec[2]; ++i) {
          for (int j = vec[1]; j <= vec[3]; ++j) {
            bitmap[i][j] = true;
          }
        }
      }

      for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
          if (bitmap[i][j]) continue;
          int area = 0;
          stack<pair<int,int>> stack;
          stack.push(make_pair(i, j));

          while (!stack.empty()) {
            auto pos = stack.top();
            stack.pop();
            int x = pos.first, y = pos.second;
            if (bitmap[x][y]) continue;
            bitmap[x][y] = true;
            ++area;

            int dirx[] = {1, -1, 0, 0};
            int diry[] = {0, 0, 1, -1};
            for (int k = 0; k < 4; ++k) {
              int xx = x + dirx[k], yy = y + diry[k];
              if (xx >= 0 && xx < 400 && yy >= 0 && yy < 600 && !bitmap[xx][yy]) {
                stack.push(make_pair(xx, yy));
              }
            }
          }
          ret.push_back(area);
        }
      }
      sort(ret.begin(), ret.end());
      return ret;
    }
}

2016-07-20

TopCoder

SRM 156 DIV-1 1000 Path Finding

Problem Statement

class PathFinding {
public:
  int minTurns(vector <string> board) {
    typedef struct state {
      int ax, ay, bx, by;
      int step;
    } state;

    state s;
    s.ax = s.ay = s.bx = s.by = -1;
    bool visited[20][20][20][20] = {false};
    int rows = board.size(), cols = board[0].size();

    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        if (board[i][j] == 'A') {
          s.ax = i; s.ay = j;
        }
        if (board[i][j] == 'B') {
          s.bx = i; s.by = j;
        }
      }
    }

    // Invalid board in first place.
    if (s.ax == -1 || s.bx == -1) return -1;
    s.step = 0;

    queue<state> q;
    q.push(s);
    visited[s.ax][s.ay][s.bx][s.by] = true;
    while (!q.empty()) {
      state node = q.front();
      q.pop();
      if (node.ax == s.bx && node.ay == s.by && node.bx == s.ax &&
          node.by == s.ay) {
        return node.step;
      }

      for (int dx1 = -1; dx1 <= 1; ++dx1) {
        for (int dy1 = -1; dy1 <= 1; ++dy1) {
          for (int dx2 = -1; dx2 <= 1; ++dx2) {
            for (int dy2 = -1; dy2 <= 1; ++dy2) {
              int axx = node.ax + dx1;
              int ayy = node.ay + dy1;
              int bxx = node.bx + dx2;
              int byy = node.by + dy2;

              // Out of board.
              if (axx < 0 || axx >= rows || ayy < 0 || ayy >= cols ||
                  bxx < 0 || bxx >= rows || byy < 0 || byy >= cols) {
                continue;
              }

              if (board[axx][ayy] == 'X' || board[bxx][byy] == 'X') {
                continue; // obstacle.
              }

              // Crossed line (both moves)
              if (axx == node.bx && ayy == node.by && bxx == node.ax && byy == node.ay) {
                continue;
              }
              // Cross line (a single side move)
              if (axx == bxx && ayy == byy) continue;

              if (visited[axx][ayy][bxx][byy]) continue;
              state ns;
              ns.step = node.step + 1;
              ns.ax = axx, ns.ay = ayy, ns.bx = bxx, ns.by = byy;
              visited[axx][ayy][bxx][byy] = true;
              q.push(ns);
            }
          }
        }
      }
    }

    return -1;
  }
};