Thank you for participating in our round! We hope you enjoyed the problems.
2257A - Creating Abbreviations Idea: egorka5opka
Note that adding abbreviations to the set $$$S$$$ does not create any new possibilities for creating new abbreviations, because a word starting with that letter already exists. Therefore, for each of the 26 letters, we can remember that there is a word that begins with it, and then go through all the abbreviations and check each letter.
2257B - Gigantomachy Idea: egorka5opka
On each turn, the height at which the giant stands decreases by exactly $$$1$$$, except in cases where he changes mountains.
Thus, the first giant will lose after $$$((a_1 - a_2) + 1) + ((a_2 - a_3) + 1) + \dots + ((a_{n - 1} - a_n) + 1) + a_n = a_1 + n - 1$$$ moves.
Similarly, the second giant will lose after $$$b_1 + m - 1$$$ moves. All left is only to compare these two numbers.
Time complexity: $$$\mathcal{O}(n)$$$.
2257C - Spying on the Beaver Idea: egorka5opka
Suppose we have placed some cameras and remove the corresponding edges from the tree. If all the dams are now in different connected components, we can always uniquely determine where the Beaver went. Conversely, if there is a component containing two dams, we cannot distinguish between them.
Since the original graph is a tree, it is necessary and sufficient to remove $$$m-1$$$ edges.
If the root contains a dam, we can take the edges leading directly to all the other dams, obtaining a set of size $$$m-1$$$.
If the root does not contain a dam, we take the same edges but skip one of them. It is important that we cannot skip just any edge: we must choose a dam such that there are no other dams on the path from the root to it. We can take the dam with the smallest depth or vertex number. In this case, we do not even need to run a DFS.
Time complexity: $$$\mathcal{O}(n+m)$$$.
2257D - Bermuda Rectangle Idea: pskobx, oblememan, egorka5opka
Before processing the queries, let us perform some preprocessing. Find all pairs $$$(a, b)$$$ such that $$$a \cdot b = S$$$. There are $$$\mathcal{O}(\sqrt{S})$$$ such pairs, and they can also be found in $$$\mathcal{O}(\sqrt{S})$$$ time with standard algorithms.
These pairs are the top-right corners of all possible Bermuda rectangles. The union of these rectangles forms a staircase-like shape; let us call it $$$F$$$. The answer to a query is the area of the intersection of the query rectangle with $$$F$$$.
Sort the points by $$$x$$$, and for the point with index $$$i$$$, compute the value $$$P_i$$$, equal to the area of $$$F$$$ between $$$0$$$ and this $$$x_i$$$.
This information is enough to answer each query efficiently using binary search. We find the position where the boundary of $$$F$$$ crosses the horizontal side of the query rectangle and calculate the answer using the corresponding prefix areas. The exact formulas and case analysis may vary depending on the implementation.
A couple of remarks that may make implementation easier. If there is a point $$$(x, y)$$$, then there is also $$$(y, x)$$$, and since, knowing one coordinate, it is easy to compute the other. Therefore, it is enough to store just the sorted list of divisors of $$$S$$$ and treat them both as $$$x$$$ and as $$$y$$$.
Preprocessing complexity: $$$\mathcal{O}(\sqrt{S})$$$, time complexity per query: $$$\mathcal{O}(\log S)$$$.
2257E - Busy Beaver Idea: pskobx
The first step is to earn as many carrots as possible to maximize our capital. Divide the floors of each building into the shortest consecutive segments whose total profit is non-negative, and calculate the entry threshold of each such segment. The entry threshold is the minimum amount of capital required to construct all floors of the segment in order.
For example, consider two floors with $$$(a_1, a_2) = (10, 0)$$$ and $$$(b_1, b_2) = (0, 100)$$$. Constructing only the first floor is unprofitable, but constructing both floors yields a profit of $$$90$$$ carrots. However, an initial capital of at least $$$10$$$ carrots is required.
In an ordered set, we keep the next available segment for each building, sorted by its entry threshold. While the segment with the minimum threshold is affordable, we construct the entire segment, add its profit to our capital, and insert the next segment of the same building into the set. If the segment with the minimum threshold is not affordable, then none of the available segments can be constructed, meaning that we have maximized our capital.
In the second step, we independently try to continue constructing each building from its current height, floor by floor, for as long as the current capital allows. Among all buildings, we choose the maximum resulting height and, in case of a tie, the smallest index.
Time complexity: $$$\mathcal{O}\left(\sum m_i \log n\right)$$$.
2257F1 - Beaver's Jumping Track (Easy Version) Idea: pskobx, oblememan, egorka5opka
Since $$$x$$$ is small, we build a segment tree whose vertices store matrices of size $$$x \times x$$$.
For an interval of platforms, let $$$c[i][j]$$$ be the minimum penalty if the Beaver starts $$$i$$$ cells after the beginning of the interval and first lands $$$j$$$ cells after its end. Invalid starting positions are ignored.
For a single platform of length $$$d$$$ and penalty $$$s$$$,
where $$$0\le i \lt \min(d,x)$$$ and $$$0\le j \lt x$$$. The last jump leaves the platform and causes no penalty, while all previous jumps stay inside it.
To merge two consecutive intervals $$$A$$$ and $$$B$$$, enumerate the first landing position $$$k$$$ in $$$B$$$:
If $$$A$$$ contains fewer than $$$x$$$ cells, the Beaver may start directly inside $$$B$$$; in this case, we copy the corresponding values from $$$c_B$$$.
For a query $$$[l,r]$$$, obtain the matrix for $$$[l,r-1]$$$ and enumerate the first landing position $$$i$$$ on platform $$$r$$$. The answer is
The case $$$l=r$$$ is calculated directly.
Each update and query takes $$$\mathcal{O}(x^3\log n)$$$ time. Memory complexity is $$$\mathcal{O}(nx^2)$$$. Build is $$$\mathcal{O}(nx^3)$$$.
2257F2 - Beaver's Jumping Track (Hard Version)
Surprisingly, the main problem with the solution from F1 is memory, not time. A segment tree stores $$$\mathcal{O}(n)$$$ matrices, each containing $$$x^2$$$ values. For $$$x=10$$$, this does not fit into the memory limit.
To reduce memory usage, divide the platforms into blocks of size $$$B$$$ (for example, $$$B=16$$$). For each block, calculate the matrix of the entire block using the same merging formula as in F1. Then build a segment tree only over these block matrices.
For a query, at most two blocks are only partially covered by the required range. Process the platforms in these blocks separately, and use the segment tree to combine all blocks that are fully covered. After an update, recalculate the matrix of the affected block and update it in the segment tree.
For a block size $$$B$$$, the memory complexity is $$$\mathcal{O}\left(n+\frac{n}{B}x^2\right)$$$.
Each query takes $$$\mathcal{O}\left(Bx^2+x^3\log\frac{n}{B}\right)$$$.
Аnd each update takes $$$\mathcal{O}\left(Bx^3+x^3\log\frac{n}{B}\right)$$$.
