Thanks for the participation in our second ever contest, and the first ever fully public contest STEM Avengers: Age of Algorithms. We at Team A² 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:
If you're wondering why this editorial took 3 months...
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.
642756A — Tony Stark's Missing Core
Problem Credit: Abdur-Rehman
Let
If the missing suit has power
then the reported average
satisfies
Since
is given rounded to at most three decimals, write
with integer
(thousandths). Then
Therefore an integer solution exists exactly when
and the resulting
satisfies
If both conditions hold output that
, otherwise output
The code will be added shortly after the manual testing ends.
Problem Credit: Abdur-Rehman
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.
The code will be added shortly after the manual testing ends.
642756C — Ant-Man and the Swap
Problem Credit: Abdur-Rehman
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 \gt 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.
The code will be added shortly after the manual testing ends.
642756D — Fragments of Civilization
Problem Credit: M_AsadHussain
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.
The code will be added shortly after the manual testing ends.
642756E — Reconnecting the Civilization
Problem Credit: M_AsadHussain
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 \gt 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.
The code will be added shortly after the manual testing ends.
642756F — Stabilizing the Overloaded Stones
Problem Credit: M_AsadHussain
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.
The code will be added shortly after the manual testing ends.
642756G — Resonance of Corrupted Circuits
Problem Credit: JonKhan; Special Thanks: M_AsadHussain
Compute SCCs (Kosaraju/Tarjan); for each SCC $$$S$$$ with $$$|S| \gt 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.
The code will be added shortly after the manual testing ends.
