Improve the Question and Example


  • 64
    G

    Can you guys define the problem a little more and improve the test case.

    The example provided for n=10 does not actually give the solution to the problem (it shows 21 as the result of the provided guessing pattern); however, if you run a custom testcase the leetcode server say the answer is 16. Can you explain how we arrive at 16. If the number is 8 and we choose 5 7 9, we pay $21. How does one do better than that?

    Additionally, the question states: Given a particular n ≥ 1, find out how much money you need to have to guarantee a win. Well, this wording is ambiguous, as I should be able to always return n(n+1)/2 to give the sum of all numbers from 1 to n. That would certainly guarantee a win, right? I think you are looking for the minimum amount of money you need to guarantee a win. If so, can you specify that and improve the example to reflect it (and show how the answer 16 is achieved).


  • 1
    T

    I agree with you ==


  • 1
    O

    Totally agree. I did n = 6 by hand and I got 9, while the answer says 8 for some reason, and after that it detracts even more. Clarity please! :(


  • 0
    H

    @oneraynyday 1,2,3,4,5,6 choose 3 first and 5 next


  • 3
    A

    n=10
    choose 7 first,
    then choose 9 if 7 is smaller (got 16)
    or if 7 is larger, choose 4 then choose 5 if 4 is smaller (got 16) or choose 2 is 4 is larger (got 13)


  • 0
    N

    @Amigua said in Improve the Question and Example:

    n=10
    choose 7 first,
    then choose 9 if 7 is smaller (got 16)
    or if 7 is larger, choose 4 then choose 5 if 4 is smaller (got 16) or choose 2 is 4 is larger (got 13)

    Yes. Pick 7 first. If it tells you it's higher, then pick 9.
    If it's wrong again, you don't need to pay more to guess the correct number.
    If it tells you it's lower when you pick 7, I don't agree with the picks of your left part, from 1 to 6.
    You can then pick 3 and ( 5 or 1) to guarantee a win, which you need to pay $8 at most.
    But overall, 8 is smaller than the right part, 9.
    So the answer for n = 10 is 7 + 9 = 16.


  • 34

    @nlackx nice demo, and what you are showing is a best strategy to guess the number with lowest cost.,So i guess what @grodrigues3 is saying is that the example as shown in the problem description is very confusing because it does not suppose to be in the description at all since it IS NOT A BEST STRATEGY WAY to guess the number at lowest cost.

    The example description should be:

    first introducebest strategyto guess:

    1. for one number, like 1, best strategy is 0$
    2. for two number, like 3,4, best strategy is 3$, which can be understood in this way: you have two way to guess: a) start by guess 4 is the target, (the worst case is) if wrong, you get charged $4, then immediately you know 3 is the target number, get get charged $0 by guessing that, and finally you get charged $4. b) similarly, if you start by 3, (the worst case is) if wrong, you get charged $3, then you immediately know that 4 is the target number, and get charged $0 for guessing this, and finally you get charged $3. In summary:
      range ---------> best strategy cost
      3, 4 ---------> $3
      5, 6 ---------> $5
      ...
    3. for three number, the best strategy is guess the middle number first, and (worst case is) if wrong, you get charged that middle number money, and then you immediately know what target number is by using "lower" or "higher" response, so in summary:
      range ---------> best strategy cost
      3, 4, 5 ---------> $4
      7, 8, 9 ---------> $8
      ...
    4. "for more numbers", it can simply be reduced them into smaller ranges, and here is why DP solution make more sense in solving this.
      suppose the range is [start, end]
      the strategy here is to iterate through all number possible and select it as the starting point, say for any k between start and end, the worst cost for this is: k+DP( start, k-1 ) + DP(k+1, end ), and the goal is minimize the cost, so you need the minimum one among all those k between start and end

  • 3
    A

    @realdonaldtrump said in Improve the Question and Example:

    the worst cost for this is: k+DP( start, k-1 ) + DP(k+1, end ), and the goal is minimize the cost, so you need the minimum one among all those k between start and end

    The worst cost should be: cost = k+ max( DP(start,k-1) + DP(k+1, end) ) and you have to minimize cost for each k in [start,end]. The reason you need a max there is that you either have to go left or you have to go right, so you don't need to sum the cost of both sides but just add the side which is larger.
    Most probably, you just missed the max while typing.


  • 0
    B

    @realdonaldtrump This explanation is perfect and probably better than most of real world interviewee explanations.


  • 0
    P

    @realdonaldtrump for all k in [i, j], get min(k + max(DP(start, k - 1), DP(k + 1, end)))


  • 3
    S

    I am also very angry.


  • 0
    Z

    @realdonaldtrump Well done, Trump!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.