We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. Bonetrousle
  5. Discussions

Bonetrousle

  • kristoffer_nord2
     + 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;
}