Editorial for SAC '22 Code Challenge 4 P5 - Obligatory Interactive Problem


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

Subtask 1

It suffices to count inversions by iterating over all pairs of indices (including j < i).

Time Complexity: \mathcal{O}(N^2)

Query Count: N(N-1)

Subtask 2

Optimize the subtask 1 solution by iterating over all pairs of indices excluding j \le i.

Time Complexity: \mathcal{O}(N^2)

Query Count: \frac{N(N-1)}{2}

Subtask 3

This subtask was intended to reward solutions that use a heuristic that has a bad query constant.

Subtask 4

First, query Q_2 heights. If there are more Q_2 queries than people, output the permutation.

For the heights that were not found in the Q_2 queries, insert them into an array and sort it with any built-in function but create a custom comparator to interact with the grader.

After sorting it, output the permutation.

Time Complexity: \mathcal{O}(N \log N)

Query Count: \min(N, Q_2) + \max(0, (N-Q_2) \log(N-Q_2))

Note that other solutions that use probabilistic lemmas also suffice since the grader is not adaptive.


Comments

There are no comments at the moment.