The Revenge of Jalebi Bai
All submissions for this problem are available.
Jalebi Bai recently met her long time friend Barfi Tai. Instead of entertaining her guest, Barfi Tai kept boasting about her K marvelous necklaces made of black and golden beads. Jalebi Bai felt really jealous of it and decided to exact revenge.
She has invited Barfi to visit her home next week. Meanwhile, she is planning to buy a truly beautiful necklace to make Barfi jealous. According to her, a truly beautiful necklace should contain each of Barfi’s necklaces as a subsequence of it. Though still trying to show off, Jalebi Bai is smart and does not want to put a lot of money in it. So she wants to buy a truly beautiful necklace containing the minimum number of beads.
She goes to Devu Sunar and asks him to provide her such a necklace. Devu Sunar is busy this week and has asked you to help him in building the necklace. Please help him!
- A subsequence is a sequence that can be derived from another sequence by deleting some elements but without changing the order of the remaining elements. For example, the sequence [A,B,D] is a subsequence of [A,B,C,D,E,F].
- The bead patterns on the necklaces are not considered circular.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases is as follows.
The first line of each test case contains an integer K denoting the number of necklaces of Barfi.
K lines follow. Each of them contains a string made from the characters ‘B’ (representing black bead) and ‘G’ (representing golden bead), with the ith line denoting Barfi Tai's ith necklace.
For each test case, output a truly beautiful necklace with the minimum number of beads. If there are more than one such necklace, you are allowed to print any of them.
- 1 ≤ T ≤ 30
- 1 ≤ K ≤ 16
- 1 ≤ length of each necklace of Barfi ≤ 8
Input: 3 2 BG GB 2 BGB GG 3 BG GBB BGB Output: BGB BGGB BGBB
In the first example,
Devu can give necklace the BGB to Jalebi Bai, as it contains both the Barfi's necklace BG and GB as subsequence.
Note that Devu can also give GBG to Jalebi Bai.
In the second example,
Devu can give the necklace BGGB, as it contains both the Barfi's necklace BGB and GG as subsequence.
Note that there are many other possible truly beautiful necklaces of length 4, that Devu can give, e.g. BGBG or GBGB.
You are allowed to print any of them.
In the third example,
Devu can give the necklace BGBB or GBGB. You are print any of them as your answer.
|Tags||acm15kol, admin2, backtracking, shortest, supersequence|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.