I am trying to solve an interactive problem from atcoder's practice contest. The abridged problem statement is as follows:

Given the value of N where N ranges from [1,26] and Q where Q is the maximum number of queries that one can make, sort a list of distinct uppercase alphabets in ascending order. N indicates that there are N characters starting from 'A'. Hence, N = 5 means that our final list must contain 'A', 'B', 'C', 'D' and 'E'.

A single query is defined as printing out a string "? x y" where x and y represent the characters we want to check the relation between (e.g. "? A B"). The problem restricts the number of such queries to Q. Hence, we must determine the final order of the characters using at most Q queries.

For each query, we get a binary answer '<' or '>' from stdin. '<' indicates that x comes before y in the final list. '>' means otherwise.

Problem link: here (Do note that atcoder account is needed to view the task)

My attempt:

I tried using merge sort to solve the problem — I changed the comparison at the merging step to get the ordering of characters using the console. I managed to solve constraints for N=26, Q=100. However, the strictest task requires a solution that fulfils the constraints N=5, Q=7.

After some research, I found that merge sort's worst case number of comparisons is n * ceil(logn) — 2^(ceil(logn)) + 1 which gives 8 in this case. I couldn't find a better sorting algorithm that would solve the problem — I even tried STL sort which proved to be worse than merge sort.

Could anyone please advise me on how I could solve this problem?

U.D. I just revisited this problem today. I solved it by using a single comparison to detect if there were exactly 5 elements with at most 7-comparisons. If this were true, I hard-coded a separate comparison-efficient function to handle this. Otherwise, just use merge-sort.

AC code here.