Thanks for the participation in our second ever contest, and the first ever fully public contest [contest:642756]. We at [Team A²](https://sites.google.com/view/team-a-squared/home?authuser=0) hope you enjoyed the contest. Due to the solutions and tutorials being from different people the solutions may differ from the shown implementation (we will fix this soon).↵
↵
We'd also like to congratulate the winners of the round:↵
↵
- [user:PaPaPiZzA,2026-01-11]↵
↵
- [user:Grotok,2026-01-11]↵
↵
- [user:Ahmed-Nawaz,2026-01-11]↵
↵
If you're wondering why this editorial took 3 months...↵
↵
<spoiler summary="Here's why">↵
One of the authors had taken responsibility to write and upload the editorial, but we were misled and that person never did so, so finally after 3 months I decided to do it myself.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Rate the Contest!">↵
- [likes:1,Epic] Epic↵
- [likes:1,Good] Good↵
- [likes:1,Moderate] Moderate↵
- [likes:1,Bad] Bad↵
- [likes:1,Horrendous] Horrendous↵
</spoiler>↵
↵
The solution codes will be added shortly after the manual testing ends.↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/A" title="STEM Avengers: Age of Algorithm">642756A — Tony Stark's Missing Core</a>↵
↵
Problem Credit: [user:M.AbdurRehman,2025-12-11]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:2,Epic] Epic↵
- [likes:2,Good] Good↵
- [likes:2,Moderate] Moderate↵
- [likes:2,Bad] Bad↵
- [likes:2,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let $$S=\sum_{i=1}^n i=\frac{n(n+1)}{2}.$$↵
If the missing suit has power $$x$$ then the reported average $$k$$ satisfies ↵
$$k=\frac{S-x}{n-1}\quad\Longrightarrow\quad x=S-k(n-1).$$↵
Since $$k$$ is given rounded to at most three decimals, write $$k=\frac{K}{1000}$$ with integer $$K$$ (thousandths). Then ↵
$$x=\frac{1000S-K(n-1)}{1000}.$$↵
Therefore an integer solution exists exactly when ↵
$$1000S-K(n-1)\equiv 0\pmod{1000},$$↵
and the resulting $$x=\dfrac{1000S-K(n-1)}{1000}$$ satisfies ↵
$$1\le x\le n.$$↵
If both conditions hold output that $$x$$, otherwise output $$-1.$$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/B" title="STEM Avengers: Age of Algorithm">642756B — Rise and Fall</a>↵
↵
Problem Credit: [user:Abdur-Rehman,2025-12-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:3,Epic] Epic↵
- [likes:3,Good] Good↵
- [likes:3,Moderate] Moderate↵
- [likes:3,Bad] Bad↵
- [likes:3,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Tony observes an array of energies $a_1, a_2, \ldots, a_n$. Let the prefix sums be defined as $p_i = a_1 + a_2 + \cdots + a_i$. The difference between consecutive prefix sums gives the rate of rise, so $\text{rate}_i = p_{i+1} - p_i = a_{i+1}$. A rising–fall segment is a maximal subarray $[l,r]$ such that the sequence of energies first strictly increases and then strictly decreases. To find the segment with the greatest total energy, one can iterate through the array while identifying each maximal increasing–then–decreasing region. For each such region $[s, e]$, its total energy is $p_{e+1} - p_s$. Maintain two variables: the maximum sum $m$ and its count $c$. Whenever a segment’s sum exceeds $m$, update $m = \text{sum}$ and reset $c = 1$; if it equals $m$, increment $c$. After processing all segments, output the pair $(m, c)$. The algorithm runs in linear time $\mathcal{O}(n)$ per test case since each index is visited at most twice. Thus, for each test, we efficiently find the maximum height of any rise–fall sequence and how many segments achieve it.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/C" title="STEM Avengers: Age of Algorithm">642756C — Ant-Man and the Swap</a>↵
↵
Problem Credit: [user:Abdur-Rehman,2025-12-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:4,Epic] Epic↵
- [likes:4,Good] Good↵
- [likes:4,Moderate] Moderate↵
- [likes:4,Bad] Bad↵
- [likes:4,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Compute $S=\sum_{i=1}^n i=\frac{n(n+1)}{2}$. Flipping a chosen set $F$ of signs changes the total from $S$ to $S-2\sum_{f\in F}f$, so a necessary and sufficient condition for a set $F$ to produce $T$ is $\sum_{f\in F}=X=\frac{S-T}{2}$; if $S-T$ is negative or odd there are $0$ ways. Thus the problem reduces to counting $k$-element subsets of $\{0,1,\dots,n\}$ whose elements sum to $X$. Use dynamic programming: let $dp[i][j][s]$ be the number of ways (mod $10^9+7$) to choose $j$ elements from $\{1,\dots,i\}$ with sum $s$, with base $dp[0][0][0]=1$, and transition $dp[i][j][s]=dp[i-1][j][s]+(s\ge i?\;dp[i-1][j-1][s-i]:\;0)$. After filling the DP for $i=1\ldots n$ the count of $k$-element subsets of $\{0,\dots,n\}$ summing to $X$ equals $dp[n][k][X]+(k>0?\;dp[n][k-1][X]:\;0)$ (the second term accounts for choosing $0$ as one of the $k$ elements). Return this value modulo $10^9+7$. The preprocessing requires $O(nkX)$ time and $O(kX)$ (or $O(nkX)$) memory where $X\le S\le n(n+1)/2\le 5050$ for $n\le100$, so the solution is efficient under the given constraints.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/D" title="STEM Avengers: Age of Algorithm">642756D — Fragments of Civilization</a>↵
↵
Problem Credit: [user:1uxmere,2025-10-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:5,Epic] Epic↵
- [likes:5,Good] Good↵
- [likes:5,Moderate] Moderate↵
- [likes:5,Bad] Bad↵
- [likes:5,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let $G$ be the graph with $n$ vertices and $m$ edges given by adjacency lists, and maintain a boolean array $\text{vis}[1\ldots n]$ initialized to $\text{false}$. For each vertex $i=1,\dots,n$, if $\text{vis}[i]$ is false start a DFS (or BFS) from $i$, mark every reached vertex as visited and count them; this count is the size of one settlement. Push each size into a vector $S$, sort $S$ in non-decreasing order, then output $|S|$ and the elements of $S$. The traversal visits every vertex and edge at most once, so the running time is $\mathcal{O}(n+m)$ and the extra memory is $\mathcal{O}(n+m)$ for adjacency lists (or $\mathcal{O}(n)$ additional auxiliary memory); prefer an iterative DFS if recursion depth is a concern.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/E" title="STEM Avengers: Age of Algorithm">642756E — Reconnecting the Civilization</a>↵
↵
Problem Credit: [user:1uxmere,2025-10-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:6,Epic] Epic↵
- [likes:6,Good] Good↵
- [likes:6,Moderate] Moderate↵
- [likes:6,Bad] Bad↵
- [likes:6,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let $G$ be the graph with vertex set of settlements and edges $(u,v,d)$ representing roads of length $d$, and let $w$ denote the available miles of wire. Sort all edges by nondecreasing weight and run Kruskal’s algorithm with a Disjoint Set Union: process edges in that order and accept an edge exactly when it joins two different components. Maintain a running sum $S$ of accepted edge weights and a counter $e$ of accepted edges. If after Kruskal the graph becomes connected, the accepted edges form a minimum spanning tree and $S$ is the minimum miles required to reconnect all settlements; if $S\le w$ then the answer is ``YES`` and the minimum required miles $S$. If $S>w$, then to maximize the number of merges achievable within the budget one should greedily accept the cheapest edges while keeping the running sum $\le w$; the number of accepted merges under the budget is $e'$, and the number of remaining disconnected settlements equals $n-e'$, so the answer is ``NO`` and $n-e'$. Kruskal is optimal here because it always picks the cheapest edges that merge components, hence it minimizes the total cost to connect the graph and — for any fixed budget — it also maximizes the number of merges achievable with that budget. The procedure runs in $O(m\log m)$ time for sorting plus near $O(m\alpha(n))$ for DSU operations, and uses $O(n+m)$ memory for the edge list and DSU.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/F" title="STEM Avengers: Age of Algorithm">642756F — Stabilizing the Overloaded Stones</a>↵
↵
Problem Credit: [user:1uxmere,2025-10-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:7,Epic] Epic↵
- [likes:7,Good] Good↵
- [likes:7,Moderate] Moderate↵
- [likes:7,Bad] Bad↵
- [likes:7,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Each operation changes a stone's energy by exactly $\pm k$, so starting from $S_i$ the set of reachable values is $S_i + k\mathbb{Z}$. Hence the $i$-th stone can be made equal to $T_i$ if and only if $T_i\equiv S_i\pmod{k}$. Therefore, for each $i$ output `1` when $S_i\equiv T_i\pmod{k}$ and `0` otherwise; this check is $O(1)$ per stone and the whole solution runs in $O(n)$ time per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/G" title="STEM Avengers: Age of Algorithm">642756G — Resonance of Corrupted Circuits</a>↵
↵
Problem Credit: [user:JonKhan,2025-12-13]; Special Thanks: [user:1uxmere,2025-10-14]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:8,Epic] Epic↵
- [likes:8,Good] Good↵
- [likes:8,Moderate] Moderate↵
- [likes:8,Bad] Bad↵
- [likes:8,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Compute SCCs (Kosaraju/Tarjan); for each SCC $S$ with $|S|>1$ or containing a self-loop compute $g=\gcd_{v\in S}w_v$; sieve primes up to $10^6$ and insert $g$ into a set $D$ if $g$ is prime; answer each query $x$ with YES iff $x\in D$. The algorithm runs in $O(n+m)$ per test case with $O(n+m)$ memory.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
↵
We'd also like to congratulate the winners of the round:↵
↵
- [user:PaPaPiZzA,2026-01-11]↵
↵
- [user:Grotok,2026-01-11]↵
↵
- [user:Ahmed-Nawaz,2026-01-11]↵
↵
If you're wondering why this editorial took 3 months...↵
↵
<spoiler summary="Here's why">↵
One of the authors had taken responsibility to write and upload the editorial, but we were misled and that person never did so, so finally after 3 months I decided to do it myself.↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Rate the Contest!">↵
- [likes:1,Epic] Epic↵
- [likes:1,Good] Good↵
- [likes:1,Moderate] Moderate↵
- [likes:1,Bad] Bad↵
- [likes:1,Horrendous] Horrendous↵
</spoiler>↵
↵
The solution codes will be added shortly after the manual testing ends.↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/A" title="STEM Avengers: Age of Algorithm">642756A — Tony Stark's Missing Core</a>↵
↵
Problem Credit: [user:M.AbdurRehman,2025-12-11]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:2,Epic] Epic↵
- [likes:2,Good] Good↵
- [likes:2,Moderate] Moderate↵
- [likes:2,Bad] Bad↵
- [likes:2,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let $$S=\sum_{i=1}^n i=\frac{n(n+1)}{2}.$$↵
If the missing suit has power $$x$$ then the reported average $$k$$ satisfies ↵
$$k=\frac{S-x}{n-1}\quad\Longrightarrow\quad x=S-k(n-1).$$↵
Since $$k$$ is given rounded to at most three decimals, write $$k=\frac{K}{1000}$$ with integer $$K$$ (thousandths). Then ↵
$$x=\frac{1000S-K(n-1)}{1000}.$$↵
Therefore an integer solution exists exactly when ↵
$$1000S-K(n-1)\equiv 0\pmod{1000},$$↵
and the resulting $$x=\dfrac{1000S-K(n-1)}{1000}$$ satisfies ↵
$$1\le x\le n.$$↵
If both conditions hold output that $$x$$, otherwise output $$-1.$$↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/B" title="STEM Avengers: Age of Algorithm">642756B — Rise and Fall</a>↵
↵
Problem Credit: [user:Abdur-Rehman,2025-12-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:3,Epic] Epic↵
- [likes:3,Good] Good↵
- [likes:3,Moderate] Moderate↵
- [likes:3,Bad] Bad↵
- [likes:3,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Tony observes an array of energies $a_1, a_2, \ldots, a_n$. Let the prefix sums be defined as $p_i = a_1 + a_2 + \cdots + a_i$. The difference between consecutive prefix sums gives the rate of rise, so $\text{rate}_i = p_{i+1} - p_i = a_{i+1}$. A rising–fall segment is a maximal subarray $[l,r]$ such that the sequence of energies first strictly increases and then strictly decreases. To find the segment with the greatest total energy, one can iterate through the array while identifying each maximal increasing–then–decreasing region. For each such region $[s, e]$, its total energy is $p_{e+1} - p_s$. Maintain two variables: the maximum sum $m$ and its count $c$. Whenever a segment’s sum exceeds $m$, update $m = \text{sum}$ and reset $c = 1$; if it equals $m$, increment $c$. After processing all segments, output the pair $(m, c)$. The algorithm runs in linear time $\mathcal{O}(n)$ per test case since each index is visited at most twice. Thus, for each test, we efficiently find the maximum height of any rise–fall sequence and how many segments achieve it.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/C" title="STEM Avengers: Age of Algorithm">642756C — Ant-Man and the Swap</a>↵
↵
Problem Credit: [user:Abdur-Rehman,2025-12-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:4,Epic] Epic↵
- [likes:4,Good] Good↵
- [likes:4,Moderate] Moderate↵
- [likes:4,Bad] Bad↵
- [likes:4,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Compute $S=\sum_{i=1}^n i=\frac{n(n+1)}{2}$. Flipping a chosen set $F$ of signs changes the total from $S$ to $S-2\sum_{f\in F}f$, so a necessary and sufficient condition for a set $F$ to produce $T$ is $\sum_{f\in F}=X=\frac{S-T}{2}$; if $S-T$ is negative or odd there are $0$ ways. Thus the problem reduces to counting $k$-element subsets of $\{0,1,\dots,n\}$ whose elements sum to $X$. Use dynamic programming: let $dp[i][j][s]$ be the number of ways (mod $10^9+7$) to choose $j$ elements from $\{1,\dots,i\}$ with sum $s$, with base $dp[0][0][0]=1$, and transition $dp[i][j][s]=dp[i-1][j][s]+(s\ge i?\;dp[i-1][j-1][s-i]:\;0)$. After filling the DP for $i=1\ldots n$ the count of $k$-element subsets of $\{0,\dots,n\}$ summing to $X$ equals $dp[n][k][X]+(k>0?\;dp[n][k-1][X]:\;0)$ (the second term accounts for choosing $0$ as one of the $k$ elements). Return this value modulo $10^9+7$. The preprocessing requires $O(nkX)$ time and $O(kX)$ (or $O(nkX)$) memory where $X\le S\le n(n+1)/2\le 5050$ for $n\le100$, so the solution is efficient under the given constraints.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/D" title="STEM Avengers: Age of Algorithm">642756D — Fragments of Civilization</a>↵
↵
Problem Credit: [user:1uxmere,2025-10-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:5,Epic] Epic↵
- [likes:5,Good] Good↵
- [likes:5,Moderate] Moderate↵
- [likes:5,Bad] Bad↵
- [likes:5,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let $G$ be the graph with $n$ vertices and $m$ edges given by adjacency lists, and maintain a boolean array $\text{vis}[1\ldots n]$ initialized to $\text{false}$. For each vertex $i=1,\dots,n$, if $\text{vis}[i]$ is false start a DFS (or BFS) from $i$, mark every reached vertex as visited and count them; this count is the size of one settlement. Push each size into a vector $S$, sort $S$ in non-decreasing order, then output $|S|$ and the elements of $S$. The traversal visits every vertex and edge at most once, so the running time is $\mathcal{O}(n+m)$ and the extra memory is $\mathcal{O}(n+m)$ for adjacency lists (or $\mathcal{O}(n)$ additional auxiliary memory); prefer an iterative DFS if recursion depth is a concern.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/E" title="STEM Avengers: Age of Algorithm">642756E — Reconnecting the Civilization</a>↵
↵
Problem Credit: [user:1uxmere,2025-10-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:6,Epic] Epic↵
- [likes:6,Good] Good↵
- [likes:6,Moderate] Moderate↵
- [likes:6,Bad] Bad↵
- [likes:6,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let $G$ be the graph with vertex set of settlements and edges $(u,v,d)$ representing roads of length $d$, and let $w$ denote the available miles of wire. Sort all edges by nondecreasing weight and run Kruskal’s algorithm with a Disjoint Set Union: process edges in that order and accept an edge exactly when it joins two different components. Maintain a running sum $S$ of accepted edge weights and a counter $e$ of accepted edges. If after Kruskal the graph becomes connected, the accepted edges form a minimum spanning tree and $S$ is the minimum miles required to reconnect all settlements; if $S\le w$ then the answer is ``YES`` and the minimum required miles $S$. If $S>w$, then to maximize the number of merges achievable within the budget one should greedily accept the cheapest edges while keeping the running sum $\le w$; the number of accepted merges under the budget is $e'$, and the number of remaining disconnected settlements equals $n-e'$, so the answer is ``NO`` and $n-e'$. Kruskal is optimal here because it always picks the cheapest edges that merge components, hence it minimizes the total cost to connect the graph and — for any fixed budget — it also maximizes the number of merges achievable with that budget. The procedure runs in $O(m\log m)$ time for sorting plus near $O(m\alpha(n))$ for DSU operations, and uses $O(n+m)$ memory for the edge list and DSU.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/F" title="STEM Avengers: Age of Algorithm">642756F — Stabilizing the Overloaded Stones</a>↵
↵
Problem Credit: [user:1uxmere,2025-10-13]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:7,Epic] Epic↵
- [likes:7,Good] Good↵
- [likes:7,Moderate] Moderate↵
- [likes:7,Bad] Bad↵
- [likes:7,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Each operation changes a stone's energy by exactly $\pm k$, so starting from $S_i$ the set of reachable values is $S_i + k\mathbb{Z}$. Hence the $i$-th stone can be made equal to $T_i$ if and only if $T_i\equiv S_i\pmod{k}$. Therefore, for each $i$ output `1` when $S_i\equiv T_i\pmod{k}$ and `0` otherwise; this check is $O(1)$ per stone and the whole solution runs in $O(n)$ time per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
<a href="https://mirror.codeforces.com/gym/642756/problem/G" title="STEM Avengers: Age of Algorithm">642756G — Resonance of Corrupted Circuits</a>↵
↵
Problem Credit: [user:JonKhan,2025-12-13]; Special Thanks: [user:1uxmere,2025-10-14]↵
↵
<spoiler summary="Rate the Problem!">↵
- [likes:8,Epic] Epic↵
- [likes:8,Good] Good↵
- [likes:8,Moderate] Moderate↵
- [likes:8,Bad] Bad↵
- [likes:8,Horrendous] Horrendous↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Compute SCCs (Kosaraju/Tarjan); for each SCC $S$ with $|S|>1$ or containing a self-loop compute $g=\gcd_{v\in S}w_v$; sieve primes up to $10^6$ and insert $g$ into a set $D$ if $g$ is prime; answer each query $x$ with YES iff $x\in D$. The algorithm runs in $O(n+m)$ per test case with $O(n+m)$ memory.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
The code will be added shortly after the manual testing ends.↵
</spoiler>↵
↵
