1st Central European Olympiad in Informatics 1994

Day 2 Problem B Subsets

Lexicographic Ordering Problems

Let n be a positive integer. We consider an ordering <, called lexicographic ordering, defined on the subsets of {1,2,...,n}. Let S1={x1,...,xi} and S2={y1,...,yj} be two distinct subsets of {1,2,...,n} with x1<x2<...<xi and y1<y2<...<yj. Then we say that S1<S2 if there exists k with 0<=k<=min{i,j} such that x1=y1,...,xk=yk and either k=i or xk+1<yk+1.

For example, the subsets of {1,2,3} listed in lexicographic order are:


{}          1
{1}         2
{1,2}       3
{1,2,3}     4
{1,3}       5
{2}         6
{2,3}       7
{3}         8

The lexicographic ordering associates to each subset a natural number, as shown in the above example.

Your program should read lines from an ASCII file. Each line has one of the following forms:

1 n k

2 n k1 k2 . . . ki

If the line has the first form, you have to print on the display the subset of {1,2,...,n} whose associated number is k (supposing that k<=2n).

If the line is of the second form, you have to print the number associated with the subset {k1,...,ki} of {1,...,n} (supposing that k1<k2< ...<ki<n).

Your program should be able to produce the answer for each input line in at most 3 minutes, assuming that n<=30.

Solution (Michael Permana) :

Examine the following figure :


o         {}
| 
4--o      {1}
|  |      
|  2--o   {1,2}
|  |  |
|  |  1   {1,2,3}
|  |
|  1      {1,3}
|
2--o      {2}
|  |
|  1      {2,3}
|
1         {3}

Got the idea?

I discussed the problem with Michael Permana and he gave me this. He inspired me the general idea, but I coded the solution myself. He gave me a pseudocode, which I didn't understand at first. But thanks to him I got the idea. I think the figure above is the simplest way to express the idea about the solution

I also discussed the problem with Andy Kurnia and he gave me this. Lengthy explanation and blah blah blah. He expressed the idea about the solution in a different way. The whole idea is the same though...
ps : he used chronologic order instead of lexicographic...

yogy-n@sby.mega.net.id GeoCities