xrisk's blog

Hint to solve "Sorting a Three-Valued Sequence” from IOI 96
By xrisk, history, 9 years ago, In English

Here is a description of the problem:

Sorting a Three-Valued Sequence IOI'96 — Day 2

Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

A small hint would be appreciated! I want to solve the problem myself, not have someone else solve it for me :D

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Small hint: say there are A 1's, B 2's and C 3's in the sequence; then you know that after sorting all 1's should be in the range [1, A], all 2's in the range [A+1, A+B] and all 3's in the range [A+B+1, A+B+C] (one-based indexing).

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

    Ty. I am getting some ideas now!

    → Reply