Can you think of the simplest properties that relate a number and its sum of digits?

Note that if $$$X$$$ is a multiple of 3, then both $$$X$$$ as well as the sum of digits of $$$X$$$ are a multiple of 3! Can you put this property to use here?

If $$$X$$$ is a multiple of 3, then $$$\texttt{gcd-sum}(X) \ge 3$$$. Therefore, we are guaranteed that at least every third number will satisfy the constraints required by our problem $$$(\texttt{gcd-sum}(X) > 1)$$$.

Therefore, for the input $$$n$$$, we can simply check which one of $$$n$$$, $$$n+1$$$, and $$$n+2$$$ has its gcd-sum $$$> 1$$$, and print the lowest of them.

Note that you must take long long, as input integers exceed the range of int.

Moreover, simply outputting $$$\text{ceil}((n / 3) \times 3)$$$ is incorrect as some non-multiples of three may also may have gcd-sum $$$> 1$$$, for example, 26.

~~~~~

include <bits/stdc++.h>

using namespace std;

long long int gcd_sum(long long int num) { // returns gcd-sum long long int tmp = num, digitsum = 0;

while (tmp > 0) {
    digitsum += tmp % 10;
    tmp /= 10;
}

long long int gcd = __gcd(num, digitsum);
return gcd;

}

int main(void) { int t; cin >> t;

while (t--) {
    long long int n;
    cin >> n;
    if (gcd_sum(n) != 1) {
        cout << n << endl;
    } else if (gcd_sum(n + 1) != 1) {
        cout << n + 1 << endl;
    } else if (gcd_sum(n + 2) != 1) {
        cout << n + 2 << endl;
    }
}
return 0;

}

```

There can exist multiple optimal packings for a given set of rectangles. However, all of them can always be rearranged to follow a specific pattern, based on the rectangles' sizes.

Can you show that it is always possible to replace a set of consecutive small blocks with a single large block? (of same or larger size)

We follow a greedy strategy:

1. Initialize height of box as 1.
2. Initialize current layer size as $$$W$$$.
3. Pick the largest available rectangle that can fit into the current layer, and place it there. Repeat until this layer cannot fit any more rectangles.
4. If more rectangles remain, increment height by 1 and now repeat the last three steps. Else, output the current value of height.

First count sort the given rectangles based on their widths. There can only be 20 distinct rectangle widths in the range $$$[1, 10^9]$$$, so the following works:

counts = [0 for w in range(0, 20)]
for w in widths:
    counts[log2(w)] += 1

The solution can be implemented by iterating $$$N$$$ times.

At each iteration, step through the counts array and take the largest available rectangle that can fit into the current space. If no rectangle was able to fit, increment height by 1 and reset box width to $$$W$$$.

This has complexity $$$\mathcal{O}(n\log(w_\text{max}))$$$.

It is also possible to implement the solution with a multiset and upper_bound, for a complexity of $$$\mathcal{O}(n\log(n))$$$.

Store all rectangle sizes in a multiset. At each iteration, find using upper_bound the largest rectangle that can fit into the current space we have, and fit it in. If no rectangle can fit in this space, reset the space to maximum, increment height, and repeat.

It is always possible to replace several smaller blocks with a single larger block if it is available. Because all blocks are powers of two, it must so happen that smaller powers of two will sum to a larger power. Therefore, we can always place a larger block first if it can be placed there.

This elaborate proof isn't actually required for solving the problem. The intuition in the brief proof is sufficient for solving the problem. This proof is for correctness purpose only.

Let's first note a property: if $$$a_1 + \ldots + a_n>a_0$$$, then there exists some $$$i$$$ such that $$$a_1+ \ldots +a_i=a_0$$$, when all $$$a_i$$$ are powers of 2 AND $$$a_1$$$ to $$$a_n$$$ is a non-increasing sequence (AND $$$a_1 <= a_0$$$, of course). Why is this so? You can take an example and observe this intuitively, this is a common property of powers of two. For example, $$$4+2+2+1+1>8$$$, but $$$4+2+2$$$ (prefix) $$$=8$$$. Formally: if $$$a_1 =a_0$$$, this property is trivially true. If $$$a_1 < a_0$$$, we can splilt $$$a_0=2^ka_1$$$ for some $$$k$$$ into $$$2^k$$$ parts and — by strong induction — claim this property holds.

Let us now compare some optimal solution and our greedy solution. Before comparing, we first sort all blocks in each layer of the optimal solution in decreasing order. This does not affect the final answer but helps in our comparison. This comparison goes from bottom to top, left to right. Let us look at the first point of difference: when the block placed by us ($$$B_G$$$) is different from the block placed by the optimal solution ($$$B_O$$$). There are three cases.

If $$$B_O > B_G$$$: this is impossible, as in our greedy solution, we are always placing the largest possible block. We wouldn't place $$$B_G$$$ in there if $$$B_O$$$ was also possible. If $$$B_O == B_G$$$: we have nothing to worry about (this isn't a point of difference)

If $$$B_O < B_G$$$: let us assume that the optimal solution places several consecutive small blocks, and not just one $$$B_O$$$. Since the blocks are in decreasing order, none of them would be bigger than $$$B_G$$$. Note that either all of these blocks will sum to less than $$$B_G$$$ or a prefix of them will be exactly equal to $$$B_G$$$. In either case, we can swap them with one single large block $$$B_G$$$ (swapping with a $$$B_G$$$ which was placed in some higher layer in the optimal solution)

Hence, in the last case, we have shown that any optimal solution (an arrangement of blocks) can be rearranged such that each layer fits the largest possible block first. This is also what is done in our greedy strategy. Therefore, with this proof by rearrangement, we conclude that our greedy strategy gives the same minimum height as that of the optimal answer.

As we understood in the proof, this solution only works when it's guaranteed that smaller blocks will always exactly sum to any larger block. Therefore, if the blocks are not powers of two, this guarantee does not hold.

The following counterexample suffices:

6 13
6 6 4 4 3 3

As you can see here the smaller blocks are not guaranteed to sum to the larger block (no prefix of $$$4,3,3$$$ sums to $$$6$$$). Our greedy solution gives minimum height 3, but best possible minimum height is $$$2$$$ (first layer: $$$6,4,3$$$, second layer: $$$6,4,3$$$)

~~~~~

include

include

include

using namespace std;

int main() { int t; cin >> t;

while (t--) {
    int n, box_width, w;
    cin >> n >> box_width;

    vector<int> counts(20);
    for (int i = 0; i < n; i++) {
        cin >> w;
        counts[log2(w)]++;
    }

    int height = 1, space_left = box_width;

    for (int iter = 0; iter < n; iter++) {
        int largest = -1;

        for (int size = 19; size >= 0; size--) {
            if (counts[size] and (1 << size) <= space_left) {
                largest = size;
                break;
            }
        }

        if (largest == -1) {
            space_left = box_width;
            height++;
            for (int size = 19; size >= 0; size--) {
                if (counts[size] and (1 << size) <= space_left) {
                    largest = size;
                    break;
                }
            }
        }

        counts[largest] -= 1;
        space_left -= 1 << largest;
    }

    cout << height << endl;
}

}

```

