Training Gateway Greedy Algorithms Text

Problems and Contests
#1

Hi,

I am currently going through Chapter 1 of the Training Gateway. In section 1.4, I’m reading the text for Greedy Algorithms. There is 1 part I do not understand:

Sorting a three-valued sequence [IOI 1996]

You are given a three-valued (1, 2, or 3) sequence of length up to 1000. Find a minimum set of exchanges to put the sequence in sorted order.

Algorithm The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1’s in the 2 part with 2’s in the 1 part, as many as possible 1’s in the 3 part with 3’s in the 1 part, and 2’s in the 3 part with 3’s in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1’s into place and then all the 2’s into place.

Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no “interference” between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1’s are put in place but no others; then all that remains are 2’s in the 3’s place and vice-versa, and which can be swapped).

Can you please explain the algorithm to me? What would be the 1 part, 2 part, and 3 part? How would we exchange the i's in the $j$th part and the j's in the $i$th part? Can you please show me a step-by-step example for this?

Additionally, how does the second section of the solution work (rotating elements)? Why would the best we can do be 2 swaps for every 3 elements not in the correct location?

I would also appreciate it if you can explain why this is greedy. What role does optimization play in this problem?

Thank you.

#2

Consider sorting (2,1,2,1,2,1)\to (1,1,1,2,2,2). First half of the output sequence would be the part which will be 1 when in sorted order, second half would be the part which will be 2 when in sorted order.

Consider (2,2,3,3,1,1)\to (1,1,2,2,3,3).

(What’s the fastest way to sort each of the above sequences?)

Find a minimum set of exchanges

#3

If I understand correctly, is this the step-by-step method?
(1) 3 1 2 1 1 2 2 3
(2) 1 3 2 1 1 2 2 3
(3) 1 3 1 2 1 2 2 3
(4) 1 3 1 1 2 2 2 3
(5) 1 2 1 1 2 2 3 3
(6) 1 1 2 1 2 2 3 3
__ 1 1 1 2 2 2 3 3

So by swapping1’s in the 3’s section and vice-versa, does it mean swapping the pairs where 1 is after 3 (ie. not in the right order)?

I am not following this. Why doesn’t it matter which order we swap the (1,3), (2,3), (1,2) in? Why will the number of moves be the same, and what does it mean by “no interference” between the types of pairs we swap?

For example, from (4) we could have done:
(4) 1 3 1 1 2 2 2 3
(5) 1 1 3 1 2 2 2 3
(6) 1 1 1 3 2 2 2 3
__ 1 1 1 2 2 2 3 3

Where, instead of swapping 2’s and 3’s, then 1’s and 2’s, we swapped 1’s and 3’s, then 2’s and 3’s. So why does this “different types of elements” simplification work?

What about (1,3,2), (2,1,3), or (3,2,1)? Those require just 1 swap. Why is 2 the best we can do for each set of 3?

Can you please explain why the above is optimal? Why should we swap i's and j's in the wrong orders first? Then, why is rotating the set of 3 optimal? Why does this, either logically or rigorously, produce the minimum set of exchanges?

#4

No, it doesn’t have anything to do with inversions. If the original sequence is (3,1,2,1,1) then your first step is not to swap the first two elements. A better first step is to swap the first and the last elements, so we never have to make a swap involving either the first or last element again.

Once those swaps have been performed

For these cases, there exists a swap that puts two elements into place. We’re considering cases where no such swap exists.

#5

Thank you; I think I now understand the “3 parts” and the swaps between 2 out-of-place categories. Essentially, we’re performing as many swaps as possible that put 2 elements in place, right?

Can you please confirm the following steps (where commas separate the 3 parts)?
2 1 3 1, 1 3 2, 2 1 (1st swap)
2 1 1 1, 1 3 2, 2 3 (2nd swap)
1 1 1 1, 2 3 2, 2 3 (3rd swap)
1 1 1 1, 2 2 2, 3 3

Would this be correct, then, for the second part of the algorithm (2 swaps for every 3 elements out of place)?
3 1 2, 1 2 1, 2, 2 3
3 1 1, 2 2 1, 2 3
The bolded elements above are now a set of 3 that are out of place, so rotate them by swapping 2 elements sequentially into place.

Different types of elements means swapping (1,3), (2,3), and (1,2) that are in the wrong place, right? What does the analysis mean by “intereference” between them?

Why will elements not interfere with each other? For example, a 1 can be swapped multiple times, right? It may be swapped with a 2 and then in another swap with a 3?

Does the algorithm swap 2 elements into place and then keep them in place? So then the next swaps use 2 new elements to put into place? Then how does “intereference” relate to this?

Exactly why is this algorithm optimal? The first part achieves maximal effect by correcting 2 numbers with each swap. However, in part 2 we built off part 1 and rotate twice for every remaining set of 3. Why does this “building off” previous optimal steps work? Why does the tradeoff in part 2 (additional rotations) for the optimal steps in part 1 (2-step swaps) still produce the best result?

Thank you.

#6

Yes.

Yes. So they don’t interfere.

Induction probably suffices.