Editorial for W03L01 - CS 334 - Spring 2025.

582534A - Building an Aquarium

For a given $$$h$$$, we can compute $$$w$$$ as $$$w(h)=\sum_{i=1}^n \max(h-a_i, 0)$$$. For the following, assume that $$$a$$$ is sorted.

For any $$$h<a_1$$$, $$$w(h)=0$$$. With the given bounds, $$$1\le n\le 2\cdot 10^5, 1\le x\le 10^9, 1\le a_i\le 10^9$$$, the maximum $$$h$$$ is $$$2\cdot 10^9$$$.

Now that we have the lower and upper bounds for $$$h$$$, and noticing that $$$w(h)$$$ is non-decreasing, we can do a binary search over the range of values of $$$h$$$ to find the value at which $$$w(h)$$$ just exceeds $$$x$$$. The answer is then one less than that value.

If $$$H$$$ is the size of the range of possible values of $$$h$$$, then the complexity of this solution is $$$O(\log H)$$$, determined by the binary search.

Original problem: 1873E - Building an Aquarium, leads to official tutorial and all solutions including WS solution: 276080524

582534B - Scuza

After climbing the $$$i$$$-th step, the height that is reached is $$$h_i = a_1+a+2+\ldots+a_i$$$. In order to climb the $$$i$$$-th step, the shortest required leg length is $$$m_i = \max(a_1,a+2,\ldots,a_i)$$$.

Given the array, $$$a$$$, we can compute the arrays $$$h$$$ and $$$m$$$ as above, each in $$$O(n)$$$ time. Note that $$$h$$$ and $$$m$$$ are non-decreasing. Given a leg length, $$$k$$$, we find the maximum leg length in $$$m$$$ that is equal to or less than $$$k$$$. That is, $$$i=\max_j m_j\le k$$$. This can be found in $$$O(\log n)$$$ time using binary search. If no such $$$i$$$ exists, i.e. $$$k < m_1$$$, then the answer is 0, otherwise the reached height is $$$h_i$$$.

The complexity of this solution is $$$O(n + q\log n)$$$ determined by the computation of $$$h$$$ and $$$m$$$, and by the binary search for each of the $$$q$$$ queries.

Original problem: 1742E - Scuza, leads to official tutorial and all solutions including WS solution: 269560517

582534C - Counting Pairs

Let's sort $$$a$$$ and let $$$s$$$ be its sum. Then we have that $$$ x \le s - a_i - a_j \le y$$$ and $$$s-y \le a_i + a_j \le s-x$$$. Note that $$$i$$$ and $$$j$$$ are distinct. For any $$$i$$$, we have to find all values of $$$j$$$ such that $$$s-y-a_i \le a_j \le s-x-a_i$$$. As $$$a$$$ is sorted, this can be done with 2 binary searches.

In order to avoid double counting, the search should only be performed on $$$a_{i+1}, a_{i+2},\ldots,a_n$$$.

The complexity of this solution is determined by

• the sorting of $$$a$$$ which takes $$$O(n\log n)$$$ time, and
• the binary searches for each $$$a_i$$$, which totals to $$$O(n\log n)$$$.

Altogether, the complexity is $$$O(n\log n)$$$.

Original problem: 2051D - Counting Pairs, leads to official tutorial and all solutions including WS solution: 302196583