RangeGame
SRM 174 · 2003-12-13 · by LunaticFringe
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
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
, 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
, 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.
{"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!
{"132447405 503544040-715973485 870200752-956544119",
"440049267 841256627 1241586057",
"143874572-187537992",
"932502012-1085870188",
"1708889038-1991574143",
"911181254",
"548114547 866929779 1668234563-1978195718",
"467794707",
"551581396 1148184404",
"237081393-380066752 830822133-1024839262",
"77696488-217679535 1278558658 1776485780",
"597956231-779614167",
"80727418-172687869 500179896 1521697244 1895196968",
"229976197-344997820",
"1087891781 1288379708-1334482037 1965935685",
"300141226-382907261 1218123340 1931738268",
"520690996 1696041786",
"534278455-556098837 1545131273 1721738340",
"229536304 643356527 822238152-901711165 1239153872",
"411794115-565530322 1736054227-1780499136",
"1249293313-1425652429 1612552532",
"458805831-524707218 1214632828-1421293305",
"297795447-314646881 445588509-595896973 1720780033",
"201826750-316108869 450664772 1528814748",
"19567648-33895381 578571750-767131664 1006672000",
"25972710 1071542579 1538710581 1787738190",
"156037887-277290566 1804132015",
"660515267 1493049654",
"371295219 1465967224 1618792601-1749577437",
"566394086 1041682040-1177307168"}
{"263517117 539336844-549676969 851117406 1498595346",
"15272923-170480950 635191484-799829499",
"1128715543",
"531444683-667303543 1858056624-1978483140",
"71123728-159755693 575537168 1549705716 1986536228",
"1521265477-1570928024 1810696046",
"484383335-734836289 910114111-976923180 1933996364",
"6466685 706868993 1510388152-1555366471 1915824408",
"180650469 510149509 1554480570-1562156387",
"37278659",
"1540197963 1985794262"}
Returns: { 300141226, 143874572, 1288379708, 1288379708, 467794707, 467794707, 467794707, 371295219, 371295219, 371295219, 371295219, 371295219 }
{"107034898",
"1435222368",
"1610706092-1697663808 1871122314 1976839809",
"1226794060 1927190387-1964483670 1987884603",
"861922579-1336337207",
"142748363",
"1546075400-1748036115 1955500686-1974232656",
"1736945528 1743643105-1864443183",
"406917722 1469388991 1674485521-1699512544",
"1345731396",
"411781688-1308033034",
"306942452",
"284066323 330387048-903698718",
"1238389562 1588857617 1598204195-1730338367",
"1222145365 1251330405 1737637452 1932383881",
"1182878989 1991733477",
"1379845270",
"97462325-1869043704",
"122785453-470030750 1388087012-1472126209",
"567959290-1062178801 1313923490",
"1604936321 1910270373",
"284954044",
"490398145 697778577-1390967710",
"762724135-1857573006",
"1355396212",
"158447965",
"57540788 579470392",
"1451893787 1887627601",
"148093489 338484798 1916176499",
"1931587615 1975565077",
"1047868305-1457264130 1678787372-1691714456",
"1431865467 1494054738 1957664580 1996432579",
"1160697241 1298672632 1515023722-1863250323",
"252737264 443527480-897862342",
"291338892",
"218849644-948481786 1299116802 1852333175",
"375015845 1183622525 1470627680-1609496410",
"1346409743 1810586929 1878299307-1995444290",
"1124773126-1783012154 1910459538-1953802626",
"1040343157-1274638734 1525460811 1580706663",
"45922830-114162556 178888101-522462530",
"1085305598-1314003765",
"1641550247",
"1182877954",
"1924495436 1928524460-1963872423 1996026506",
"87785117",
"1443095146",
"367156410-961032268"}
{"213048876 346861597-1265215573",
"1095111572",
"95233077",
"550268949 1044392523",
"450959885-1678393446 1772844450-1889281952",
"1420165907 1514317577-1938341283 1993341096",
"877538323 1167682166",
"943532736-1001933205 1471248256-1918251137",
"1372800765 1603057441-1842145371",
"1132314788 1929779652",
"702294813-1451506939",
"1556428629 1812896460-1935221730 1964342541",
"1281427157-1735021131",
"1359184198-1669113915",
"846474777 1029907910",
"1853256721",
"740095137-766015924 1244079649-1763094483",
"133352737-426664696 1514211039",
"1206931840",
"654398657 1517923766",
"347012854",
"1336563216-1643536101",
"570686880-1233701422",
"821154312-1668460811",
"407500886 993868475-1806116539"}
Returns: { 861922579, 1957664580, 1957664580, 1957664580, 1957664580, 1931587615, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117, 87785117 }
Submissions are judged against all 18 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RangeGame with a public method vector<int> bestDoors(vector<string> possible, vector<string> hints) · 18 test cases · 2 s / 256 MB per case