SRM 702 Div2

Easy. TestTaking:

Problem Description:
There are q false/true questions, in which you guessed g are true, and there are a that are really true. Output the maximum number of questions you might get correct.

Constraints:
1 ≤ Q ≤ 50

Solution:
As for true, you can at most get min(guess_true, actual_true). So does this work for marks at false.

Code:

class TestTaking {
public:
  int findMax(int questions, int guessed, int actual) {
    return std::min(guessed, actual) + std::min(questions - guessed, questions - actual);
  }
};

Medium. GridSort:

Problem Description:
You are given a grid of N * M, in one dimension form. The values are given in permutation 1..(N*M).
Determine whether it is possible to apply any number of these operations, so that the permutation is sorted:
1. Swap any two rows.
2. Swap any two columns.

Constraints:
1 ≤ N, M ≤ 50

Solution:
If some x and y were initially at the same row, then they will be at the same row forever. So will x and y at the same column, they stay at the same column forever. Hence we can reject the input if there is any such pair of x and y that does not match with the property of a sorted permutation. However, if this property is met, one can easily sort to the desired permutation (greedily).

Code:

class GridSort {
 public:
  std::string sort(int n, int m, std::vector<int> grid) {
    std::for_each(grid.begin(), grid.end(), [&](int &x) { --x; });
    for (int i = 0; i < n; ++i) {
      int x = grid[i * m] / m;
      for (int j = 1; j < m; ++j) {
        if (x != grid[i * m + j] / m) {
          return "Impossible";
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      int x = grid[i] % m;
      for (int j = 1; j < n; ++j) {
        if (x != grid[j * m + i] % m) {
          return "Impossible";
        }
      }
    }
    return "Possible";
  }
};

Hard. SubsetSumExtreme:

Problem Description:
You have an equal probability dice, described by the values of its faces. You also have a multiset called block.
Each time you roll the dice, and suppose you rolled a face with some value F, then you examine if there is a subset of block with sum F, and eliminate the subset from the block (arbitrarily choose one if multiple choices exist). If such subset is not found, the game ends.
You will repeat this process until the game ends, trying to minimize the sum of eliminated subsets' values. Output the expected sum.

Constraints:
1 ≤ block.size, face.size ≤ 12
1 ≤ block[i] ≤ 1000

Solution:
dp[s]: With set s still existing, the answer.
dp[s] = sum(min(dp[ss] for ss is subset of s, and sum[ss] == F) for F in face) / face.size

Code:

class SubsetSumExtreme {
 public:
  double getExpectation(std::vector<int> block, std::vector<int> face) {
    std::vector<double> dp(1 << block.size());
    std::vector<int> sum(1 << block.size());
    for (int s = 1; s < 1 << block.size(); ++s) {
      sum[s] = std::accumulate(block.begin(), block.end(), 0,
                               [&, i = 0](int x, int y) mutable {
                                 return x + block[i] * (s >> i++ & 1);
                               });
      for (int i = 0; i < face.size(); ++i) {
        double e = sum[s];
        for (int ss = s; ; ss = ss - 1 & s) {
          if (sum[ss] == face[i]) e = std::min(e, dp[s ^ ss]);
          if (!ss) break;
        }
        dp[s] += 1.0 * e / face.size();
      }
    }
    return dp.back();
  }
};