DMOPC '20 Contest 1 P2 - Victor's Moral Dilemma

Points: 5

Time limit: 0.6s

Memory limit: 128M

Author:

Problem type

Is killing an innocent person strictly wrong? ~ Victor, 2019

Victor has become obsessed with the Trolley Problem! Victor found the original trolley problem too boring, so he has devised his own version. In Victor's trolley problem, there is initially an array of $N$ ~N~ trolleys, $D$ ~D~ days, and the $k$ ~k~th trolley contains $A_k$ ~A_k~ people. On the $i$ ~i~th day, Victor lines up all the remaining trolleys, and picks a number $n_i$ ~n_i~. He will then partition his array into two subarrays, $F = [A_1,A_2,\dots,A_{n_i}]$ ~F = [A_1,A_2,\dots,A_{n_i}]~ and $S = [A_{n_i+1},A_{n_i+2},\dots,A_{m_i}]$ (where $m_i$ ~m_i~ is the total number of trolleys on day $i$ ~i~). If $\mathrm{sum}(F) \ge \mathrm{sum}(S)$ ~\mathrm{sum}(F) \ge \mathrm{sum}(S)~, then Victor will snap all the trolleys in $F$ ~F~ out of existence and set $A$ ~A~ equal to $S$ ~S~. Otherwise, he will snap all the trolleys in $S$ ~S~ out of existence and set $A$ ~A~ equal to $F$ ~F~.

Calculate the number of people Victor snaps on each day!

Constraints

$1 \le N \le 10^6$ ~1 \le N \le 10^6~
$1 \le D \le N$ ~1 \le D \le N~
$1 \le a_k \le 10^3$ ~1 \le a_k \le 10^3~
$m_i \ge 1$ ~m_i \ge 1~ for all $i$ ~i~.
The order of the trolleys will always remain the same.
$1 \le n_i \le m_i$ ~1 \le n_i \le m_i~ for all $i$ ~i~.

Input Specification

The first line will contain two space-separated integers $N$ ~N~ and $D$ ~D~, denoting the initial number of trolleys and the number of days respectively.

The next line will contain $N$ ~N~ space-separated integers $a_1, a_2, \dots, a_N$ ~a_1, a_2, \dots, a_N~, denoting the number of people in each trolley.

The next $D$ ~D~ lines will each contain a single integer $n_i$ ~n_i~.

Output Specification

For each day, output the number of people that Victor will snap out of existence on a new line.

Sample Input

8 3
6 1 3 2 9 10 2 4
4
1
1

Sample Output

25
6
5

Explanation of Sample Output

On the first day, $F=[6,1,3,2]$ ~F=[6,1,3,2]~ and $S=[9,10,2,4]$ ~S=[9,10,2,4]~. Then, $\mathrm{sum}(F)=12$ ~\mathrm{sum}(F)=12~ and $\mathrm{sum}(S)=25$ ~\mathrm{sum}(S)=25~. Since $12<25$ ~12<25~, Victor will snap trolleys $5$ ~5~ to $8$ ~8~ out of existence, leaving $[6,1,3,2]$ ~[6,1,3,2]~ as our array of trolleys.

On the second day, $F=[6]$ ~F=[6]~ and $S=[1,3,2]$ ~S=[1,3,2]~. Then, $\mathrm{sum}(F)=6$ ~\mathrm{sum}(F)=6~ and $\mathrm{sum}(S)=6$ ~\mathrm{sum}(S)=6~. Since $6 \ge 6$ ~6 \ge 6~, Victor will snap the first trolley and leave $[1,3,2]$ ~[1,3,2]~ as our array.

On the third and last day, $F=[1]$ ~F=[1]~ and $S=[3,2]$ ~S=[3,2]~. Then, $\mathrm{sum}(F)=1$ ~\mathrm{sum}(F)=1~ and $\mathrm{sum}(S)=5$ ~\mathrm{sum}(S)=5~. Since $1 < 5$ ~1 < 5~, Victor will snap the last two trolleys and leave $[1]$ ~[1]~ as our array.

Comments

0

valegrete commented on Jan. 14, 2023, 9:33 p.m. ← edit 2 →

I'm still not sure why the brute force solution works given that $N$ ~N~ and $D$ ~D~ can be up to $10^6$ ~10^6~ with $a_k$ ~a_k~ up to $10^3$ ~10^3~. The fact that this is, at most, $N \log sum(a_k)$ ~N \log sum(a_k)~, makes sense. But when you plug numbers in, that's 30 million operations just in the iteration and summations. In the worst case scenario, a Python solution should take roughly 6 seconds, but mine finished in 0.2. Do the test cases not actually hit the constraint extremes? I am new to efficiency analysis so I'm sure I'm just missing something.

-2

ross_cleary commented on Oct. 13, 2020, 12:53 p.m. ← edited →

It's too bad that brute force $\mathcal{O}(ND)$ ~\mathcal{O}(ND)~ solutions passed during the contest, this was a nice prefix sum array problem.

19

Kirito commented on Oct. 13, 2020, 1:01 p.m. ← edited →

You can prove that the brute force solution only takes $\mathcal O(N \log N)$ ~\mathcal O(N \log N)~ time, and was in fact intended.

0

ross_cleary commented on Oct. 13, 2020, 6:12 p.m. ← edited →

Interesting, if there was no upper bound on $a_k$ ~a_k~, would $\mathcal{O}(ND)$ ~\mathcal{O}(ND)~ be worst case.

9

Tzak commented on Oct. 13, 2020, 7:16 p.m.

Water is wet