Lance_HAOH's blog

By Lance_HAOH, history, 3 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

3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! Thank was indeed an eye-opener. I read that one can solve this problem by using Ford-Johnson's algorithm. However, there is lack of information about this algorithm's implementation details (one has to read knuth's book to understand it). Is there an easier way to solve this problem than to implement the lengthy algorithm?

3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Lance_HAOH (previous revision, new revision, compare).

5 weeks 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$$$.