Problem Statement |
| | Often, to determine who gets some sort of prize, one person picks a number in some range, and a group of other people try to guess a number as close to the picked number as possible. After everyone has guessed, the person who guessed the number closest to the picked number wins. While it is impossible to totally eliminate ties, to help avoid them, a person cannot guess a number that has already been guessed. For example, if there are 3 people, and the picked number is between 1 and 10, inclusive, the first person might guess 6. The second person could then guess any number but 6, so say he or she guesses 3. The third person might then guess 5. Now, if the picked number turned out to be 8, the person who guessed 6 would win, since he or she is closest.
In this problem a number has been chosen uniformly, at random between 1 and range, inclusive. A number of people have already guessed some numbers, and those numbers are given as elements of guesses. It is now your turn, and there are numLeft people left after you. Your task is to guess a number such that, if everyone after you follows the best strategy possible (guesses the number that maximizes his or her chance of winning), your chance of winning after everyone has guessed is maximized. Furthermore, if there is more than one way to achieve the best chance of winning, you should pick the lowest number, and assume that everyone after you does the same.
For example, if range = 1000, guesses = {500}, and numLeft = 1, you should pick 501. This gives the person after you 2 ways to win with a probability of 499/1000. He or she can pick either 499 or 502. You can assume that he or she will pick the lower of these, 499. This gives you a 500/1000 = 50% chance winning. Picking any other number would cause you to do worse. Note that a tie does not count as a win, and we are only concerned with maximizing the chance of winning. |
| |
Definition |
| | | Class: | NumberGuessing | | Method: | bestGuess | | Parameters: | int, int[], int | | Returns: | int | | Method signature: | int bestGuess(int range, int[] guesses, int numLeft) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Assume the people ahead of you, when looking for the best guess, will employ the same strategy as you are using. Namely, they will assume everyone ahead of them is employing the best strategy, and choose accordingly to maximize the probability of winning. |
| |
Constraints |
| - | range will be between 1 and 1,000,000, inclusive. |
| - | guesses will contain between 0 and 10 elements, inclusive. |
| - | Each element of guesses will be between 1 and range, inclusive. |
| - | Each element of guesses will be distinct. |
| - | numLeft will be between 0 and 6, inclusive. |
| - | range^numLeft (where '^' denotes exponentiation) will be less than or equal to 1,000,000. |
| - | range will be at least 1 + numLeft + the number of elements in guesses. |
| |
Examples |
| 0) | |
| | |
| 1) | |
| | |
| 2) | |
| | | Returns: 750 | | Your first intuition might be that you should guess 500 in this case, since that is right in the middle. However, lets consider what would happen if you were to guess 500. The person after you would guess 501 to maximize his or her chance of winning, and the last person would then pick 499, to maximize his or her chance of winning. This leaves you winning only if the number that was originally picked is exactly 500, at a probability of 1/1000. It turns out that your probability is maximized if you guess 750. The next person then guesses 250, and the last person guesses 251. |
|
|
| 3) | |
| | |