TopCoder problem "RangeGame" used in SRM 174 (Division I Level Two)

Problem Statement

Imagine a game consisting of two billion doors (numbered starting at 1), behind some of which lie fabulous cash prizes. There are a limited number of patterns to the placement of the prizes, which the contestant knows in advance. All doors initially begin closed. Before the game begins, the host secretly selects one of the patterns from the list at random (all with equal probability), and puts prizes behind the doors specified by the pattern. For example, if the host chose the pattern "3-4 9 12-15", he would put prizes behind doors 3, 4, 9, 12, 13, 14, and 15 (and nowhere else).

Two things happen every turn. First, the contestant decides which door is currently most likely to contain a prize, and secretly records this choice. (If two or more doors both have the greatest likelihood of containing a prize, he chooses the door with the lowest number.) The second part of a turn consists of the host opening one or more doors, all of which are revealed to be empty. For example, if the host gave the hint "2 7-10", this would indicate that he opened doors 2, 7, 8, 9, and 10 and there were no prizes behind any of them.

In specific, the following grammar is used for this problem:

<doors> ::= <range> | <range><sp><doors> <range> ::= <num> | <num><to><num> (the first num must be strictly less than the second num)<num> ::= integer between 1 and 2000000000, inclusive, with no leading zeroes <sp> ::= ' ' <to> ::= '-'

Given a String[] possible, containing the possible placements of prizes, and a String[] hints, the N hints given during the course of the game, your method should return a int[] containing N+1 elements. Each element should describe the most likely position of a prize at that point in the game. The first element represents your guess before any hints are given; the last element represents your guess taking every hint into account. Remember to break ties by choosing the lowest numbered door, if multiple doors are all the most likely.

Definition

Class:	RangeGame
Method:	bestDoors
Parameters:	String[], String[]
Returns:	int[]
Method signature:	int[] bestDoors(String[] possible, String[] hints)
(be sure your method is public)

Notes

- Each element of possible has an equal chance of being the pattern that is chosen by the host. This means that if one pattern appears on the list twice, it is twice as likely of being chosen as a pattern which appears on the same list only once.

Constraints

- possible will contain between 2 and 50 elements, inclusive.

- Each element of possible will contain between 1 and 50 characters, inclusive.

- Each element of possible will conform to the rules of <doors>, as specified in the grammar above.

- For each element of possible, the ranges contained therein will be non-overlapping and in ascending order.

- hints will contain between 0 and 50 elements, inclusive.

- Each element of hints will contain between 2 and 50 characters, inclusive.

- Each element of hints will conform to the rules of <doors>, as specified in the grammar above.

- For each element of hints, the ranges contained therein will be non-overlapping and in ascending order.

- The information given in hints will always be consistent with at least one pattern in possible.

Examples

{"1-100","100-200","200-300"}

{"50-75","250-1000"}

Returns: { 100,  200,  100 }

There are three possible patterns of prizes: doors 1-100, doors 100-200, or doors 200-300. Before any hints are given, you know that doors 100 and 200 are more likely than the rest; the odds of a prize being in either of them are 2/3, whereas the odds of a prize being in any other door 1-300 is only 1/3. Doors 100 and 200 are the most likely, so your first guess should be 100 (since it is smaller).

Then the host reveals that there are no prizes behind doors 50-75. Pattern "1-100" is now no longer an option. You now know for sure that there is a prize in door 200, whereas the odds for any other door 100-300 is only 1/2. Therefore, 200 is the second element of the return list.

Finally, the host opens doors 250-1000 and shows them all to be empty. You now know the pattern must be "100-200", so you choose the smallest door of this group, 100, to be your final answer.

{"100-900 1111","200-800 2222","300-700 3333","4444"}

{"2000-4000","500"}

Returns: { 300,  100,  4444 }

Before any hints are given, doors 300-700 are the most likely to contain prizes. The first hint tells you that doors 2222 and 3333 are empty, leaving only the first and last patterns as options. The second hint eliminates the first pattern, so the only prize must be in room 4444.

{"346591240","858005279","1321831520","1453846384","1972718383","530431653-1848872872"}

{"1400000000-2000000000","400000000-600000000"}

Returns: { 858005279,  346591240,  346591240 }

Beware of large numbers and ranges!

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2233

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4675&pm=2233

Writer:

LunaticFringe

Testers:

lbackstrom , brett1479

Problem categories:

Math, String Parsing