CCC '21 S3 - Lunch Concert - DMOJ: Modern Online Judge

CCC '21 S3 - Lunch Concert

Points: 10 (partial)

Time limit: 3.0s

Memory limit: 1G

Author:

Problem type

Canadian Computing Competition: 2021 Stage 1, Senior #3

It's lunchtime at your school! Your $N$ $N$ friends are all standing on a long field, as they usually do. The field can be represented as a number line, with the $i^\text{th}$ $i^{th}$ friend initially at position $P_i$ $P_{i}$ metres along it. The $i^\text{th}$ $i^{th}$ friend is able to walk in either direction along the field at a rate of one metre per $W_i$ $W_{i}$ seconds, and their hearing is good enough to be able to hear music up to and including $D_i$ $D_{i}$ metres away from their position. Multiple students may occupy the same positions on the field, both initially and after walking.

You're going to hold a little concert at some position $c$ $c$ metres along the field (where $c$ $c$ is any integer of your choice), and text all of your friends about it. Once you do, each of them will walk along the field for the minimum amount of time such that they end up being able to hear your concert (in other words, such that each friend $i$ $i$ ends up within $D_i$ $D_{i}$ units of $c$ $c$ ).

You'd like to choose $c$ $c$ such that you minimize the sum of all $N$ $N$ of your friends' walking times. What is this minimum sum (in seconds)? Please note that the result might not fit within a $32$ $32$ -bit integer.

Input Specification

The first line of input contains $N$ $N$ .
The next $N$ $N$ lines contain three space-separated integers, $P_i$ $P_{i}$ , $W_i$ $W_{i}$ , and $D_i$ $D_{i}$ $(1 \le i \le N)$ $(1 \leq i \leq N)$ .

The following table shows how the available $15$ $15$ marks are distributed.

Subtask	$N$ $N$	$P_i$ $P_{i}$	$W_i$ $W_{i}$	$D_i$ $D_{i}$
$4$ $4$ marks	$1 \le N \le 2\,000$ $1 \leq N \leq 2 000$	$0 \le P_i \le 2\,000$ $0 \leq P_{i} \leq 2 000$	$1 \le W_i \le 1\,000$ $1 \leq W_{i} \leq 1 000$	$0 \le D_i \le 2\,000$ $0 \leq D_{i} \leq 2 000$
$9$ $9$ marks	$1 \le N \le 200\,000$ $1 \leq N \leq 200 000$	$0 \le P_i \le 1\,000\,000$ $0 \leq P_{i} \leq 1 000 000$	$1 \le W_i \le 1\,000$ $1 \leq W_{i} \leq 1 000$	$0 \le D_i \le 1\,000\,000$ $0 \leq D_{i} \leq 1 000 000$
$2$ $2$ marks	$1 \le N \le 200\,000$ $1 \leq N \leq 200 000$	$0 \le P_i \le 1\,000\,000\,000$ $0 \leq P_{i} \leq 1 000 000 000$	$1 \le W_i \le 1\,000$ $1 \leq W_{i} \leq 1 000$	$0 \le D_i \le 1\,000\,000\,000$ $0 \leq D_{i} \leq 1 000 000 000$

Output Specification

Output one integer which is the minimum possible sum of walking times (in seconds) for all $N$ $N$ of your friends to be able to hear your concert.

Sample Input 1

Copy

1
0 1000 0

Output for Sample Input 1

Copy

Explanation of Output for Sample Input 1

If you choose $c = 0$ $c = 0$ , your single friend won't need to walk at all to hear it.

Sample Input 2

Copy

2
10 4 3
20 4 2

Output for Sample Input 2

Copy

Explanation of Output for Sample Input 2

One possible optimal choice of $c$ $c$ is $14$ $14$ , which would require your first friend to walk to position $11$ $11$ (taking $4 \times 1 = 4$ $4 \times 1 = 4$ seconds) and your second friend to walk to position $16$ $16$ (taking $4 \times 4 = 16$ $4 \times 4 = 16$ seconds), for a total of $20$ $20$ seconds.

Sample Input 3

Copy

Output for Sample Input 3

Copy

Comments

-4

Ri_Si_Zz commented on Oct. 29, 2024, 7:20 p.m. ← edited →

OMG my friend Sam thought of a solution in 5s

-8

hostsjim commented on Jan. 19, 2024, 2:41 p.m. ← edit 7 →

I found a way to AC without binary search and with time time complexity of o(n) just consider a function like this: f(x) = $1/2 * W * |x-(P-D)| + 1/2 * W * |x-(P+D)| -W * D$ $1 / 2 * W * | x - (P - D) | + 1 / 2 * W * | x - (P + D) | - W * D$ this means on point can be considered as two points with half of the weight and D = 0. Then finally minus WD when you calculate the time but if you directly calculate WD's sum will cause numerical overflow so it will be better to minus 1/2WD each time

https://dmoj.ca/src/6088148

This comment is hidden due to too much negative feedback. Show it anyway.

2

d commented on Jan. 20, 2024, 3:08 a.m.

Unfortunately, your code is $\mathcal O(N \log N)$ $O (N \log N)$ because of a = sorted(a, key=lambda x: x[0])

7

tyoueenn commented on Jan. 20, 2024, 12:34 a.m.

I would recommend you to post it in the editorial instead of here

-16

kopichiki commented on Aug. 13, 2022, 7:02 p.m. ← edit 2 →

Why isn't my code working? I passed all of the test cases... https://dmoj.ca/src/4767082

This comment is hidden due to too much negative feedback. Show it anyway.

7

omaewamoushindeiru commented on Aug. 16, 2022, 6:43 a.m. ← edited →

because it is printing the wrong answer or taking too long to print the wrong answer.