0w1

SRM 700 Div2

Easy. Xylophone:

Code:

class Xylophone {
 public:
  int countKeys(std::vector<int> keys) {
    std::set<int> bag;
    for (int v : keys) bag.emplace(v % 7);
    return bag.size();
  }
};

Medium. XMarksTheSpot:

Problem Description:
You are given a 2D board.
There are three types of contents for a grid:
'O' meaning there is a marker.
'.' meaning it is empty.
'?' meaning it could be any of the above until it is examined.
You know that there is a treasure lying in between the rectangle constituted by the outmost border of markers.
You want to know the sum for every possible configuration of '?'s, the sum of possible grids that could hide the treasure.

Constraints:
1 ≤ N * M ≤ 50
K ≤ 19, K is the number of '?'s

Solution:
Preprocess the outmost markers.
Then test for each configurations.
O(2**K * K)

Code:

class XMarksTheSpot {
 public:
  int countArea(std::vector<std::string> board) {
    std::vector<std::pair<int, int>> var;
    int mnx = board.size(), mxx = -1, mny = board[0].size(), mxy = -1;
    for (int i = 0; i < board.size(); ++i) {
      for (int j = 0; j < board[i].size(); ++j) {
        if (board[i][j] == 'O') {
          mnx = std::min(mnx, i);
          mxx = std::max(mxx, i);
          mny = std::min(mny, j);
          mxy = std::max(mxy, j);
        } else if (board[i][j] == '?') {
          var.emplace_back(i, j);
        }
      }
    }
    int res = 0;
    for (int s = 0; s < 1 << var.size(); ++s) {
      int nx = mnx, xx = mxx, ny = mny, xy = mxy;
      for (int i = 0; i < var.size(); ++i) {
        if (s >> i & 1) {
          nx = std::min(nx, var[i].first);
          xx = std::max(xx, var[i].first);
          ny = std::min(ny, var[i].second);
          xy = std::max(xy, var[i].second);
        }
      }
      res += (xx - nx + 1) * (xy - ny + 1);
    }   
    return res;
  }
};

Hard. XYZCoder:

Problem Description:
There are R rooms, each with S size.
There are R * S competitors for this contests, and there is no tie.
After the contest has finished, you will take the rank of each winner of the room, and sort them.
You are to find the number of possible lists you could obtain, modulo 1e9 + 7.

Constraints:
1 ≤ R, S ≤ 100

Solution:
dp[i][j]: there are i winners of the room left undetermined, j non-winner of the room, number of ways
dp[i][j] = dp[i - 1][j + S - 1] * i + dp[i][j - 1]

Code:

class XYZCoder {
  const int MOD = 1e9 + 7;
 public:
  int countWays(int room, int size) {
    std::vector<std::vector<int>> dp(2, std::vector<int>((size - 1) * room + 1));
    std::fill(dp[0].begin(), dp[0].end(), 1);
    for (int i = 1; i <= room; ++i) {
      std::fill(dp[i & 1].begin(), dp[i & 1].end(), 0);
      for (int j = 0; j <= (size - 1) * (room - i); ++j) {
        if (j - 1 >= 0) (dp[i & 1][j] += dp[i & 1][j - 1]) %= MOD;
        (dp[i & 1][j] += 1LL * i * dp[~i & 1][j + size - 1] % MOD) %= MOD;
      }
    }
    return (dp[room & 1][0] + MOD) % MOD;
  }
};