Editorial for DMOPC '19 Contest 2 P3 - Selection

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: KevinWan

For subtask 1, a simple brute force algorithm will suffice. For each query, we can sort the subarray, take the $c$ ~c~th best item, and then revert the array to its original state.

Time complexity: $\mathcal{O}(MN \log N)$ ~\mathcal{O}(MN \log N)~

For subtask 2, we can build a Binary Indexed Tree (BIT) over our array and update it accordingly. For each query, we use our BIT to find the number of 1s in our subarray. If this is more than $c$ ~c~, then the $c$ ~c~th best item has goodness 1. Otherwise, it has goodness 0.

Time complexity: $\mathcal{O}((M+N) \log N)$ ~\mathcal{O}((M+N) \log N)~

For subtask 3, we instead build a BIT for the number of elements for each possible $g_i$ ~g_i~. Similar to subtask $2$ ~2~, we can use our BIT's to find for each possible $g_i$ ~g_i~, the number of elements that have $g_i$ ~g_i~ as its goodness. The $c$ ~c~th best item is thus the highest possible $k$ ~k~ such that the number of elements with a value greater than or equal to $k$ ~k~ is more than $c$ ~c~, which can be checked with our BITs.

Time complexity: $\mathcal{O}((M \max(g_i)+N) \log N)$ ~\mathcal{O}((M \max(g_i)+N) \log N)~

Comments

0

Swarley commented on Oct. 21, 2019, 3:46 p.m. ← edit 3 →

A segment tree for number frequency would suffice as well. $\mathcal{O}(20M \log N)$ ~\mathcal{O}(20M \log N)~

0

imasheepow commented on Oct. 21, 2019, 5:41 p.m.

"26 pbds" - ChrisT