Indian Computing Olympiad

Training Material


Sorting→Utopia (IOI 2002)

Suppose we number the four quadrants on the coordinate plane as follows.

                       2      |      1
                              |
                --------------+--------------
                              |
                       3      |      4
      

We are given a sequence over {1,2,3,4}, e.g. 1244112431. This specifies an order in which the quadrants are to be visited --- we have to first move to quadrant 1, then quadrant 2, then quadrant 4, then stay in quadrant 4, ....

This tour consists of N stops, q1q2...qN. We are then provided with 2N distinct postive integers d1,d2,...,d2N. (N is in the range [1..10000].)

The tour starts at (0,0). We now have to group the 2N numbers into N pairs (x1,y1), (x2,y2), ..., (xN,yN). We can insert negative signs, if required, before each xi or yi.

Intepret these pairs as displacements. This constructs a tour as follows.

        Point                Current Quadrant

        p0  (0,0)
        p1  (x1,y1)                    v1
        p2  (x1+x2,y1+y2)              v2
        p3  (x1+..+x3,y1+..+y3)        v3
        .
        .
        .
        pN  (x1+..+xN,y1+..+yN)        vN
      

The goal is to make the sequence of quadrants visited v1v2...vN equal to the original sequence q1q2...qN.

For instance, suppose the desired trajectory is 4 1 2 1 and there are 8 numbers 7, 5, 6, 1, 3, 2, 4, 8, here is a solution:

        (+7,-1), (-5,+2), (-4,+3), (+8,+6)
      

Solution

Simplified version:

We work along one axis, divided into two regions + or -.

                 -                  +
        ------------------|------------------
                          0
      

We have a {+,-} sequence of length N that describes a trajectory. We are given N numbers. We begin at the origin. We have to fix an ordering of the N numbers and insert signs to obtain a sequence of N displacements that traces out the required trajectory.

For example, suppose that

  • The required trajectory is + + - +
  • The values we are given are 4 5 2 8

If we assign the signs as +4, -5, -2, +8, we can trace out the required trajectory by the sequence +4 -2 -5 +8.

Suppose we have a sorted sequence x1, x2, ..., xN in which we insert + and - signs alternately (we may start with + or - for x1).

Suppose we pick a subsequence xi,...,xj. Observe that the sign of sum(xi,...,xj) will always be the same as the sign of xj.

Pair xj with xj-1 etc. Each pair has the same sign as xj and they add up. If the sequence is of odd length, you are left with an extra unpaired element on the left, but this is of the same sign.

Now, observe the following. Given sum(xi,...,xj):

  • if we add xj+1 (the next larger number with an opposite sign to xj), the sign of the sum (xi,...,xj+1) flips
  • if we add xi-1 (the next smaller number with an opposite sign to xi), the sign of the sum (xi-1,...,xj) is the same as the sign of sum of (xi,...,xj)

We can thus use the sorted sequence with alternating signs provided we know

  • how to assign the alternating signs
  • where in the sorted sequence we start

Wherever we start, we move right each time we want to flip the sign and move left each time we retain the sign. So, we can determine the starting position by counting, in the given tour, the number of sign changes.

Having fixed the position that we start, the sign of this element is determined by the sign of the first element of the sequence. We then propagate alternating signs from this point.

In our earlier example, + + - +, the sorted sequence is 2 4 5 8. There is one move that does not change sign, so we start at 4. The first side we have to visit is +, so the sign of 4 is +. So, we work with the signed sequence -2,+4,-5,+8. The order in which we choose the displacements is +4, -2, -5, +8 (the order of points visited is +4, +2, -3, +5).

Suppose instead the desired tour was + + - -. We now have two moves that do not change sign, so we start with 5 and make it +5, giving the sequence +2, -4, +5, -8. The moves are now +5, -4, -8, +2 (points visited are +5, +1, -7, -5).

Observe that the solution is always feasible, for any choice of traversal and displacements!

Back to 2 dimensional utopia

We can represent each quadrant in terms of the sign of the x and y coordinates. Thus, 1 = (+,+), 2 = (-,+), 3 = (-,-), 4 = (+,-). We can then split the sequence of quadrants into two signed sequences, one for x and one for y. Divide the initial 2n numbers into two sets of n, one for x and one for y and solve the one dimensional problems for x and y independently.