SMU Summer 2024 Contest Round 8 - Problem Solutions
Problem 1: Product
Approach Observing that the constraint \(\prod_{i=1}^N L_i \le 10^5\) implies that N cannot exceed 16, since \(2^{17} > 10^5\). This allows us to solve the problem using straightforward brute force enumeration of all possible combinations.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64 totalElements, targetValue;
cin >> totalElements >> targetValue;
vector<vector<int64>> elementGroups(totalElements);
for (int i = 0; i < totalElements; i++) {
int groupSize;
cin >> groupSize;
elementGroups[i].resize(groupSize);
for (int j = 0; j < groupSize; j++) {
cin >> elementGroups[i][j];
}
}
int64 answer = 0;
function<void(int, __int128)> enumerate = [&](int currentGroup, __int128 currentProduct) {
if (currentProduct > targetValue) {
return;
}
if (currentGroup == totalElements) {
if (currentProduct == targetValue) {
answer++;
}
return;
}
for (size_t idx = 0; idx < elementGroups[currentGroup].size(); idx++) {
enumerate(currentGroup + 1, currentProduct * elementGroups[currentGroup][idx]);
}
};
enumerate(0, 1);
cout << answer << '\n';
return 0;
}
Problem 2: Dice Sum
Approach This is a dynamic programming problem. Define dp[i][j] as the number of ways to obtain a sum of j using the first i dice. The transition equation is: \[dp_{i,j}=\sum_{k=1}^{\min(j,m)}dp_{i-1,j-k}\]
Implementation
#include <bits/stdc++.h>
using ll = long long;
struct ModNumber {
ll value;
ModNumber(ll v = 0) : value(v) {}
ModNumber& operator+=(const ModNumber& other) {
value += other.value;
return *this;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int diceCount, facesPerDie, maxSum;
cin >> diceCount >> facesPerDie >> maxSum;
vector<vector<ModNumber>> dp(diceCount + 1, vector<ModNumber>(maxSum + 1));
for (int face = 1; face <= facesPerDie; face++) {
if (face <= maxSum) {
dp[1][face] = ModNumber(1);
}
}
for (int i = 2; i <= diceCount; i++) {
for (int sum = 1; sum <= maxSum; sum++) {
for (int faceValue = 1; faceValue <= min(sum, facesPerDie); faceValue++) {
dp[i][sum] += dp[i - 1][sum - faceValue];
}
}
}
ModNumber result;
for (int i = 0; i <= maxSum; i++) {
result += dp[diceCount][i];
}
cout << result.value << '\n';
return 0;
}
Problem 3: Ubiquity
Approach Each position has 10 possible digits, giving a total of \(10^N\) combinations. When we subtract combinations containing only digits 0-9 (which is \(9^N\)), we over-subtract the cases where both 0 and 9 appear. By inclusion-exclusion principle, we need to add back \(8^N\). The final formula becomes: \[10^N - 2 \times 9^N + 8^N\] We can compute this using fast exponentiation.
Implementation
#include <bits/stdc++.h>
using ll = long long;
ll modPow(ll base, ll exp, ll mod) {
ll result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const ll MOD = 998244353;
int length;
cin >> length;
ll answer = modPow(10, length, MOD);
answer = (answer - 2 * modPow(9, length, MOD) % MOD + MOD) % MOD;
answer = (answer + modPow(8, length, MOD)) % MOD;
cout << answer << '\n';
return 0;
}
Problem 4: FG Operation
Approach This problem involves repeatedly deleting the first two numbers while applying two operations: addition and multiplication with the remaining number. We use dynamic programming where dp[i][j] represents the number of valid sequences after processing the first i numbers, where the current value of (x+y)%10 equals j. The transition equations are: \[dp_{i,(j+a_i)\bmod 10} += dp_{i-1,j}\] \[dp_{i,(j \times a_i)\bmod 10} += dp_{i-1,j}\]
Implementation
#include <bits/stdc++.h>
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> arr(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
vector<vector<ll>> dp(n + 1, vector<ll>(10, 0));
dp[1][arr[1] % 10] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
int multiplyResult = (j * arr[i]) % 10;
int addResult = (j + arr[i]) % 10;
dp[i][multiplyResult] += dp[i - 1][j];
dp[i][addResult] += dp[i - 1][j];
}
}
for (int i = 0; i <= 9; i++) {
cout << dp[n][i] << '\n';
}
return 0;
}
Problem 5: Left Right Operation
Approach We compute prefix minimums and suffix minimums. For each position i, we determine the minimum possible sum of elements to the left (considering the constraint that each prefix element is at most l times its position) and the minimum possible sum of elements to the right (considering the constraint that each suffix element is at most r times its remaining positions). The answer is the minimum of pre[i] + suf[i+1] for all i.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64 n, minVal, maxVal;
cin >> n >> minVal >> maxVal;
vector<int64> arr(n + 1), prefixMin(n + 1), suffixMin(n + 2);
for (int i = 1; i <= n; i++) {
cin >> arr[i];
prefixMin[i] = prefixMin[i - 1] + arr[i];
}
for (int i = 0; i <= n; i++) {
prefixMin[i] = min(prefixMin[i], i * minVal);
}
for (int i = n; i >= 1; i--) {
suffixMin[i] = min(suffixMin[i + 1] + arr[i], (n - i + 1) * maxVal);
}
int64 answer = LLONG_MAX;
for (int i = 0; i <= n; i++) {
answer = min(answer, prefixMin[i] + suffixMin[i + 1]);
}
cout << answer << '\n';
return 0;
}
Problem 6: Add and Mex
Approach According to the properties of mex, only values within [0, N] contribute to the answer. The maximum possible mex is N + 1. Since we add i to a number each time, a value will exceed N after approximately N/i additions. For each value a_i, it contributes to the answer within the range: \[0 \le a_i + k \times i \le N\] which gives us: \[k \in \left[\left\lceil\frac{-a_i}{i}\right\rceil, \left\lfloor\frac{N-a_i}{i}\right\rfloor\right]\] The total complexity becomes O(n log n) due to the harmonic series property.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<set<int>> contribution(m + 1);
for (int i = 1; i <= n; i++) {
int val;
cin >> val;
int leftBound = max((-val + i - 1) / i, 0);
int rightBound = max((n - val) / i, 0);
val += leftBound * i;
for (int k = leftBound; k <= min(rightBound, m); k++, val += i) {
contribution[k].insert(val);
}
}
for (int query = 1; query <= m; query++) {
int mexValue = 0;
while (contribution[query].count(mexValue)) {
mexValue++;
}
cout << mexValue << '\n';
}
return 0;
}
Problem 7: Diameter Set
Approach By the properties of tree diameters, every diameter of a tree passes through either a common vertex or a common edge. To find the set of vertices separated by distance D (the tree's diameter), we consider the tree's center as the root.
When the diameter length is even: A central vertex exists. We need to find vertices at distance D/2 from the center. For each child subtree of the center, let cnt be the number of valid vertices. Since vertices within the same subtree cannot form a valid diameter (their path won't pass through the center), and each subtree can conrtibute cnt + 1 ways (cnt selections or no selection), the answer is: \[\prod_{v \in son_{mid}}(cnt_v + 1) - \sum_{v \in son_{mid}} cnt_v - 1\]
When the diameter length is odd: A central edge exists. The answer is simply cnt_1 × cnt_2, where cnt_1 and cnt_2 are the counts from the two sides of the edge.
Implementation
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
class Tree {
public:
int vertexCount;
int diameter;
vector<int> maxDepth1, maxDepth2, parent1, parent2, upward;
vector<vector<int>> adjacency;
Tree(int n) : vertexCount(n), diameter(0),
maxDepth1(n + 1), maxDepth2(n + 1),
parent1(n + 1), parent2(n + 1),
upward(n + 1), adjacency(n + 1) {}
void addEdge(int u, int v) {
adjacency[u].push_back(v);
adjacency[v].push_back(u);
}
void dfs(int node, int parent) {
maxDepth1[node] = maxDepth2[node] = 0;
for (int neighbor : adjacency[node]) {
if (neighbor == parent) continue;
dfs(neighbor, node);
int candidate = maxDepth1[neighbor] + 1;
if (candidate > maxDepth1[node]) {
maxDepth2[node] = maxDepth1[node];
parent2[node] = parent1[node];
maxDepth1[node] = candidate;
parent1[node] = neighbor;
} else if (candidate > maxDepth2[node]) {
maxDepth2[node] = candidate;
parent2[node] = neighbor;
}
}
diameter = max(diameter, maxDepth1[node] + maxDepth2[node]);
}
void dfsUp(int node, int parent) {
for (int neighbor : adjacency[node]) {
if (neighbor == parent) continue;
if (parent1[node] == neighbor) {
upward[neighbor] = max(upward[node], maxDepth2[node]) + 1;
} else {
upward[neighbor] = max(upward[node], maxDepth1[node]) + 1;
}
dfsUp(neighbor, node);
}
}
int findDiameter() {
dfs(1, 0);
return diameter;
}
vector<int> findCenter() {
dfsUp(1, 0);
int bestValue = INT_MAX;
vector<int> centers;
for (int i = 1; i <= vertexCount; i++) {
int currentMax = max(maxDepth1[i], upward[i]);
if (currentMax < bestValue) {
bestValue = currentMax;
centers.clear();
centers.push_back(i);
} else if (currentMax == bestValue) {
centers.push_back(i);
}
}
return centers;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
Tree tree(n);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
tree.addEdge(u, v);
}
const int64 MOD = 998244353;
int D = tree.findDiameter();
vector<int> center = tree.findCenter();
function<int(int, int, int, int)> countAtDepth = [&](int node, int parent, int currentDist, int targetDist) -> int {
int count = 0;
if (currentDist == targetDist) {
count++;
}
for (int neighbor : tree.adjacency[node]) {
if (neighbor == parent) continue;
count += countAtDepth(neighbor, node, currentDist + 1, targetDist);
}
return count;
};
if (D % 2 == 0) {
int64 answer = 1;
int64 invalid = 0;
int targetDepth = D / 2 - 1;
for (int child : tree.adjacency[center[0]]) {
int cnt = countAtDepth(child, center[0], 0, targetDepth);
answer = (answer * (cnt + 1)) % MOD;
invalid += cnt;
}
cout << ((answer - invalid - 1) % MOD + MOD) % MOD << '\n';
} else {
int targetDepth = D / 2;
int64 cnt1 = countAtDepth(center[0], center[1], 0, targetDepth);
int64 cnt2 = countAtDepth(center[1], center[0], 0, targetDepth);
cout << (cnt1 * cnt2) % MOD << '\n';
}
return 0;
}