Programming problem

[shankvee]

How can two gangsters who have never met before identify each other when they meet to
exchange stolen goods? One technique that we see in movies is to tear a photograph or
a currency note into two and send one piece with each of them. At the meeting the two
gangsters can verify each other’s identity by matching the two pieces.
What if K gangsters, K > 2, were to meet? We could tear up the photograph or currency
note into K pieces and send a piece with each of them. But then, when the gangsters
meet, they have to spend a long time solving a rather difficult jigsaw puzzle. In underworld
meetings, speed is of the essence, to avoid attracting the attention of the police.
The boss of one gang has come up with an intelligent plan that uses numbers rather
than photographs or currency notes. He picks a number N > K. He then partitions the set
{1, 2, . . . , N} into K nonempty collections and assigns one collection to each gangster who is
part of the meeting. When the K gangsters meet, all that they have to verify is that, between
them, they have all the numbers between 1 and N with no repetitions.
To make things more secure, the boss decides that he will not directly give each gangster
his collection. Instead, he plans to encode the collections as follows. Each element m in a
collection is replaced by the number of elements in the other collections that are less than
m.
For example, suppose that K = 3, N = 10 and the collections assigned to the three
gangsters are {5, 2, 9}, {1, 8, 7} and {10, 3, 6, 4}. Then, the coded collections given to these
three gangsters would be {3, 1, 6}, {0, 5, 5} and {6, 2, 3, 2}, respectively. In the first collection,
5 is replaced by 3, since there are three elements outside this collection, {1, 3, 4}, that are
less than 5. The number 2 is replaced by 1 since there is one element outside this collection,
{1}, which is less than 2. Finally, 9 is replaced by 6, since there are 6 elements outside
this collection, {1, 3, 4, 6, 7, 8}, that are less than 9. You can check that the other two coded
collections are also obtained in the same manner.
Unfortunately, the boss is still struggling to come up with a way for the K participants to
look at the K encoded collections that they have with them when they meet and reconstruct
the original collections assigned to each of them. Without this, they cannot verify that every
number between 1 and N appears in exactly one of these collections, which they need to do
to establish that there are no impostors in the meeting.
Your task is help the boss by writing a program that will look at all the coded collections assigned to the gangsters and reconstruct the actual collections assigned to each
of them. You can assume that the input to your program always describes a valid set of
coded collections—that is, a set for which the corresponding decoded collections constitute
a partition of {1, 2, . . . , N}

Okay what i thought was first Assigning the 0's in the code as 1,2.. in the decoded but i cant figure out what to do next? Algorithm will do Thanks.

[ausairman]

This is not a particularly complex problem, it just requires some though. If I did it for you I'd feel dirty for doing someone else's homework; how about trying it yourself and letting us know if you have any problems, and where.

[shankvee]

this isn't exactly homework i'm preparing for a national olympiad, i'm looking for some help coz this is the first time i'm solving such problems... If you still think this is my homework see http://www.iarcs.org.in/inoi/2005/inoi2005/inoi2005-qpaper.pdf The second question.

[Pravesh Koirala]

The only help that I can give you is that a single set is enough to decode it. i.e. {3,1,6} can be decoded by using only {3,1,6} (Ignoring the other two sets). that was a real nice question (just completed it).