Editorial for W03L02 - CS 334 - Spring 2025

582923A - Eating Queries

To minimize the number of candies, Timur will favor candies with higher sugar content. We can sort $$$a$$$ in reverse and compute its prefix sum array, $$$b$$$. Note that $$$b$$$ is increasing. $$$b_i$$$ represents the maximum amount of sugar that Timur can get after eating $$$i$$$ candies, and $$$b_n$$$ represents the total amount of sugar that Timur can get from eating all the candies.

If $$$x_j> b_n$$$, then the answer is $$$-1$$$. Otherwise, the answer is the smallest $$$i$$$ such that $$$b_i \ge x_j$$$. This can be found easily through a binary search on $$$b$$$.

The main steps and their complexity are:

• $$$O(n\log n)$$$ to sort $$$a$$$ in reverse
• $$$\Theta(n)$$$ to compute $$$b$$$, the prefix sum array of $$$a$$$
• $$$O(q\log n)$$$ for $$$q$$$ binary searches over $$$b$$$

The overall complexity is therefore $$$O(\max(n\log n, q\log n))$$$.

Original problem: 1676E - Eating Queries, leads to official tutorial and all solutions including WS solution: 302470603

582923B - The Strict Teacher (Hard Version)

We note that only the positions of the teachers that immediately surround David are relevant. These can be found easily by sorting $$$b$$$ and performing a binary search in $$$b$$$ for a given $$$a_i$$$.

If there is no teacher on one side of David, then David can move as far as possible in that direction and make no further moves when he reaches the end. Depending on the side, the number of moves to be made by the teacher is $$$b_1-1$$$ or $$$n-b_m$$$.

When there are teachers on both sides, let $$$l$$$ and $$$r$$$ be the number of empty cells between David and the teachers on each side, and let $$$l$$$ be the smaller distance. One optimal strategy is for David to stay still for $$$l$$$ moves and then start moving. By this time one teacher is just adjacent to David and the other is $$$r-l$$$ cells away. David runs from the teacher just next to him, and thus moves closer to the other teacher, who ends up catching David in an additional $$$(r-l)//2$$$ moves. The answer is $$$l + (r - l)//2$$$.

The main steps and their complexity are:

• $$$O(n\log n)$$$ to sort $$$a$$$
• $$$O(q\log n)$$$ for $$$q$$$ binary searches over $$$b$$$

The overall complexity is therefore $$$O(\max(n\log n, q\log n))$$$.

Original problem: 2005B2 - The Strict Teacher (Hard Version), leads to official tutorial and all solutions including WS solution: 302489261