Problem A: Plus Minus
Given the sum and difference of two numbers, we can easily retrieve the original values. The first number is the average of the sum and difference, while the second is half of the difference subtracted from the sum.
s, d = map(int, input().split())
print((s + d) // 2, (s - d) // 2)
Problem B: DNA Sequence
A substring is considered complementary if the count of 'A' equals 'T' and the count of 'C' equals 'G'. We can iterate over all possible starting positions and expand the substring while maintaining character frequencies. Whenever the balance conditions are met, we increment our result. This approach operates in quadratic time complexity.
#include <iostream>
#include <string>
using namespace std;
int main() {
int len;
string seq;
cin >> len >> seq;
int total = 0;
for (int i = 0; i < len; ++i) {
int cntA = 0, cntT = 0, cntC = 0, cntG = 0;
for (int j = i; j < len; ++j) {
if (seq[j] == 'A') cntA++;
else if (seq[j] == 'T') cntT++;
else if (seq[j] == 'C') cntC++;
else if (seq[j] == 'G') cntG++;
if (cntA == cntT && cntC == cntG) total++;
}
}
cout << total << endl;
return 0;
}
Problem C: Fair Elevator
We have an elevator traversing $2N$ floors with $N$ passengers. Passenger $i$ boards at floor $u_i$ and alights at $v_i$. A key constraint states that if any two passengers share the elevator, their travel durations ($v_i - u_i$) must be identical. Some boarding and alighting data is missing, and we must determine if we can fill the gaps to form a valid scenario.
A crucial observation is that the sequence of floors can be partitioned into independent "closed" blocks. Within a valid block of length $2L$, the first $L$ floors must be exclusive for boarding, and the subsequent $L$ floors are for alighting. Furthermore, the passenger boarding at the $k$-th floor of the block must alight at the $(k+L)$-th floor of the block.
We can apply dynamic programming where dp[i] indicates whether the first i floors can be successfully partitioned. To transition, we check if a subsegment [j...i] can constitute a valid closed block. The validation ensures that existing entry data aligns with the first half and exit data with the second half, without contradictions. The overall time complexity is $O(N^3)$.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> entry(n + 1), exit_f(n + 1);
vector<int> floor_person(2 * n + 1);
vector<int> floor_count(2 * n + 1);
for (int i = 1; i <= n; ++i) {
cin >> entry[i] >> exit_f[i];
if (entry[i] != -1 && exit_f[i] != -1 && entry[i] >= exit_f[i]) {
cout << "No\n"; return 0;
}
if (entry[i] != -1) {
floor_count[entry[i]]++;
floor_person[entry[i]] = i;
}
if (exit_f[i] != -1) {
floor_count[exit_f[i]]++;
floor_person[exit_f[i]] = -i;
}
}
for (int i = 1; i <= 2 * n; ++i) {
if (floor_count[i] > 1) {
cout << "No\n"; return 0;
}
}
auto isValid = [&](int L, int R) {
int span = (R - L + 1) / 2;
for (int i = L; i <= R; ++i) {
int p = floor_person[i];
if (p > 0 && exit_f[p] != -1 && exit_f[p] > R) return false;
if (p < 0 && entry[-p] != -1 && entry[-p] < L) return false;
}
for (int i = 0; i < span; ++i) {
int in_p = floor_person[L + i];
int out_p = floor_person[L + i + span];
if (in_p < 0) return false;
if (out_p > 0) return false;
if (in_p != 0 && out_p != 0 && in_p + out_p != 0) return false;
}
return true;
};
vector<bool> dp(2 * n + 1, false);
dp[0] = true;
for (int i = 1; i <= 2 * n; ++i) {
for (int len = 2; len <= i; len += 2) {
int L = i - len + 1;
if (dp[L - 1] && isValid(L, i)) dp[i] = true;
}
}
cout << (dp[2 * n] ? "Yes" : "No") << "\n";
return 0;
}
Problem D: Multiset Mean
We are given $N$ and $K$. For every $x \in [1, N]$, we need to find the number of multisets containing integers from $1$ to $N$ (each appearing $0$ to $K$ times) such that the average of the multiset equals $x$.
A multiset has an average of $x$ if and only if the sum of differences $\sum_{i \in S} (i - x) = 0$. This implies that the sum of differences for elements strictly less than $x$ must equal the sum of absolute differences for elements strictly greater than $x$.
We can compute a bounded knapsack DP, where dp[i][s] is the number of ways to select elements up to i such that their total sum is s. Because we are counting combinations, the standard monotonic queue optimization can be simplified: since addition is invertible, we maintain a rolling prefix sum and simply subtract the states that fall out of the bounded window (when an element is chosen more than $K$ times). This yields an $O(N^3 K)$ complexity, which passes comfortably.
For a specific $x$, the answer is $(K+1) \times \sum_{s} dp[x-1][s] \times dp[N-x][s] - 1$.
#include <iostream>
#include <vector>
using namespace std;
int main() {
int max_val, max_freq, modulus;
cin >> max_val >> max_freq >> modulus;
int max_sum = max_val * max_val * max_freq;
vector<vector<int>> dp(max_val + 2, vector<int>(max_sum + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= max_val; ++i) {
vector<int> prefix(i, 0);
for (int s = 0; s <= max_sum; ++s) {
int mod_idx = s % i;
prefix[mod_idx] += dp[i - 1][s];
if (prefix[mod_idx] >= modulus) prefix[mod_idx] -= modulus;
if (s >= (max_freq + 1) * i) {
prefix[mod_idx] -= dp[i - 1][s - (max_freq + 1) * i];
if (prefix[mod_idx] < 0) prefix[mod_idx] += modulus;
}
dp[i][s] = prefix[mod_idx];
}
}
for (int x = 1; x <= max_val; ++x) {
int result = 0;
for (int s = 0; s <= max_sum; ++s) {
long long prod = 1LL * dp[x - 1][s] * dp[max_val - x][s] % modulus;
result += prod;
if (result >= modulus) result -= modulus;
}
long long final_ans = (1LL * result * (max_freq + 1) - 1 + modulus) % modulus;
cout << final_ans << "\n";
}
return 0;
}
Problem E: Random LIS
Given $N$ upper bounds $a_i$, we randomly generate a sequence $x_i$ where each $x_i$ is uniformly chosen from $[1, a_i]$. The task is to compute the expected length of the Longest Increasing Subsequence (LIS).
Since $N \le 6$, we can enumerate all possible relative orderings of $x_1, \dots, x_N$. This corresponds to generating all ordered set partitions, counted by Fubini numbers. For each valid ordering, the LIS length is deterministic and easily found via standard DP.
The main challenge is calculating the number of valid value asignments for a given relative ordering. We first coordinate compress the bounds $a_i$ to divide the value range into intervals. We then use a DP where dp[i][j] represents the number of ways to assign values to the first i ordered groups such that the i-th group is placed within the j-th interval.
During the transition, we consider the possibility that consecutive groups might fall into the same interval. We iterate backwards to find the leftmost group sharing the interval with group $i$, multiplying by the necessary combinations to select distinct values for elements within the same interval. This polynomial-time DP replaces the need for exponential brute force over interval assignments.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
long long power(long long base, int exp) {
long long res = 1;
while (exp) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
int modInverse(int x) { return power(x, MOD - 2); }
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> coords;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
coords.push_back(a[i]);
}
sort(coords.begin(), coords.end());
coords.erase(unique(coords.begin(), coords.end()), coords.end());
int m = coords.size();
auto getLen = [&](int idx) {
if (idx == 0) return coords[idx];
return coords[idx] - coords[idx - 1];
};
auto nCr = [&](int x, int y) -> int {
if (x < y) return 0;
long long res = 1;
for (int i = x - y + 1; i <= x; ++i) res = res * i % MOD;
for (int i = 1; i <= y; ++i) res = res * modInverse(i) % MOD;
return res;
};
int total_ways = 1;
for (int i = 1; i <= n; ++i) total_ways = 1LL * total_ways * a[i] % MOD;
int expected_lis = 0;
vector<int> ranks(n + 1);
function<void(int)> solveRanks = [&](int idx) {
if (idx > n) {
int max_rank = *max_element(ranks.begin() + 1, ranks.end());
vector<bool> seen(max_rank + 1, false);
for (int i = 1; i <= n; ++i) seen[ranks[i]] = true;
for (int i = 1; i <= max_rank; ++i) if (!seen[i]) return;
vector<int> lis_dp(n + 1, 1);
int lis_len = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if (ranks[j] < ranks[i]) lis_dp[i] = max(lis_dp[i], lis_dp[j] + 1);
}
lis_len = max(lis_len, lis_dp[i]);
}
vector<int> min_bound(max_rank + 1, MOD);
for (int i = 1; i <= n; ++i) min_bound[ranks[i]] = min(min_bound[ranks[i]], a[i]);
vector<vector<int>> dp(max_rank + 1, vector<int>(m + 1, 0));
for (int j = 0; j <= m; ++j) dp[0][j] = 1;
for (int i = 1; i <= max_rank; ++i) {
for (int j = 0; j < m; ++j) {
if (coords[j] > min_bound[i]) break;
for (int k = i; k >= 1; --k) {
if (coords[j] > min_bound[k]) break;
dp[i][j + 1] = (dp[i][j + 1] + 1LL * nCr(getLen(j), i - k + 1) * dp[k - 1][j]) % MOD;
}
}
for (int j = 1; j <= m; ++j) {
dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
}
}
expected_lis = (expected_lis + 1LL * lis_len * dp[max_rank][m]) % MOD;
return;
}
for (int r = 1; r <= n; ++r) {
ranks[idx] = r;
solveRanks(idx + 1);
}
};
solveRanks(1);
cout << 1LL * expected_lis * modInverse(total_ways) % MOD << "\n";
return 0;
}