SRM 710 Div2

Easy. MagicSubset:

Problem Description:
There are N stones with some weight. The first stone is magical, and if you choose it, each stone will have its weight multiplied by -1. Output the maximum weight sum you can obtain.

Constraints:
1 ≤ N ≤ 50
-50 ≤ W[i] ≤ 50

Solution:
Consider separately whether you take or not the magical stone, then greedy.

Code:

class MagicSubset {
 public:
  int findBest(std::vector<int> values) {
    return std::max(
        std::accumulate(values.begin() + 1, values.end(), 0,
                        [&](int x, int y) { return x + std::max(0, y); }),
        -std::accumulate(values.begin() + 1, values.end(), values.front(),
                         [&](int x, int y) { return x + std::min(0, y); }));
  }
};

Medium. ForwardMancala

Problem Description:
There are N piles of stones put in a circle (and given in clockwise order).
You can apply an operation each turn, until all stones are gathered at one pile.
You choose a non-empty pile, and take all the stones, distribute them one by one from the next (clockwise) pile, until there is no more stone on your hands.
Output a sequence of operation to achieve the goal. The length of the sequence must not exceed 2500.

Constraints:
2 ≤ N ≤ 10
0 ≤ A[i] ≤ 10

Solution:
Simply arbitrarily choose a non-empty pile and operate, until the goal is achieved. However, there should be one pile that is never operated upon, and for simplicity I have chose the 0-th pile. The length of the sequence is always below the bound because each time a stone is to cross over the 0-th pile, there must be at least one stone put into the 0-th pile, which never will be removed in the future. With that there are at most 10 * 10 stones, the length of the maximum sequence never exceeds 10 * 10 * 10.

Code:

class ForwardMancala {
public:
  std::vector<int> findMoves(std::vector<int> start) {
    std::vector<int> res;
    while (true) {
      bool moved = false;
      for (size_t i = 1; i < start.size(); ++i) {
        if (start[i] == 0) continue;
        res.emplace_back(i);
        moved = true;
        int x = start[i];
        start[i] = 0;
        for (size_t j = i + 1; x; ++j, --x) {
          ++start[j % start.size()];
        }
      }
      if (!moved) break;
    }
    return res;
  }
};

Hard. MinMaxMax

Problem Description:
Given a graph with N nodes and M edges, you are to compute sum(D(i, j) for i < j), where D(i, j) is equal to the minimal of (maximal weight of vertex * maximal weight of edge) passed, for any path from i to j.

Constraints:
1 ≤ N ≤ 300
1 ≤ W[i] ≤ 1e6

Solution:
Apply a Floyd-Warshall-like DP.
dpe[t][i][j]: After considering vertex with the t-th smallest weight, minimal of the maximal weight in any path within i to j.
dp[t][i][j]: After considering vertex with the t-th smallest weight, minimal of the maximal weight * maximal edge in any path within i to j.
Note that it is by sorting the vertices by its weight, that we can update dp table easily, i.e., we created monotonicity.

Code:

class MinMaxMax {
 public:
  int64_t findMin(std::vector<int> a, std::vector<int> b, std::vector<int> w, std::vector<int> v) {
    std::vector<int> vord(v.size()); {
      std::iota(vord.begin(), vord.end(), 0);
      std::sort(vord.begin(), vord.end(), [&](int i, int j) { return v[i] < v[j]; });
    }
    std::vector<std::vector<int>> dpe(v.size(), std::vector<int>(v.size(), 0x3f3f3f3f));
    std::vector<std::vector<int64_t>> dp(v.size(), std::vector<int64_t>(v.size(), 1LL << 60)); {
      for (size_t i = 0; i < w.size(); ++i) {
        dpe[a[i]][b[i]] = dpe[b[i]][a[i]] = w[i];
      }
      for (size_t i = 0; i < v.size(); ++i) {
        for (size_t j = 0; j < v.size(); ++j) {
          for (size_t k = 0; k < v.size(); ++k) {
            dpe[j][k] = std::min(dpe[j][k], std::max(dpe[j][vord[i]], dpe[vord[i]][k]));
            if (dpe[j][k] < 0x3f3f3f3f) dp[j][k] = std::min(dp[j][k], 1LL * dpe[j][k] * std::max({v[j], v[vord[i]], v[k]}));
          }
        }
      }
    }
    return std::accumulate(dp.begin(), dp.end(), 0LL,
                           [&, i = 0](int64_t x, const std::vector<int64_t> &a) mutable {
                             return x + std::accumulate(a.begin(), a.begin() + i++, 0LL);
                           });
  }
};

Post comments for the round:
I spent a lot of time debugging Hard because of overflow. From next time I will remember to check whether distances are at INF, before using them.
.