W03L02 — CS 334 — Spring 2025

#	User	Rating
1	jiangly	4039
2	tourist	3841
3	jqdai0815	3682
4	ksun48	3590
5	ecnerwala	3542
6	Benq	3535
7	orzdevinwang	3526
8	gamegame	3477
9	heuristica	3357
10	Radewoosh	3355

#	User	Contrib.
1	cry	167
2	-is-this-fft-	165
3	atcoder_official	160
3	Um_nik	160
5	djm03178	158
6	Dominater069	156
7	adamant	153
8	luogu_official	151
8	awoo	151
10	TheScrasse	146

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$$$.