We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Credits:
Special thanks to @agave and @StefanPochmann for adding this problem and creating all test cases.
Given a number , we have to find the worst case cost of guessing a number chosen from the range , assuming that the guesses are made intelligently(minimize the total cost). The cost is incremented by for every wrong guess .
For example:
n=5 1 2 3 4 5
If we start with 3 as the initial guess, the next guess would certainly be 4 as in the worst case required number is 5. Total Cost .
But if we start with 4 as the initial guess, our next guess would be 2 as in the worst case required number is 3 or 1. Total Cost which is the minimum cost.
n=8 1 2 3 4 5 6 7 8
In this case we have to guess 5 followed by 7. Total Cost . If we choose 4 as our intial guess. Total Cost .
Firstly, we need to be aware of the fact that out of the range , we have to guess the numbers intelligently in order to minimize the cost. But, along with that we have to take into account the worst case scenario possible, that is we have to assume that the original number chosen is such that it will try to maximize the overall cost.
In Brute Force, we can pick up any number in the range . Assuming it is a wrong guess(worst case scenario), we have to minimize the cost of reaching the required number. Now, the required number could be lying either to the right or left of the number picked(). But to cover the possibility of the worst case number chosen, we need to take the maximum cost out of the cost of reaching the worst number out of the right and left segments of . Thus, if we pick up as the pivot, the overall minimum cost for the worst required number will be:
For every segment, we can further choose another pivot and repeat the same process for calculating the minimum cost.
By using the above procedure, we found out the cost of reaching the required number starting with as the pivot. In the same way, we iterate over all the numbers in the range , choosing them as the pivot, calculating the cost of every pivot chosen and thus, we can find the minimum cost out of those.
Complexity Analysis
Algorithm
In Brute Force, for numbers in the range , we picked up every number from to as the pivot and found the maximum cost out of its left and right segments. But an important point to observe is that if we choose any number from the range as the pivot, the right segment(consisting of numbers larger than the picked up pivot) will be longer than the left segment(consisting of numbers smaller than it). Thus, we will always get the maximum cost from its right segment and it will be larger than the minimum cost achievable by choosing some other pivot. Therefore, our objective here is to reduce the larger cost which is coming from the right segment. Thus, it is wise to choose the pivot from the range . In this way the costs of the two segments will be nearer to each other and this will minimize the overall cost.
Thus, while choosing the pivot instead of iterating from to , we iterate from to and find the minimum achievable cost similar to brute force.
Complexity Analysis
Algorithm
The problem of finding the minimum cost of reaching the destination number choosing as a pivot can be divided into the subproblem of finding the maximum out of the minimum costs of its left and right segments as explained above. For each segment, we can continue the process leading to smaller and smaller subproblems. This leads us to the conclusion that we can use DP for this problem.
We need to use a matrix, where refers to the minimum cost of finding the worst number given only the numbers in the range . Now, we need to know how to fill in the entries of this . If we are given only a single number , no matter what the number is the cost of finding that number is always 0 since we always hit the number directly without any wrong guess. Thus, firstly, we fill in all the entries of the which correspond to segments of length 1 i.e. all entries are initialized to 0. Then, in order to find the entries for segments of length 2, we need all the entries for segments of length 1. Thus, in general, to fill in the entries corresponding to segments of length , we need all the entries of length and below to be already filled. Thus, we need to fill the entries in the order of their segment lengths. Thus, we fill the entries of diagonally.
Now, what criteria do we need to fill up the matrix? For any entry , given the current segment length of interest is i.e. if , we assume as if we are available only with the numbers in the range . To fill in its current entry, we follow the same process as Approach 1, choosing every number as the pivot and finding the minimum cost as:
But, we have an advantage in terms of calculating the cost here, since we already know the costs for the segments of length smaller than from . Thus, the dp equation becomes:
where indicates the minimum obtained by considering every number in the range as the pivot.
The following animation will make the process more clear for n=5: !?!../Documents/375_Guess.json:791,552!?!
Complexity Analysis
Time complexity : . We traverse the complete matrix once . For every entry we take atmost numbers as pivot.
Space complexity : . matrix of size is used.
Algorithm
In the last approach, we chose every possible pivot from the range . But, as per the argument given in Approach 2, we can choose pivots only from the range , where is the current segment length of interest. Thus the governing equation is:
Thus, we can optimize the Approach 3 to some extent.
Complexity Analysis
Time complexity : . We traverse the complete matrix once . For every entry we take at most numbers as pivot.
Space complexity : . matrix of size is used.
Analysis written by: @vinod23