Internet Problem Solving Contest

IPSC 2002

Solution to Problem T – Ice Cream

We can use a QuickSort-like algorithm. Choose an arbitrary flavour p and divide the other ones into two groups. First group containing flavours which are preferred to p and in the secont group are flavours such that p is preferred to them. Then recursively sort these groups. The resulting order will be the first group sorted followed by p followed by second group sorted.

This algorith computes a consistent order of flavours. This can be proved by induction. Let a and b denote the size of the first and second group respectively. Then the (a+1)-th element of the resulting sequence is p. Now let's check for each i if i-th element of resulting sequence is preferred to (i+1)-th one. If i=a then i-th element is from first group and (i+1)-th element is p, but the definition of first group implies the consistency in this case. If i=a+1 then i-th element is p and (i+1)-th element is from the second group and by the definition of the second group implies the consistency in this case. For other values of i both i-th and (i+1)-th element are in the same group, which is recursively sorted.