When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Lance_HAOH's blog

By Lance_HAOH, history, 7 years ago, In English

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.

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I bumped into the same problem. The following does also work for any $$$N$$$ (up to $$$N=9-10$$$ due to its complexity):

Let's get a list of all permutations of $$$( 0,1, ... ,n-1 )$$$. (there is std::next_permutation for that)
In each iteration get a pair of $$$( i,j )$$$ where the difference of the number of permutations containing $$$i$$$ before $$$j$$$, and the number of them containing $$$j$$$ before $$$i$$$ is minimal.
Check the ordering of $$$( v[i],v[j] )$$$, then remove all permutations, where $$$( i,j )$$$ are in the wrong order.

If there is only one permutation left, we stop and that permutation is the sorted order of $$$v$$$.