sticks

Exercise

Difficulty : Hard

Statement

There are $N$ columns. At the top of each column, there is a magic bag containing sticks. The bag at the $i$-th column can generate a stick of size $A_i$.

You - as a newbie wizard - can generate at most $K$ sticks in total. You can choose which bag to use, when a stick is generated, it is placed in its corresponding column.

The size of a column is the sum of every sticks in it. For example, if $A_i = 3$ and you generate 2 sticks, then the size of the $i$-th column is $2 \times 3 = 6$.

The score is the minimum size of each column. Your goal is to find the maximum possible score after at most $K$ stick generation.

Example

$A = [3, 5, 6]$
$K = 5$

You can generate 2 sticks in the first column and the second one and then one stick in the last column.

Bags	3	5	6
	X	X	X
	X	X
Total size	6	10	6

Hence, the score is $min(6, 10, 6) = 6$. It is possible to prove that this score is maximum.

Constraints

$1 \le N \le 10^5$
$1 \le A_i \le 100$
$1 \le K \le 10^7$

It can be shown that the maximum score won’t exceed $2 \times 10^9$.

Complexity

Time : $O(N \log(\max_i(A_i) \times K))$

Solution

Intuition

To maximize the score, we can try every possible value.

Using the provided example, we obtain this array after $K = 5$ stick generation :

Score	0	1	2	3	4	5	6	7	8	9	…
Can be obtained / exceeded ?	1	1	1	1	1	1	1	0	0	0	0

As the maximum score is 6, every score <= 6 is possible to obtain / exceed and scores > 6 are impossible to obtain.

In a binary search point of view, we can find the last 1 in logarithm time complexity.

Editorial

Let’s divide this problem into two problems.

First of all, we will make the binary search and then we will create a function to query whether or not it is possible to obtain or exceed a score given $K$ generations.

Binary search

We have to find search boundaries in first place. We can see that it is always possible to have a score of 0. Moreover, the maximum possible score is obtained by generating $K$ sticks of maximal size.

The initial interval is then $[0, max_i(A_i) \times K]$.

It is a simple lower bound algorithm, the condition to minimize the interval is whether or not it is possible to obtain / exceed the score (which is the the middle of the interval).

mid = $\frac {l + r} 2$
If possible(mid, k) then interval = $[mid + 1, r]$
Otherwise, interval = $[l, mid - 1]$

Note that when we reach step 2., we can set the maximum possible score to mid since it is possible to obtain this score.

Query

The query function must have a linear time ($O(N)$) for the target complexity, thus it is not possible to simulate the process every time.

The goal of this function is to return whether or not it is possible to achieve the score given as argument using maximum $K$ generations.

For every column, it is possible to deduce the minimum number of generations to achieve this score in constant time, let’s call $G_i$ the minimum number of generations for the column $A_i$.

$G_i$ = $\lceil \frac {score} {A_i} \rceil$

$\lceil x \rceil$ is the next integer value of $x$ (ceil function)

We can see this computation as “find the first integer $x$ where $x \times A_i \ge score$”. If the score is divisible by $A_i$ ($x \times A_i = score$) then $x = \frac {score} {A_i}$, otherwise we take the next integer since $x \times A_i$ needs to exceed $score$ using the ceil function.

If the sum of all $G_i$ values is less or equal than $K$, then it is possible to obtain / exceed the score in every column, such that the minimum of these values is greater or equal to the target score.

Code

// Returns whether or not it is possible to make this score with at least k
// generations
bool score_possible(const vector<int> &columns, int k, int score) {
    int gens = 0;
    for (auto col : columns) {
        // We have to generate ceil(score / col) sticks of this size
        // such that the total size is greater or equal to the score
        int required_gens = (score - 1) / col + 1;
        gens += required_gens;
    }

    // Possible if we used K or less than K generations to achieve this score
    return gens <= k;
}

int max_sticks_score(const vector<int> &columns, int k) {
    // It is not possible to have a score greater than this value using
    // k generations
    int max_score = *max_element(columns.begin(), columns.end()) * k;

    // Always possible to do a score of 0
    int last_possible = 0;
    int l = 0;
    int r = max_score + 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        // Is it possible to have a score >= mid using K generations ?
        if (score_possible(columns, k, mid)) {
            last_possible = mid;
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    return last_possible;
}

Full code