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)

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) through pure brute force or \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) time per query.

Time complexity: \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) time). By doing this, it is now possible to query in \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)


Comments

There are no comments at the moment.