Connection Status:
Competition Arena > EllysBulls

EllysBulls

SRM 572 · 2012-12-13 · by espr1t

SRM 572 · 2012-12-13 · by espr1t · Brute Force, Encryption/Compression
Class Name: EllysBulls
Return Type: String
Method Name: getNumber
Arg Types: (vector<string>, vector<int>)
Problem Statement

Problem Statement

Elly and Kristina play a game called "Bulls". Initially each of them thinks of a non-negative integer with K digits, possibly containing leading zeroes. Then they take alternating turns, trying to guess the opponent's number. After each guess, the other person says how many positions were guessed correctly. For example if Kristina's number was "1337" and Elly's guess was "1738", Kristina should answer 2, since the digits at positions 0 and 2 (zero-based indices from the left) are correct. A guessed position is called "bull's hit", or simply a "bull", thus the name of the game.

Elly has already made several guesses. She wonders if the information she has is enough to uniquely determine Kristina's number.

You are given the guesses so far in a String[] guesses and the corresponding number of bull's hits in int[] bulls. If a unique number satisfies the given information, return it as a String. If there is more than one number that is valid according to the current guesses, return "Ambiguity" (quotes for clarity only). If no number satisfies the given information, then Kristina has lied and you should return "Liar" instead.

Notes

  • The game "Bulls" is a simplification of a game played in Bulgaria, called "Kravi & Bikove" ("Cows & Bulls").

Constraints

  • guesses will contain between 1 and 50 elements, inclusive.
  • Each element of guesses will contain between 2 and 9 characters, inclusive.
  • All elements of guesses will contain the same number of characters.
  • All elements of guesses will consist only of digits ('0'-'9').
  • bulls will contain the same number of elements as guesses.
  • Each element of bulls will be between 0 and K-1, inclusive, where K is the length of each element of guesses.
Examples
0)
{"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"}
{2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0}
Returns: "1337"

From {1234->2, 2222->0, 4444->0} it follows that the number is {1?3?}. The additional information {4321->1} tells us that either the digit at position 1 (0-indexed) is 3, or that the one at position 3 is 1. However, since {1111->1} and we already know that the 0-th digit is 1, then the third digit cannot be 1. Now we know that the number is {133?}. When trying {7777->1} we see that Kristina's number contains a 7, which cannot be anywhere else except in the last position. Thus, her number is 1337.

1)
{"0000", "1111", "2222"}
{2, 2, 2}
Returns: "Liar"

There are supposed to be two 0s, two 1s and two 2s in a four-digit number. Thus, Kristina is clearly a liar.

2)
{"666666", "666677", "777777", "999999"}
{2, 3, 1, 0}
Returns: "Ambiguity"

Some of the possible configurations that satisfy the current results are the numbers 636172, 336617, 660007. Thus, the answer is ambiguous.

3)
{"000", "987", "654", "321", "100", "010"}
{2, 1, 0, 0, 1, 1}
Returns: "007"

The guesses, as well as the answer, can have leading zeroes.

4)
{"28", "92", "70", "30", "67", "63", "06", "65",
 "11", "06", "88", "48", "09", "65", "48", "08"}
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Returns: "54"
203)
{"121212121", "343434343", "565656565", "787878787", "909090909", "000000000", "111111111", "222222222", "333333333", "444444444", "666666666", "777777777", "888888888", "999999999", "100000001", "920000000", "083000000", "007400000", "000606000", "000004700", "000000380", "000000029", "000006001", "000000081", "020600000", "100000020", "003000001", "003000020", "000000720", "000006020", "000600009", "100000300", "900006000", "000000380", "000006001", "007006000", "107000000", "100000300", "080000009", "000600080", "003000300", "003600000", "007000700", "000400020", "083000000", "080006000", "000600700", "007000080", "000400020", "003054300"}
{2, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2}
Returns: "123456789"

Against Makoto's smart backtrack.

Submissions are judged against all 254 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EllysBulls with a public method string getNumber(vector<string> guesses, vector<int> bulls) · 254 test cases · 2 s / 256 MB per case

Submitting as anonymous