from math import log2

def solve_tc():
n, w = list(map(int, input().split()))
widths = list(map(int, input().split()))

    counts = [0 for _ in range(20)]

    for width in widths:
        counts[int(log2(width))] += 1

    space = w
    height = 1

    for it in range(n):
        largest = -1

        for size, count_width in list(enumerate(counts))[::-1]:
            if counts[size] > 0 and (2 ** size) <= space:
                largest = size
                break

        if largest == -1:
            space = w
            height += 1

            for size, count_width in list(enumerate(counts))[::-1]:
                if counts[size] > 0 and (2 ** size) <= space:
                    largest = size
                    break

        assert(largest != -1)
        counts[largest] -= 1
        space -= 2 ** largest

    print(height)

t = int(input())

while t > 0:
t -= 1

    solve_tc()

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin >> t;

    while (t--) {
        int n, w;
        int box_width;
        cin >> n >> box_width;

        multiset<int> st;
        for (int i = 0; i < n; i++) {
            cin >> w;
            st.insert(w);
        }

        int height = 1, space_left = box_width;

        while (!st.empty()) {
            auto it = st.upper_bound(space_left);
            if (it != st.begin()) {
                it--;
                int val = *it;
                space_left -= val;
                st.erase(it);
            } else {
                space_left = box_width;
                height++;
            }
        }

        cout << height << endl;
    }
    return 0;

}

We have a brute force $$$\mathcal{O}(N\cdot M^2)$$$ solution.

At every timestep $$$t$$$, for each banana $$$b_i$$$ that has already been reached previously, apply this timestep's operation $$$y_t$$$ times on $$$b_i$$$. For all the $$$y_t$$$ bananas reachable from $$$b_i$$$, update their minimum reachability time if they hadn't been reached previously.

Why is this correct? Simply because we are simulating each possible step of the algorithm exactly as it is described. Therefore, we cannot get an answer that's better or worse than that of the optimal solution.

Observe if we can reduce our search space when we visit nodes that have already been visited previously.

Let us take an example. We have some timestep $$$t,x,y = 1,5,10$$$. If we start visiting from $$$k=10$$$, we will visit $$$k=15,20,\ldots,55,60$$$. Let us say that $$$k=40$$$ was an already visited state. Do we now need to continue visiting $$$k=45,\ldots,60$$$ or can we stop our search here?

We can actually stop our search as soon as we reach a previouly visited node! Why is this so? This is because — within the same iteration — that already visited node will once again start its own search, and will hit all the points that we were going to hit, and some more!

For example, let us say we would reach points $$$a, a\cdot x, a\cdot x^2, \ldots, a\cdot x^{y-1}$$$. Now, assume that $$$a\cdot x^5$$$ had been previously reached, then it is better to stop at $$$a\cdot x^5$$$, as this node itself will reach $$$a\cdot x^5, a\cdot x^6, \ldots, a\cdot x^{y-2}, a\cdot x^{y-1},a\cdot x^{y}, \ldots, a\cdot x^{5+y-1}$$$. Note the latter range includes as a prefix the entire remaining suffix of the former range! Therefore, in this approach, nodes that would have been visited, will eventually be visited, and get assigned the minimum timestamp.

We can implement the optimized solution by simply adding an extra if already_visited[k]: break to our inner loop. Yup, really, that's all it takes to solve this question!

Complexity analysis: We can show that each node is visited at most twice: an unvisited node is reached atmost once, whereas a visited node is reached atmost twice (once during the main loop and once when searching from the immediately previous visited node) There are $$$N$$$ iterations, and in each iteration, each of the $$$M$$$ nodes is visited at most twice. Therefore, the total complexity is $$$\mathcal{O}(2NM)$$$.

1. Integer overflows: $$$x'$$$ does not fit in integer range
2. Out of bounds access: simulating the $$$y_t$$$ steps of the algorithm even when $$$k$$$ exceeds $$$M$$$ prematurely