Help!!! Confusing and Inconceivable results when n>123!!!


  • 0
    E

    My solution is accepted when n between 1-123, when n>124,the outputs differ from the test program, and I couldn't find the mistake. So please help me solve it. I suspect if the test case has some wrong.
    This is my test inputs and outputs:
    0_1469005977423_bowenjayconan_1469004129416_53.png

    My thinking process about this question :

    I used res[] for storing the all results if inputting 1 to n
    The target is to try to find the minimum of the max between split index + res[split index - 1] and right part(including split index)
    and for a certain i (1-n) , I use j to travel from i-1 to 1 to find split index
    since we need n-1 to check whether it is n, we need n-3(n-1-2) to check whether it is bigger than n-3......
    so each step I record the sum of split indexs i-1, i-1-2, i-1-2-4,..., i-1-2-4-2^m as right part
    left part is split index + res[split index - 1]
    so with the vary of j, I could record the minimum as res[i]

    public class Solution {
        public int getMoneyAmount(int n) {
            int[] res = new int[n+1];
            for(int i=2; i<=n; i++){
                res[i] = Integer.MAX_VALUE;
                int right = 0, k=1;
                for(int j=i-k; j>0; j-=k){
                    right += j;
                    k *= 2;
                    if(j+res[j-1] > right) {
                        res[i] = Math.min(res[i], j+res[j-1]);
                    }
                    else {
                        res[i] = Math.min(res[i], right);
                    }
                }
            }
            return res[n];
        }
    }
    

    I checked the result when input is 124, it should be res[108] + 109 = 557, (and 109 = 124-15 (1+2+4+8)) in my way.
    Could you find the 555 solution according to the test case.
    What I missed?


  • 0
    Y

    @EncoreSummer
    Hi!I've been troubled by this question a lot, here is what I think might explain it.

    And Do forgive my poor English. I'm not a native speaker.

    This idea is indeed quite confusing. It confused me for quite a long time, until now I finally realizes where it goes all wrong...

    Let's write down the series according to this idea:

    123 121 117 109 93.... I'll just stop here.

    The reason why not choose 110 is simple. It's not a good idea compared with 109, since 109 is less than 110, plus the function f(n) which represents the maximum money we need for numbers from 1 - n is obviously an increasing function.

    The reason why not choose 108 is also simple, because in addition to 108, one has to choose 109 again because 109 is the 'best' number .... wait! Is this really true?

    Here is exactly where this idea goes wrong. It's actually NOT necessary to choose 108 and 109 both. Take an example. If we first choose number 101, for the latter series 102, 103, ...., 124, what's the maximum money we must pay?

    Is it 109, 117, 121, 123? No! Actually it's 117, 109, 113, 115! the maximum is 454 instead of 470 as we thought. (And this is why the answer to n = 124 is 550, 101+454 = 550. An alternative is to choose 105 as start).

    Why this happens? Because if we start from 117, the chain to 124 is too short, only contains 3 numbers, 117, 121 and 123. So instead, the 'hardest' number to reach is 116, not the largest number 124 if we follow our intuition.

    In conclusion, the problem lies here. One have to examine all the numbers as start, instead of choosing few 'best' numbers. The reason is that sometimes the chain to the largest number gets too short, in this situation, instead, some numbers in the middle of the series might become the hardest one to reach.


  • 0
    E

    @yzxyzh
    Many thanks, It's my luck to meet you!
    After your explaining, I understand my mistakes and the key way to it better.
    Thank you a lot for typing such many words for my question,
    By the way, I am not a native speaker, either.
    多谢多谢~~!!


Log in to reply
 

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