↵
↵
<spoiler summary="Problem A: Hardest Matrix Leap Year">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Given an operational year Y and a calibration interval k, find the number of years until the next strict future multiple of k.</li>↵
<li><b>Key Intuition:</b> The next strict multiple is given by k — (Y % k).</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Formula:</b> Writing Y = q * k + r with 0 <= r < k, the distance is k — r.</li>↵
<li><b>Time Complexity:</b> O(1) per testcase.</li>↵
<li><b>Space Complexity:</b> O(1) extra space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
↵
using namespace std;↵
↵
void solve() {↵
long long year, interval;↵
cin >> year >> interval;↵
long long remainder = year % interval;↵
long long answer = interval — remainder;↵
cout << answer << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B: Doctor Doom's Energy Stones">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Given N stone weights and a container weight capacity K, maximize the total count of stones selected such that their total weight does not exceed K.</li>↵
<li><b>Key Intuition:</b> To maximize the item count under a fixed capacity limit, always pick the lightest available items first (classic greedy strategy).</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Sort the array of weights in ascending order w1 <= w2 <= ... <= wN. Greedily accumulate weights starting from the smallest until adding the next stone exceeds capacity K.</li>↵
<li><b>Time Complexity:</b> O(N log N) per testcase due to sorting.</li>↵
<li><b>Space Complexity:</b> O(N) space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
void solve() {↵
int n;↵
long long capacity;↵
cin >> n >> capacity;↵
↵
vector<long long> weights(n);↵
for (int i = 0; i < n; i++) {↵
cin >> weights[i];↵
}↵
↵
sort(weights.begin(), weights.end());↵
↵
long long current_sum = 0;↵
int count = 0;↵
↵
for (int i = 0; i < n; i++) {↵
if (current_sum + weights[i] > capacity) {↵
break;↵
}↵
current_sum += weights[i];↵
count++;↵
}↵
↵
cout << count << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem C: The Doom Protocol">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> We may flip signs of a prefix of length p and a disjoint suffix of length q (p + q <= n) of an array. Flipping position i costs 2|a_i| if i is even and |a_i| if i is odd. Find the minimum total cost so that the array sums to exactly S, or output -1.</li>↵
<li><b>Key Intuition:</b> Flipping a_i changes the total sum by -2a_i. If total sum is T, the sum of flipped elements must equal K = (T — S) / 2. If T — S is odd, no solution exists.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Precompute prefix sums/costs and suffix sums/costs. As prefix length p decreases from n down to 0, maintain a hash map storing the minimum cost to achieve each suffix sum seen so far. For each prefix p, query the map for the required remaining sum K — prefSum[p].</li>↵
<li><b>Time Complexity:</b> O(N) amortized per test case.</li>↵
<li><b>Space Complexity:</b> O(N) extra space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <cmath>↵
#include <unordered_map>↵
↵
using namespace std;↵
↵
const long long INF = 1e18;↵
↵
void solve() {↵
int n;↵
long long target_sum;↵
cin >> n >> target_sum;↵
↵
vector<long long> a(n + 1);↵
vector<long long> flip_cost(n + 1);↵
long long total_sum = 0;↵
↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
total_sum += a[i];↵
long long val = abs(a[i]);↵
flip_cost[i] = (i % 2 == 0) ? 2 * val : val;↵
}↵
↵
long long diff = total_sum — target_sum;↵
if (diff % 2 != 0) {↵
cout << -1 << "\n";↵
return;↵
}↵
↵
long long required_sum = diff / 2;↵
↵
vector<long long> pref_sum(n + 1, 0), pref_cost(n + 1, 0);↵
for (int i = 1; i <= n; i++) {↵
pref_sum[i] = pref_sum[i — 1] + a[i];↵
pref_cost[i] = pref_cost[i — 1] + flip_cost[i];↵
}↵
↵
vector<long long> suff_sum(n + 2, 0), suff_cost(n + 2, 0);↵
for (int i = n; i >= 1; i--) {↵
suff_sum[i] = suff_sum[i + 1] + a[i];↵
suff_cost[i] = suff_cost[i + 1] + flip_cost[i];↵
}↵
↵
unordered_map<long long, long long> best_suffix_cost;↵
long long min_total_cost = INF;↵
↵
for (int p = n; p >= 0; p--) {↵
int idx = p + 1;↵
if (idx <= n + 1) {↵
long long s_val = suff_sum[idx];↵
long long c_val = suff_cost[idx];↵
if (best_suffix_cost.find(s_val) == best_suffix_cost.end() || c_val < best_suffix_cost[s_val]) {↵
best_suffix_cost[s_val] = c_val;↵
}↵
}↵
↵
long long need = required_sum — pref_sum[p];↵
if (best_suffix_cost.find(need) != best_suffix_cost.end()) {↵
long long candidate = pref_cost[p] + best_suffix_cost[need];↵
min_total_cost = min(min_total_cost, candidate);↵
}↵
}↵
↵
if (min_total_cost >= INF) {↵
cout << -1 << "\n";↵
} else {↵
cout << min_total_cost << "\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem D: Saturn's Moon Alignment">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> For each energy value A, find the smallest k >= 0 such that adding k^2 yields a perfect square. If impossible, set A = 1 with k = 0. Output max k used and modified array.</li>↵
<li><b>Key Intuition:</b> We need M^2 — k^2 = A <=> (M — k)(M + k) = A. Setting u = M — k and v = M + k, u * v = A with u and v having the same parity. Minimizing k = (v — u) / 2 requires choosing divisor u <= sqrt(A) as close to sqrt(A) as possible. If A % 4 == 2, no matching-parity factors exist, forcing A -> 1.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Scan u downwards from floor(sqrt(A)) to 1. The first divisor found where A / u has matching parity gives the minimum gap v — u and thus minimal k.</li>↵
<li><b>Time Complexity:</b> O(N sqrt(max A)) time.</li>↵
<li><b>Space Complexity:</b> O(N) space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <cmath>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
pair<long long, long long> solve_single(long long a) {↵
long long sq = round(sqrt((double)a));↵
if (sq * sq == a) {↵
return {0, a};↵
}↵
if (a % 2 != 0 && (a % 4 == 2)) {↵
return {0, 1};↵
}↵
if (a % 4 == 2) {↵
return {0, 1};↵
}↵
↵
long long best_u = -1;↵
for (long long u = sq; u >= 1; u--) {↵
if (a % u == 0) {↵
long long v = a / u;↵
if ((v — u) % 2 == 0) {↵
best_u = u;↵
break;↵
}↵
}↵
}↵
↵
if (best_u == -1) {↵
return {0, 1};↵
}↵
↵
long long v = a / best_u;↵
long long k = (v — best_u) / 2;↵
long long m = (v + best_u) / 2;↵
return {k, m * m};↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n;↵
if (!(cin >> n)) return 0;↵
↵
vector<long long> final_energies(n);↵
long long max_k = 0;↵
↵
for (int i = 0; i < n; i++) {↵
long long a;↵
cin >> a;↵
auto [k, energy] = solve_single(a);↵
max_k = max(max_k, k);↵
final_energies[i] = energy;↵
}↵
↵
cout << max_k << "\n";↵
for (int i = 0; i < n; i++) {↵
cout << final_energies[i] << (i == n — 1 ? "" : " ");↵
}↵
cout << "\n";↵
↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem E: Doctor Doom's Binary Dominion">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Split binary string S of length N into K non-empty contiguous parts (each length <= 31) to maximize sum(i * value(P_i)).</li>↵
<li><b>Key Intuition:</b> Because each part length is bounded by 31 bits, we can use interval dynamic programming with memoization dp(pos, parts_left) where each state transitions into at most 31 choices.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Base case dp(N, 0) = 0. For state (pos, parts_left), iterate ending index end from pos up to min(N-1, pos + 30). Compute binary integer value iteratively and transition to dp(end + 1, parts_left — 1).</li>↵
<li><b>Time Complexity:</b> O(31 * N * K) total operations.</li>↵
<li><b>Space Complexity:</b> O(N * K) space for memo table.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <algorithm>↵
#include <climits>↵
↵
using namespace std;↵
↵
const long long INF = 1e18;↵
↵
long long solve_dp(const string &s, int pos, int parts_left, int total_k, vector<vector<long long>> &dp) {↵
int n = s.length();↵
if (pos == n) {↵
return parts_left == 0 ? 0 : -INF;↵
}↵
if (n — pos < parts_left || parts_left <= 0) {↵
return -INF;↵
}↵
if (dp[pos][parts_left] != -1) {↵
return dp[pos][parts_left];↵
}↵
↵
int part_number = total_k — parts_left + 1;↵
long long best = -INF;↵
long long val = 0;↵
↵
for (int end = pos; end < min(n, pos + 31); end++) {↵
val = (val << 1) + (s[end] — '0');↵
long long rest = solve_dp(s, end + 1, parts_left — 1, total_k, dp);↵
if (rest != -INF) {↵
best = max(best, part_number * val + rest);↵
}↵
}↵
↵
return dp[pos][parts_left] = best;↵
}↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
string s;↵
cin >> s;↵
↵
vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, -1));↵
long long ans = solve_dp(s, 0, k, k, dp);↵
cout << ans << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem F: Quantum Chain">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Grid pathfinding from top-left to bottom-right. Pick one light frequency from sorted base array B shifted by cell energy G_{r,c}. Chosen frequencies must strictly increase along path. Minimize total cost sum(10^6 — F) or print DOOMED.</li>↵
<li><b>Key Intuition:</b> Maintain running prefix minimum arrays for candidate light frequencies. Monotonic two-pointer updates allow finding the best strictly smaller frequency predecessor from the top or left cell in amortized O(1) time.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Sort base frequencies B ascending. Iterating through cells (r, c), maintain idx_top and idx_left pointers advancing monotonically to query pref[c][idx_top — 1] and pref[c — 1][idx_left — 1]. Use rolling 1D DP arrays over grid rows to optimize memory.</li>↵
<li><b>Time Complexity:</b> O(N * M * K) total time.</li>↵
<li><b>Space Complexity:</b> O(M * K) memory using rolling arrays.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
const long long INF = 1e18;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n, m, k;↵
if (!(cin >> n >> m >> k)) return 0;↵
↵
vector<long long> b(k);↵
for (int i = 0; i < k; i++) {↵
cin >> b[i];↵
}↵
sort(b.begin(), b.end());↵
↵
vector<long long> prev_grid(m), curr_grid(m);↵
vector<vector<long long>> prev_pref(m, vector<long long>(k, INF));↵
vector<vector<long long>> curr_pref(m, vector<long long>(k, INF));↵
↵
for (int r = 0; r < n; r++) {↵
for (int c = 0; c < m; c++) {↵
cin >> curr_grid[c];↵
long long g_curr = curr_grid[c];↵
long long g_top = (r > 0) ? prev_grid[c] : 0;↵
long long g_left = (c > 0) ? curr_grid[c — 1] : 0;↵
↵
long long running_min = INF;↵
int idx_top = 0, idx_left = 0;↵
↵
for (int i = 0; i < k; i++) {↵
long long f = g_curr + b[i];↵
↵
if (r > 0) {↵
while (idx_top < k && g_top + b[idx_top] < f) {↵
idx_top++;↵
}↵
}↵
if (c > 0) {↵
while (idx_left < k && g_left + b[idx_left] < f) {↵
idx_left++;↵
}↵
}↵
↵
long long best_prev = INF;↵
if (r == 0 && c == 0) {↵
best_prev = 0;↵
} else {↵
if (r > 0 && idx_top > 0) {↵
best_prev = min(best_prev, prev_pref[c][idx_top — 1]);↵
}↵
if (c > 0 && idx_left > 0) {↵
best_prev = min(best_prev, curr_pref[c — 1][idx_left — 1]);↵
}↵
}↵
↵
if (best_prev != INF) {↵
running_min = min(running_min, best_prev + (1000000LL — f));↵
}↵
curr_pref[c][i] = running_min;↵
}↵
}↵
↵
for (int c = 0; c < m; c++) {↵
prev_grid[c] = curr_grid[c];↵
for (int i = 0; i < k; i++) {↵
prev_pref[c][i] = curr_pref[c][i];↵
}↵
}↵
}↵
↵
long long ans = prev_pref[m — 1][k — 1];↵
if (ans >= INF) {↵
cout << "DOOMED\n";↵
} else {↵
cout << ans << "\n";↵
}↵
↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem G: Doom's Palindromic Matrix">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Calculate range sums of distinct palindromic subsequence counts f_x(i) over Pascal matrix rows i in [L, R] truncated at column x modulo 998244353.</li>↵
<li><b>Key Intuition:</b> The structural behavior of row i splits i into three main mathematical regions relative to limit x:↵
<ol>↵
<li><b>Region 1 (i <= x):</b> Full symmetric row, geometric sums of powers of 2 based on even/odd parity.</li>↵
<li><b>Region 2 (x < i <= 2x+1):</b> Partially folded row, capped symmetric pair counts.</li>↵
<li><b>Region 3 (i >= 2x+2):</b> Strictly increasing window, constant x + 1 distinct elements per row.</li>↵
</ol>↵
</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Evaluate contributions from each region using logarithmic power function power_two and range exponent sum formula sum_pow.</li>↵
<li><b>Time Complexity:</b> O(Q log MOD) time.</li>↵
<li><b>Space Complexity:</b> O(1) space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
const long long MOD = 998244353;↵
↵
long long power_two(long long exp) {↵
long long res = 1;↵
long long base = 2;↵
while (exp > 0) {↵
if (exp % 2 == 1) res = (res * base) % MOD;↵
base = (base * base) % MOD;↵
exp /= 2;↵
}↵
return res;↵
}↵
↵
long long sum_pow(long long low, long long high) {↵
if (low > high) return 0;↵
long long val_high = power_two(high + 1);↵
long long val_low = power_two(low);↵
return (val_high — val_low + MOD) % MOD;↵
}↵
↵
void solve_query() {↵
long long l, r, x;↵
if (!(cin >> l >> r >> x)) return;↵
↵
long long total = 0;↵
↵
long long r1_start = l, r1_end = min(r, x);↵
if (r1_start <= r1_end) {↵
long long res = 0;↵
↵
long long even_start = (r1_start % 2 == 0) ? r1_start : r1_start + 1;↵
long long even_end = (r1_end % 2 == 0) ? r1_end : r1_end — 1;↵
if (even_start <= even_end) {↵
long long count = (even_end — even_start) / 2 + 1;↵
long long sp = sum_pow(even_start / 2, even_end / 2);↵
res = (res + 3 * sp % MOD * (count % MOD)) % MOD;↵
}↵
↵
long long odd_start = (r1_start % 2 != 0) ? r1_start : r1_start + 1;↵
long long odd_end = (r1_end % 2 != 0) ? r1_end : r1_end — 1;↵
if (odd_start <= odd_end) {↵
long long count = (odd_end — odd_start) / 2 + 1;↵
long long sp = sum_pow((odd_start + 1) / 2, (odd_end + 1) / 2);↵
res = (res + 2 * sp % MOD * (count % MOD)) % MOD;↵
}↵
↵
total = (total + res) % MOD;↵
}↵
↵
long long r2_start = max(l, x + 1), r2_end = min(r, 2 * x + 1);↵
if (r2_start <= r2_end) {↵
long long res = 0;↵
↵
long long even_start = (r2_start % 2 == 0) ? r2_start : r2_start + 1;↵
long long even_end = (r2_end % 2 == 0) ? r2_end : r2_end — 1;↵
if (even_start <= even_end) {↵
long long sp = sum_pow(x — even_end / 2, x — even_start / 2);↵
res = (res + 3 * sp) % MOD;↵
}↵
↵
long long odd_start = (r2_start % 2 != 0) ? r2_start : r2_start + 1;↵
long long odd_end = (r2_end % 2 != 0) ? r2_end : r2_end — 1;↵
if (odd_start <= odd_end) {↵
long long sp = sum_pow(x — (odd_end + 1) / 2, x — (odd_start + 1) / 2);↵
res = (res + 2 * sp) % MOD;↵
}↵
↵
total = (total + res) % MOD;↵
}↵
↵
long long r3_start = max(l, 2 * x + 2), r3_end = r;↵
if (r3_start <= r3_end) {↵
long long count = r3_end — r3_start + 1;↵
total = (total + (x + 1) % MOD * (count % MOD)) % MOD;↵
}↵
↵
cout << total << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int q;↵
if (cin >> q) {↵
while (q--) {↵
solve_query();↵
}↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Problem A: Hardest Matrix Leap Year">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Given an operational year Y and a calibration interval k, find the number of years until the next strict future multiple of k.</li>↵
<li><b>Key Intuition:</b> The next strict multiple is given by k — (Y % k).</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Formula:</b> Writing Y = q * k + r with 0 <= r < k, the distance is k — r.</li>↵
<li><b>Time Complexity:</b> O(1) per testcase.</li>↵
<li><b>Space Complexity:</b> O(1) extra space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
↵
using namespace std;↵
↵
void solve() {↵
long long year, interval;↵
cin >> year >> interval;↵
long long remainder = year % interval;↵
long long answer = interval — remainder;↵
cout << answer << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem B: Doctor Doom's Energy Stones">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Given N stone weights and a container weight capacity K, maximize the total count of stones selected such that their total weight does not exceed K.</li>↵
<li><b>Key Intuition:</b> To maximize the item count under a fixed capacity limit, always pick the lightest available items first (classic greedy strategy).</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Sort the array of weights in ascending order w1 <= w2 <= ... <= wN. Greedily accumulate weights starting from the smallest until adding the next stone exceeds capacity K.</li>↵
<li><b>Time Complexity:</b> O(N log N) per testcase due to sorting.</li>↵
<li><b>Space Complexity:</b> O(N) space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
void solve() {↵
int n;↵
long long capacity;↵
cin >> n >> capacity;↵
↵
vector<long long> weights(n);↵
for (int i = 0; i < n; i++) {↵
cin >> weights[i];↵
}↵
↵
sort(weights.begin(), weights.end());↵
↵
long long current_sum = 0;↵
int count = 0;↵
↵
for (int i = 0; i < n; i++) {↵
if (current_sum + weights[i] > capacity) {↵
break;↵
}↵
current_sum += weights[i];↵
count++;↵
}↵
↵
cout << count << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem C: The Doom Protocol">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> We may flip signs of a prefix of length p and a disjoint suffix of length q (p + q <= n) of an array. Flipping position i costs 2|a_i| if i is even and |a_i| if i is odd. Find the minimum total cost so that the array sums to exactly S, or output -1.</li>↵
<li><b>Key Intuition:</b> Flipping a_i changes the total sum by -2a_i. If total sum is T, the sum of flipped elements must equal K = (T — S) / 2. If T — S is odd, no solution exists.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Precompute prefix sums/costs and suffix sums/costs. As prefix length p decreases from n down to 0, maintain a hash map storing the minimum cost to achieve each suffix sum seen so far. For each prefix p, query the map for the required remaining sum K — prefSum[p].</li>↵
<li><b>Time Complexity:</b> O(N) amortized per test case.</li>↵
<li><b>Space Complexity:</b> O(N) extra space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <cmath>↵
#include <unordered_map>↵
↵
using namespace std;↵
↵
const long long INF = 1e18;↵
↵
void solve() {↵
int n;↵
long long target_sum;↵
cin >> n >> target_sum;↵
↵
vector<long long> a(n + 1);↵
vector<long long> flip_cost(n + 1);↵
long long total_sum = 0;↵
↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
total_sum += a[i];↵
long long val = abs(a[i]);↵
flip_cost[i] = (i % 2 == 0) ? 2 * val : val;↵
}↵
↵
long long diff = total_sum — target_sum;↵
if (diff % 2 != 0) {↵
cout << -1 << "\n";↵
return;↵
}↵
↵
long long required_sum = diff / 2;↵
↵
vector<long long> pref_sum(n + 1, 0), pref_cost(n + 1, 0);↵
for (int i = 1; i <= n; i++) {↵
pref_sum[i] = pref_sum[i — 1] + a[i];↵
pref_cost[i] = pref_cost[i — 1] + flip_cost[i];↵
}↵
↵
vector<long long> suff_sum(n + 2, 0), suff_cost(n + 2, 0);↵
for (int i = n; i >= 1; i--) {↵
suff_sum[i] = suff_sum[i + 1] + a[i];↵
suff_cost[i] = suff_cost[i + 1] + flip_cost[i];↵
}↵
↵
unordered_map<long long, long long> best_suffix_cost;↵
long long min_total_cost = INF;↵
↵
for (int p = n; p >= 0; p--) {↵
int idx = p + 1;↵
if (idx <= n + 1) {↵
long long s_val = suff_sum[idx];↵
long long c_val = suff_cost[idx];↵
if (best_suffix_cost.find(s_val) == best_suffix_cost.end() || c_val < best_suffix_cost[s_val]) {↵
best_suffix_cost[s_val] = c_val;↵
}↵
}↵
↵
long long need = required_sum — pref_sum[p];↵
if (best_suffix_cost.find(need) != best_suffix_cost.end()) {↵
long long candidate = pref_cost[p] + best_suffix_cost[need];↵
min_total_cost = min(min_total_cost, candidate);↵
}↵
}↵
↵
if (min_total_cost >= INF) {↵
cout << -1 << "\n";↵
} else {↵
cout << min_total_cost << "\n";↵
}↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem D: Saturn's Moon Alignment">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> For each energy value A, find the smallest k >= 0 such that adding k^2 yields a perfect square. If impossible, set A = 1 with k = 0. Output max k used and modified array.</li>↵
<li><b>Key Intuition:</b> We need M^2 — k^2 = A <=> (M — k)(M + k) = A. Setting u = M — k and v = M + k, u * v = A with u and v having the same parity. Minimizing k = (v — u) / 2 requires choosing divisor u <= sqrt(A) as close to sqrt(A) as possible. If A % 4 == 2, no matching-parity factors exist, forcing A -> 1.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Scan u downwards from floor(sqrt(A)) to 1. The first divisor found where A / u has matching parity gives the minimum gap v — u and thus minimal k.</li>↵
<li><b>Time Complexity:</b> O(N sqrt(max A)) time.</li>↵
<li><b>Space Complexity:</b> O(N) space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <cmath>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
pair<long long, long long> solve_single(long long a) {↵
long long sq = round(sqrt((double)a));↵
if (sq * sq == a) {↵
return {0, a};↵
}↵
if (a % 2 != 0 && (a % 4 == 2)) {↵
return {0, 1};↵
}↵
if (a % 4 == 2) {↵
return {0, 1};↵
}↵
↵
long long best_u = -1;↵
for (long long u = sq; u >= 1; u--) {↵
if (a % u == 0) {↵
long long v = a / u;↵
if ((v — u) % 2 == 0) {↵
best_u = u;↵
break;↵
}↵
}↵
}↵
↵
if (best_u == -1) {↵
return {0, 1};↵
}↵
↵
long long v = a / best_u;↵
long long k = (v — best_u) / 2;↵
long long m = (v + best_u) / 2;↵
return {k, m * m};↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n;↵
if (!(cin >> n)) return 0;↵
↵
vector<long long> final_energies(n);↵
long long max_k = 0;↵
↵
for (int i = 0; i < n; i++) {↵
long long a;↵
cin >> a;↵
auto [k, energy] = solve_single(a);↵
max_k = max(max_k, k);↵
final_energies[i] = energy;↵
}↵
↵
cout << max_k << "\n";↵
for (int i = 0; i < n; i++) {↵
cout << final_energies[i] << (i == n — 1 ? "" : " ");↵
}↵
cout << "\n";↵
↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem E: Doctor Doom's Binary Dominion">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Split binary string S of length N into K non-empty contiguous parts (each length <= 31) to maximize sum(i * value(P_i)).</li>↵
<li><b>Key Intuition:</b> Because each part length is bounded by 31 bits, we can use interval dynamic programming with memoization dp(pos, parts_left) where each state transitions into at most 31 choices.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Base case dp(N, 0) = 0. For state (pos, parts_left), iterate ending index end from pos up to min(N-1, pos + 30). Compute binary integer value iteratively and transition to dp(end + 1, parts_left — 1).</li>↵
<li><b>Time Complexity:</b> O(31 * N * K) total operations.</li>↵
<li><b>Space Complexity:</b> O(N * K) space for memo table.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <algorithm>↵
#include <climits>↵
↵
using namespace std;↵
↵
const long long INF = 1e18;↵
↵
long long solve_dp(const string &s, int pos, int parts_left, int total_k, vector<vector<long long>> &dp) {↵
int n = s.length();↵
if (pos == n) {↵
return parts_left == 0 ? 0 : -INF;↵
}↵
if (n — pos < parts_left || parts_left <= 0) {↵
return -INF;↵
}↵
if (dp[pos][parts_left] != -1) {↵
return dp[pos][parts_left];↵
}↵
↵
int part_number = total_k — parts_left + 1;↵
long long best = -INF;↵
long long val = 0;↵
↵
for (int end = pos; end < min(n, pos + 31); end++) {↵
val = (val << 1) + (s[end] — '0');↵
long long rest = solve_dp(s, end + 1, parts_left — 1, total_k, dp);↵
if (rest != -INF) {↵
best = max(best, part_number * val + rest);↵
}↵
}↵
↵
return dp[pos][parts_left] = best;↵
}↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
string s;↵
cin >> s;↵
↵
vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, -1));↵
long long ans = solve_dp(s, 0, k, k, dp);↵
cout << ans << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int test_cases;↵
cin >> test_cases;↵
while (test_cases--) {↵
solve();↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem F: Quantum Chain">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Grid pathfinding from top-left to bottom-right. Pick one light frequency from sorted base array B shifted by cell energy G_{r,c}. Chosen frequencies must strictly increase along path. Minimize total cost sum(10^6 — F) or print DOOMED.</li>↵
<li><b>Key Intuition:</b> Maintain running prefix minimum arrays for candidate light frequencies. Monotonic two-pointer updates allow finding the best strictly smaller frequency predecessor from the top or left cell in amortized O(1) time.</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Sort base frequencies B ascending. Iterating through cells (r, c), maintain idx_top and idx_left pointers advancing monotonically to query pref[c][idx_top — 1] and pref[c — 1][idx_left — 1]. Use rolling 1D DP arrays over grid rows to optimize memory.</li>↵
<li><b>Time Complexity:</b> O(N * M * K) total time.</li>↵
<li><b>Space Complexity:</b> O(M * K) memory using rolling arrays.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
const long long INF = 1e18;↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int n, m, k;↵
if (!(cin >> n >> m >> k)) return 0;↵
↵
vector<long long> b(k);↵
for (int i = 0; i < k; i++) {↵
cin >> b[i];↵
}↵
sort(b.begin(), b.end());↵
↵
vector<long long> prev_grid(m), curr_grid(m);↵
vector<vector<long long>> prev_pref(m, vector<long long>(k, INF));↵
vector<vector<long long>> curr_pref(m, vector<long long>(k, INF));↵
↵
for (int r = 0; r < n; r++) {↵
for (int c = 0; c < m; c++) {↵
cin >> curr_grid[c];↵
long long g_curr = curr_grid[c];↵
long long g_top = (r > 0) ? prev_grid[c] : 0;↵
long long g_left = (c > 0) ? curr_grid[c — 1] : 0;↵
↵
long long running_min = INF;↵
int idx_top = 0, idx_left = 0;↵
↵
for (int i = 0; i < k; i++) {↵
long long f = g_curr + b[i];↵
↵
if (r > 0) {↵
while (idx_top < k && g_top + b[idx_top] < f) {↵
idx_top++;↵
}↵
}↵
if (c > 0) {↵
while (idx_left < k && g_left + b[idx_left] < f) {↵
idx_left++;↵
}↵
}↵
↵
long long best_prev = INF;↵
if (r == 0 && c == 0) {↵
best_prev = 0;↵
} else {↵
if (r > 0 && idx_top > 0) {↵
best_prev = min(best_prev, prev_pref[c][idx_top — 1]);↵
}↵
if (c > 0 && idx_left > 0) {↵
best_prev = min(best_prev, curr_pref[c — 1][idx_left — 1]);↵
}↵
}↵
↵
if (best_prev != INF) {↵
running_min = min(running_min, best_prev + (1000000LL — f));↵
}↵
curr_pref[c][i] = running_min;↵
}↵
}↵
↵
for (int c = 0; c < m; c++) {↵
prev_grid[c] = curr_grid[c];↵
for (int i = 0; i < k; i++) {↵
prev_pref[c][i] = curr_pref[c][i];↵
}↵
}↵
}↵
↵
long long ans = prev_pref[m — 1][k — 1];↵
if (ans >= INF) {↵
cout << "DOOMED\n";↵
} else {↵
cout << ans << "\n";↵
}↵
↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
<spoiler summary="Problem G: Doom's Palindromic Matrix">↵
↵
<p><b>Problem Summary & Key Intuition:</b></p>↵
<ul>↵
<li><b>Summary:</b> Calculate range sums of distinct palindromic subsequence counts f_x(i) over Pascal matrix rows i in [L, R] truncated at column x modulo 998244353.</li>↵
<li><b>Key Intuition:</b> The structural behavior of row i splits i into three main mathematical regions relative to limit x:↵
<ol>↵
<li><b>Region 1 (i <= x):</b> Full symmetric row, geometric sums of powers of 2 based on even/odd parity.</li>↵
<li><b>Region 2 (x < i <= 2x+1):</b> Partially folded row, capped symmetric pair counts.</li>↵
<li><b>Region 3 (i >= 2x+2):</b> Strictly increasing window, constant x + 1 distinct elements per row.</li>↵
</ol>↵
</li>↵
</ul>↵
↵
<p><b>Detailed Explanation & Complexity:</b></p>↵
<ul>↵
<li><b>Detailed Explanation:</b> Evaluate contributions from each region using logarithmic power function power_two and range exponent sum formula sum_pow.</li>↵
<li><b>Time Complexity:</b> O(Q log MOD) time.</li>↵
<li><b>Space Complexity:</b> O(1) space.</li>↵
</ul>↵
↵
<p><b>C++ Implementation:</b></p>↵
↵
<pre class="prettyprint lang-cpp">↵
#include <iostream>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
const long long MOD = 998244353;↵
↵
long long power_two(long long exp) {↵
long long res = 1;↵
long long base = 2;↵
while (exp > 0) {↵
if (exp % 2 == 1) res = (res * base) % MOD;↵
base = (base * base) % MOD;↵
exp /= 2;↵
}↵
return res;↵
}↵
↵
long long sum_pow(long long low, long long high) {↵
if (low > high) return 0;↵
long long val_high = power_two(high + 1);↵
long long val_low = power_two(low);↵
return (val_high — val_low + MOD) % MOD;↵
}↵
↵
void solve_query() {↵
long long l, r, x;↵
if (!(cin >> l >> r >> x)) return;↵
↵
long long total = 0;↵
↵
long long r1_start = l, r1_end = min(r, x);↵
if (r1_start <= r1_end) {↵
long long res = 0;↵
↵
long long even_start = (r1_start % 2 == 0) ? r1_start : r1_start + 1;↵
long long even_end = (r1_end % 2 == 0) ? r1_end : r1_end — 1;↵
if (even_start <= even_end) {↵
long long count = (even_end — even_start) / 2 + 1;↵
long long sp = sum_pow(even_start / 2, even_end / 2);↵
res = (res + 3 * sp % MOD * (count % MOD)) % MOD;↵
}↵
↵
long long odd_start = (r1_start % 2 != 0) ? r1_start : r1_start + 1;↵
long long odd_end = (r1_end % 2 != 0) ? r1_end : r1_end — 1;↵
if (odd_start <= odd_end) {↵
long long count = (odd_end — odd_start) / 2 + 1;↵
long long sp = sum_pow((odd_start + 1) / 2, (odd_end + 1) / 2);↵
res = (res + 2 * sp % MOD * (count % MOD)) % MOD;↵
}↵
↵
total = (total + res) % MOD;↵
}↵
↵
long long r2_start = max(l, x + 1), r2_end = min(r, 2 * x + 1);↵
if (r2_start <= r2_end) {↵
long long res = 0;↵
↵
long long even_start = (r2_start % 2 == 0) ? r2_start : r2_start + 1;↵
long long even_end = (r2_end % 2 == 0) ? r2_end : r2_end — 1;↵
if (even_start <= even_end) {↵
long long sp = sum_pow(x — even_end / 2, x — even_start / 2);↵
res = (res + 3 * sp) % MOD;↵
}↵
↵
long long odd_start = (r2_start % 2 != 0) ? r2_start : r2_start + 1;↵
long long odd_end = (r2_end % 2 != 0) ? r2_end : r2_end — 1;↵
if (odd_start <= odd_end) {↵
long long sp = sum_pow(x — (odd_end + 1) / 2, x — (odd_start + 1) / 2);↵
res = (res + 2 * sp) % MOD;↵
}↵
↵
total = (total + res) % MOD;↵
}↵
↵
long long r3_start = max(l, 2 * x + 2), r3_end = r;↵
if (r3_start <= r3_end) {↵
long long count = r3_end — r3_start + 1;↵
total = (total + (x + 1) % MOD * (count % MOD)) % MOD;↵
}↵
↵
cout << total << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int q;↵
if (cin >> q) {↵
while (q--) {↵
solve_query();↵
}↵
}↵
return 0;↵
}↵
</pre>↵
↵
</spoiler>↵
↵
