NBLTHIEF - The Nobel Thief

no tags 

The Nobel Prize of Kabiguru Rabindranath Thagore was stolen from a museum of Viswa Bharati University in West Bengal. The Central Bureau of Investigation (CBI) has been assigned the job to investigate the crime and recover the prize. CBI has identified some suspects and linked each one of them to a distinct subset of a set of clues.

Let there be p suspects and q clues. Integers 1 to p identify suspects while q distinct letter-codes identify clues. The clues are of varying importance. The alphabetic order of letter-codes determines the priority order in the clues; letter-codes 'a' to 'z' vary from highest to lowest priority.

Let L0 be the set of all suspects. Based on a clue '$ \alpha$', a subset L of L0 may be split into two disjoint subsets L+ $\scriptstyle \alpha$ and L- $\scriptstyle \alpha$. The subset L+ $\scriptstyle \alpha$ includes all elements of L that are linked to a subset of clues containing '$ \alpha$' and L- $\scriptstyle \alpha$ includes all other elements of L. Let n, n+ $\scriptstyle \alpha$, and n- $\scriptstyle \alpha$ denote respectively the total number of elements in L, L+ $\scriptstyle \alpha$ and L- $\scriptstyle \alpha$. The discriminatory power of a clue '$ \alpha$' to discriminate suspects in L is defined by $ \delta_{\alpha}^{}$ = - (| n+ $\scriptstyle \alpha$ - n- $\scriptstyle \alpha$|)

Let L* denote a set of disjoint subsets of L0, each subset containing two or more elements. The discriminatory power $ \delta_{\alpha}^{*}$ of a clue '$ \alpha$' to discriminate suspects in subsets contained in L* is defined to be the sum of all $ \delta_{\alpha}^{}$'s corresponding to each subset in L*.

CBI wants to select a set D of dominant clues so that the presence or absence of some or all of these clues can identify each suspect uniquely. The selection is to be done in stages.

Let L* contain only L0 initially. At each stage of selection a clue '$ \beta$' with highest discriminatory power $ \delta_{\beta}^{*}$ is selected. Selecting the clue '$ \beta$' with highest priority breaks tie, if any. After a selection of '$ \beta$' each L in L* is split into disjoint subsets L+ $\scriptstyle \beta$ and ' L- $\scriptstyle \beta$' all resulting subsets with less than two elements are dropped from L*. The process of selection continues until L* becomes empty. All the clues thus selected form the set of dominant clues D.

You are required to write a program to find the set of dominant clues D.


Input may contain multiple test cases. For each test case input is given in one line. It contains an integer k representing the case number and a certain number of strings of clues. The i-th string represents the subset of clues to which the i-th suspect is linked. A space separates two consecutive fields in input.

Input terminates with an input 0 for the case number k.


For each test case, present output in one line. The line contains the case number k and a string of letters. The letters in the string correspond to the clues in D and appear in the order of their selection.

Sample Input 

1 cbx cpxb bc brc
2 bac adce cbd d

Sample Output 

1  xpr
2  ab

Kanpur-Kolkata 2004-2005

Added by:Duc
Time limit:0.179s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2004