Sort by

recency

|

160 Discussions

|

  • + 0 comments

    Hi. I am questioning the test cases. E.g. # 13, 1st input: 999999995000050000 10000000000000 100000 the output should be -1, but the expected output in the test is 9999999900001 9999999900002 9999999900003 9999999900004.

    I do not understand why.

    P.S: If I test my code with the custom input 999999995000050000 10000000000000 100000, I am receiveing the correct answer -1, the test passes.

  • + 0 comments

    python3: pure math solution

    def bonetrousle(n, k, b):
        """Find b distinct integers in [0,...,k] that sum to n."""
        
        # Define these convenient variables:
        N = n - b*(b+1)//2
        d = k - b
        
        # For a solution to exist, n must lie between the sum of first b boxes and the last b boxes
        if (N < 0) or (N > b*d):
            return [-1]
        elif N == 0:  # edge case when d==0
            return [*range(1, b+1)]
        else:
            # Imagine starting with first b boxes. While keeping the sum below n, replace b->k, (b-1)->(k-1), .... Each shift adds d to the total. Finally add the missing balance to the "next" (b-i) term. (i.e. the largest value in [1,2,..b] that didn't get shifted.)
            q, r = N//d, N % d
            # Take care of edge case with b-q+r==0 
            mid = [] if (b == q-r) else [b-q+r]
            return [*range(1, b-q)] + mid + [*range(k, k-q, -1)]
    
  • + 0 comments

    Single-pass (O(b)) without constructing an array

    Overview

    First calulate the min and max achievable with given k and b (ie. what's the min and max given how many boxes we will use and how many boxes the store carries). Check if we are able to achieve the sum at all, otherwise return -1.

    Next up calculate how many sticks we can add to each box (our quotient) and how many sticks we will need to distribute after that (our remainder). Then we simply shift our number series according to our quotient, and distribute the remainder.

    Example: buy 10 strains using 3 boxes, store carries 5 boxes. Start out with the series 1 + 2 + 3, sum is 6. We calculate our quotient 1 and remainder 1. This means we can shift our series by one and get 2 + 3 + 4, sum is 9. Find a way to distribute our 1 remainder: 2 + 3 + 5 = 10. Done.

    C++ quirks and overflows

    Had some issues with overflow even after plastering uint64_t all over the place, turns out my formula for max was laid out in such a way that one intermediate result produced an overflow, this was solved by shamelessy stealing the formula from another solution on here and having ChatGPT explain why that one works compared to my initial formula...

    To avoid creating an array I just pass the out stream to the function and write directly to that.


    void bonetrousle(uint64_t n, uint64_t k, uint64_t b,ostream& fout) {
        uint64_t min = (b * (1 + b)) / 2;
        // uint64_t max = (b * ((k - b + 1) + k)) / 2; <-- This overflows, use a different formula to reduce the size of intermediate results...
        uint64_t max = k * b - b * (b - 1) / 2; // Doesn't overflow.
        
        if(min > n || max < n) {
            fout << "-1" << endl;
            return;
        }
        
        // We can add this many sticks to each box (quotient).
        int64_t q = (n - min) / b;
        // These additional sticks can be distributed after that (remainder).
        uint64_t r = (n - min) % b;
        
        for(int64_t i = 1; i <= b; ++i) {
            // Our number in sequence order, offset by our quotient.
            int64_t num = i + q;
            
            // Replacing num would add our missing remainder to the sum and thus complete it.
            if (r > 0 && (b + q + 1) - num == r) {
            // Example: b is 4, q is 0, and r is 2 which means our sequence is 1 2 3 4.
            // We have to find a way to increase the sum by 2, from 10 to 12.
            // b + q will always be the highest numbers in the sequence, in this case 4,
            // and we simply add 1 (b + q + 1) to get the next number in our sequence (5): this is the number we want to replace some num with so that we increase our total by r.
            // 5 = num - 2, so in this case we would replace 3 and end up with the sequence 1 2 5 4 which has a sum of 12!
                fout << b + 1 + q;
            } else {
                fout << num;
            }
            
            if(i < b) {
                fout << " ";
            }
        }
        
        fout << endl;
    }
    
  • + 0 comments

    Determine the highest and lowest possible sums using the provided value 'k'. Compare these sums with 'b' to ascertain if the sum 'n' is achievable using the given 'b' value. Next, calculate the required value by subtracting the minimum value from 'n', and then distribute it equally among all the values in the result array. Afterwards, distribute the remainder equally in the result array from the last position to prevent any overlap. Finally, this result array is the definitive solution.

    def bonetrousle(n, k, b):
        mini=maxi=0
        res=[0]*b
        temp=1
        while temp<=b:
            mini+=temp
            maxi+=k-temp+1
            temp+=1
        if n>=mini and n<=maxi:
            q=(n-mini)//b
            r=(n-mini)%b
            for i in range(b):
                res[i]+=(q+i+1)
            for i in range(1,r+1):
                res[-i]+=1
            return res
        else:
            return [-1]
    
  • + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank Bonetrousle Problem Solution