Editorial for SAC '22 Code Challenge 4 P5 - Obligatory Interactive Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
It suffices to count inversions by iterating over all pairs of indices (including ).
Time Complexity:
Query Count:
Subtask 2
Optimize the subtask solution by iterating over all pairs of indices excluding .
Time Complexity:
Query Count:
Subtask 3
This subtask was intended to reward solutions that use a heuristic that has a bad query constant.
Subtask 4
First, query heights. If there are more queries than people, output the permutation.
For the heights that were not found in the 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:
Query Count:
Note that other solutions that use probabilistic lemmas also suffice since the grader is not adaptive.
Comments