Editorial for DMOPC '19 Contest 5 P4 - Cafeteria Confrontation Conundrum

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.

Subtask 1

For the first subtask, it suffices to simply brute force everything: for every query, iterate over every person and calculate the total amount of money you can get from each chain. Stop when you reach a chain that has enough money.

Time complexity: $\mathcal O(QN^2)$ ~\mathcal O(QN^2)~

Subtask 2

For the second subtask, we can note that instead of recomputing the sum of each chain for every query, we can preprocess it. Preprocessing takes $\mathcal O(N^2)$ ~\mathcal O(N^2)~ through pure brute force or $\mathcal O(N)$ ~\mathcal O(N)~ by making the observation that you can reuse previously computed sums. Then for each query, you can brute force the smallest person in $\mathcal O(N)$ ~\mathcal O(N)~ time per query.

Time complexity: $\mathcal O(QN)$ ~\mathcal O(QN)~

Subtask 3

The intended solution for this subtask is to construct and prefix maximum array from the sum array described in Subtask 2 (which can also be done in $\mathcal O(N)$ ~\mathcal O(N)~ time). By doing this, it is now possible to query in $\mathcal O(\log N)$ ~\mathcal O(\log N)~ time by doing binary search to find the smallest index rather than resorting to brute force.

Time complexity: $\mathcal O(Q \log N)$ ~\mathcal O(Q \log N)~

Comments

There are no comments at the moment.