PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Sorting, greedy
PROBLEM:
There are N types of roses, you have A_i of the i-th type.
Find the maximum number of them you can plant in a row of M pots such that:
- Adjacent pots do not contain the same color of rose; and
- At most K consecutive pots can contain a rose.
EXPLANATION:
The constraints on planting roses essentially say that we can plant several contiguous blocks of roses such that:
- Each block has length \le K
- All roses within the block have the same color; and
- Any two blocks are separated by at least one empty pot.
The key observation here is that it’s always optimal to make blocks of roses as large as possible.
Why?
To see why, suppose we have two blocks of roses, say of sizes x and y where x \le y \lt K.
We look at two cases.First, suppose these two blocks have the same color of rose.
Then, we can remove one rose from the x-block and add one rose to the y-block instead; while moving all roses between these two blocks towards the x-block to make space.
This makes the block sizes (x-1, y+1) instead. Repeat this over and over again till either x becomes 0 (so the block disappears), or y becomes K and cannot increase.Note that this also proves the following: for any fixed color, in an optimal configuration there will be at most one block having size \lt K.
Next, suppose x and y are block sizes with different color roses.
If there’s at least one unused rose from the larger block, we can do the same (x-1, y+1) transformation and increase the size of the larger block.If there are no unused roses from the larger block, then because y \lt K and we saw that there can be at most one non-K-sized block of any color, we must have in fact used all roses of this color.
This tracks with our claim that the blocks must be of maximal size.
We can now simply ignore all roses of the fully-used color, and repeatedly apply the above argument to only the other blocks.
This tells us that the optimal strategy is as follows:
- Use blocks of K roses as long as we can.
- When this is no longer possible, use blocks of \lt K.
There is at most one such block for each color; so we can find these blocks and then use them in descending order.
Now, for each i, there are \left\lfloor \frac{A_i}{K} \right\rfloor blocks of size K it can form, and the leftover block will have size A_i \bmod K.
Let S = \sum_i \left\lfloor \frac{A_i}{K} \right\rfloor denote the total number of size-K blocks available to us.
Note that each size K block (except the last one) requires an extra space after it for separation, so that’s actually K+1 spaces in total for K flowers.
So, if we want to use X blocks of size K, we need X \cdot (K+1) - 1 space in total in total, for a benefit of X\cdot K flowers.
We want the largest X \le S that satisfies this; which can be found in \mathcal{O}(\log S) by binary searching for it or in constant time by doing some math - either approach is fast enough.
Then, if all S blocks of size K have been used, simply simulate the remainder by taking as many of the A_i \bmod K values in descending order as possible - again, while remaining to keep an empty space between blocks.
TIME COMPLEXITY:
\mathcal{O}(N \log N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n, m, k; cin >> n >> m >> k;
k++;
vector <int> a(n);
for (auto &x : a) cin >> x;
if (k == 1){
cout << 0 << "\n";
return;
}
int full = 0;
for (auto &x : a){
full += x / (k - 1);
x %= (k - 1);
}
// all full should be placed
// maybe some extra
sort(a.begin(), a.end(), greater<int>());
vector <int> ps(n + 1);
for (int i = 1; i <= n; i++){
ps[i] = ps[i - 1] + a[i - 1];
}
int ans = 0;
int max_allow = m - (m / k);
if (full * (k - 1) >= max_allow) ans = max_allow;
for (int i = 0; i <= n; i++){
int tot = ps[i] + full * (k - 1);
int loss = full + i - 1;
int got = min(tot, m - loss);
ans = max(ans, got);
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}