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);
});
}
};
```