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 cth best item, and then revert the array to its original state.

Time complexity: \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, then the cth best item has goodness 1. Otherwise, it has goodness 0.

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

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

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


Comments


  • 1
    pblpbl  commented on March 21, 2020, 11:24 p.m. edit 2

    For the third subtask, how do the queries process the range l, r? It seems like the BIT does not track the range.

    edit: figured it out, ignore pls


  • 0
    Swarley  commented on Oct. 21, 2019, 11:46 a.m. edit 2

    A segment tree for number frequency would suffice as well. O(20mlog(n))