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$ $j < i$ ).

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

Query Count: $N(N-1)$ $N (N - 1)$

Subtask 2

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

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

Query Count: $\frac{N(N-1)}{2}$ $\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$ $Q_{2}$ heights. If there are more $Q_2$ $Q_{2}$ queries than people, output the permutation.

For the heights that were not found in the $Q_2$ $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)$ $O (N \log N)$

Query Count: $\min(N, Q_2) + \max(0, (N-Q_2) \log(N-Q_2))$ $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.