ConcatGame | Topcoder Archive

Problem Statement

All strings in this problem are non-empty strings of lowercase English letters ('a'-'z').

There is one canonical order among these strings: the length-lexicographic order. In this order strings are ordered by length and ties are broken lexicographically.

For example, "cat" < "dog" < "cats".

When talking about smaller/bigger strings, we mean strings that are earlier/later in this order. For example, the smallest string out of all is "a" and the string "cats" is bigger than the string "dog".

You are given the int[] upperBounds.

Your friend Timmy just did the following steps:

For each element X of upperBounds he chose one of the X smallest strings. (He may have selected the same string multiple times.)
He reordered all those strings into an order of his choice and then concatenated them in the chosen order.
He announced that the result of this whole process was the string claim.

When concatenating the chosen pieces, Timmy is trying to create a string that is as large as possible. When announcing the result of the concatenation, Timmy may be lying.

Analyze Timmy's claim. Return the result of your analysis. There are four possible results:

"lie": We are sure that Timmy must be lying, he couldn't have obtained the string claim if he followed all the rules.
"good": Tommy may be telling the truth. If he is telling the truth, we can be sure that he did the concatenation optimally and got the largest possible result.
"bad": Tommy may be telling the truth. If he is telling the truth, we can be sure that he did the concatenation suboptimally - there was definitely a way to produce a bigger string.
"unknown": Tommy may be telling the truth. Neither the result "good" nor the result "bad" applies.

Definition

Class:: ConcatGame
Method:: analyze
Parameters:: int[], String
Returns:: String
Method signature:: String analyze(int[] upperBounds, String claim)
(be sure your method is public)

Constraints

upperBounds will have between 1 and 13 elements, inclusive.
Each element of upperBounds will be between 1 and 10,000,000, inclusive.
claim will have between 1 and 100 characters, inclusive.
Each character in claim will be a lowercase English letter.

Examples

```
{5, 5}
```
```
"go"
```
```
Returns: "lie"
```
Timmy must have selected two (not necessarily distinct) one-character strings from the set {"a", "b", "c", "d", "e"}. There is no way to concatenate two such strings and return the string "go", so Timmy is clearly lying.
```
{26, 26}
```
```
"go"
```
```
Returns: "bad"
```
Now Timmy can be telling the truth: it is possible that he chose the strings "g" and "o" and concatenated them to form "go". But if he did so, he clearly didn't do the concatenation optimally: if he did "o" + "g" = "og" instead, he would have created a bigger string.
```
{30, 20, 50}
```
```
"salad"
```
```
Returns: "good"
```
Timmy was selecting one string from the range "a"-"ad", one from the range "a"-"t", and one from the range "a"-"ax". The only way to build the string "salad" is to select the string "ad" from the first range, the string "s" from the second range, and the string "al" from the third range. If Timmy really selected these three strings, he did a good job concatenating them: "salad" is the biggest out of all the strings he could have obtained. (Other options he had include "sadal", "alads", and "adsal".)
```
{30, 100}
```
```
"abc"
```
```
Returns: "bad"
```
Timmy can be telling the truth, it is possible to obtain the string "abc": either as "a" + "bc", or as "ab" + "c". In either case Timmy did a bad job: if it was the first case, he should have announced "bca", and if it was the second case, he should have announced "cab" instead of "abc".
```
{200, 200}
```
```
"dad"
```
```
Returns: "unknown"
```
Here we know that Timmy can be telling the truth but we cannot judge how good he is at concatenating. This is because there are two plausible options: If Timmy chose the strings "d" and "ad", he did a good job concatenating them: "dad" is bigger than "add". However, if Timmy chose the strings "da" and "d", he did a bad job concatenating them: "dda" would have been bigger than "dad".
```
{10, 100, 1000}
```
```
"topcoder"
```
```
Returns: "lie"
```
Timmy is clearly lying, the string he announced is too long for the options he had.

{10, 100, 1000, 10000, 100000}

"topcoder"

Returns: "bad"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.