This problem seems to be very strange. The graph theory sais that it always has a solution. But I think, that any algorithm works slower than O(K^2) and for K=50000 it is TLE. The O(K) algorithm (like Locomotive's one) is obviously incorrect, because gives the wrong answer even in a sample input.

(The first two sets in sample input: 1 3 5 6 4 and 1 3 5 6 3 are similar, but his program sais that I must send these sets to shop №1.)

The problem sais that two sets are "similar" if one of them is obtained by deleting one good form the second set or by replacing one good to another. But if the similar sets can be obtained only by deleting one good, the Locomotive's solution is correct.

Maybe the problem text is incorrect, or there is no tests with K=50000 (so I can solve it, finding the minimal number of colors to paint this graph in O(K^2)).

Who can tell me, why I am wrong?

Edited by author 07.08.2004 11:57

Obvious correct solution is O(input_size)

Is locomotive's the correct solution?
If the text is correct,why 1 2 3 4 and 1 5 4 3 can be put in the same shop in his answer?
They are similar!

Read problem statement carefully, and you'll easily solve this task: there are k DIFFERENT set of goods in the warehouse...

Edited by author 08.08.2006 13:58