Editorial for CCC '21 S3 - Lunch Concert - Olympiads Online Judge

Editorial for CCC '21 S3 - Lunch Concert

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

Observe that the only field positions that can be optimal are between the leftmost and rightmost positions of all friends, so we can simply check those positions.

Time Complexity: $\mathcal{O}(N \times \max(P_i))$ $O (N \times max (P_{i}))$

Subtask 2

We use the same observation as the last subtask except we must check positions more quickly, which we can do with linesweep.

Consider how the answer changes as we move from position $x$ $x$ to $x+1$ $x + 1$ : for every $i$ $i$ where $P_i+D_i \le x$ $P_{i} + D_{i} \leq x$ , we must add $W_i$ $W_{i}$ to the answer, and for every $j$ $j$ where $x < P_j-D_j$ $x < P_{j} - D_{j}$ , we must subtract $W_j$ $W_{j}$ from the answer. Thus, we simply need to maintain the sum of weights on the left and right of the current position.

Note: At any position $x$ $x$ , let $\text{leftSum}=\sum_{i=1,x \ge P_i+D_i}^N W_i$ $leftSum = \sum_{i = 1, x \geq P_{i} + D_{i}}^{N} W_{i}$ and $\text{rightSum}=\sum_{i=1,x < P_i-D_i}^N W_i$ $rightSum = \sum_{i = 1, x < P_{i} - D_{i}}^{N} W_{i}$ .

This solution can also be used to explain why field positions between the leftmost and rightmost positions of all friends are optimal: if we are to the left of the leftmost position of a friend, $\text{leftSum}=0$ $leftSum = 0$ while $\text{rightSum}>0$ $rightSum > 0$ , so moving to the right will always result in a better answer. A similar argument can be used to prove the same for positions to the right of the rightmost position of a friend.

Time Complexity: $\mathcal{O}(N + \max(P_i))$ $O (N + max (P_{i}))$

Subtask 3

The solution from subtask $2$ $2$ can be extended by realizing that an optimal answer will be at $P_i \pm D_i$ $P_{i} \pm D_{i}$ for some $1 \le i \le N$ $1 \leq i \leq N$ (we'll call these positions candidate positions). We can prove this by considering the $\text{leftSum}$ $leftSum$ and $\text{rightSum}$ $rightSum$ variables again: $\text{leftSum}$ $leftSum$ and $\text{rightSum}$ $rightSum$ only change at candidate positions, meaning that if we're between two candidate positions, we can always move left (if $\text{leftSum} \le \text{rightSum}$ $leftSum \leq rightSum$ ) or right (if $\text{leftSum} \ge \text{rightSum}$ $leftSum \geq rightSum$ ) until we reach a candidate position for a better answer.

Time Complexity: $\mathcal{O}(N \log N)$ $O (N \log N)$

Alternative Solution

Let $f_i(x)$ $f_{i} (x)$ be the walking time of the $i$ $i$ th friend if the concert was at position $x$ $x$ .

$\displaystyle f_i(x) = \begin{cases} W_i \times (P_i-D_i-x) & \text{if }x < P_i-D_i \\ 0 & \text{if } P_i-D_i \le x \le P_i+D_i \\ W_i \times (x-P_i-D_i) & \text{if }x > P_i+D_i \end{cases}$ $f_{i} (x) = {\begin{cases} W_{i} \times (P_{i} - D_{i} - x) & if x < P_{i} - D_{i} \\ 0 & if P_{i} - D_{i} \leq x \leq P_{i} + D_{i} \\ W_{i} \times (x - P_{i} - D_{i}) & if x > P_{i} + D_{i} \end{cases}$

We can prove that $f_i(x)$ $f_{i} (x)$ is convex for all $1 \le i \le N$ $1 \leq i \leq N$ using one of the conditions for convex functions:

A function $f$ $f$ is convex if for all $0 \le t \le 1$ $0 \leq t \leq 1$ and $x_1, x_2 \in X$ $x_{1}, x_{2} \in X$ (where $X$ $X$ is the domain of $f$ $f$ ), $f(tx_1+(1-t)x_2) \le tf(x_1)+(1-t)f(x_2)$ $f (t x_{1} + (1 - t) x_{2}) \leq t f (x_{1}) + (1 - t) f (x_{2})$ . Geometrically, this means that if we draw a line between $(x,f(x))$ $(x, f (x))$ and $(y,f(y))$ $(y, f (y))$ for any $x,y$ $x, y$ in $f$ $f$ 's domain, it must sit above the graph of $f$ $f$ . A bit of drawing on a sheet of paper and observing how $f_i$ $f_{i}$ looks like a straightened out parabola can help convince us that it satisfies the condition. However, we can also prove this formally by considering the $6$ $6$ possible cases of which piece of $f_i$ $f_{i}$ ( $f_i$ $f_{i}$ is piecewise) $x_1$ $x_{1}$ and $x_2$ $x_{2}$ fall on.

To complete our solution, observe that as the sum of convex functions is also convex, $F(x) = f_1(x)+f_2(x)+\dots+f_N(x)$ $F (x) = f_{1} (x) + f_{2} (x) + \dots + f_{N} (x)$ is convex as well. Thus we can binary search for the first point where $F(x)$ $F (x)$ changes from decreasing to non-decreasing, which will be our answer.

Evaluating $f_i(x)$ $f_{i} (x)$ for any $i,x$ $i, x$ takes $\mathcal{O}(1)$ $O (1)$ time, so evaluating $F(x)$ $F (x)$ takes $\mathcal{O}(N)$ $O (N)$ time.

Time Complexity: $\mathcal{O}(N \log P_i)$ $O (N \log P_{i})$

Comments

2

TheBoss123 commented on Jan. 10, 2022, 6:15 a.m. ← edited →

What data structure would be best to keep track of $P$ $P$ , $W$ $W$ , and $D$ $D$ ? (C++)

Also is sorting necessary in this problem?

2

DynamicSquid commented on March 11, 2021, 3:40 a.m.

For the second subtask, how do we check if a person is on the left of right of a position x? Would that require us to iterate over each person every time we move position x?

2

Overseas commented on March 11, 2021, 4:12 p.m.

binary search,

2

DynamicSquid commented on March 12, 2021, 3:11 a.m.

I tried binary search, but I can't get it to work. What am I doing wrong?

2

noirsnow commented on March 22, 2021, 12:45 a.m.

I first iterate over each person once to calculate and record the spots that weight changes when passing. Then I just loop through the line while checking the spots. This is enough to get through subtask 2.