WIPL - Editorial
PROBLEM LINK:
Practice
Div-2 Contest
Div-3 Contest
Author & Editorialist: Shivam Singh
Tester: Radoslav Dimitrov
DIFFICULTY:
Easy
PREREQUISITES:
DP, Knapsack
PROBLEM:
Given N boxes of each of some height, you need to combine them to form 2 towers such that the height of each towers is at least K.
QUICK EXPLANATION:
The problem can be solved using knapsack.
- Sort all the boxes in non-decreasing order.
- Run a knapsack of the form dp[i][S]: minimum height greater than equal to S that can be made using only the last i boxes.
- Define suf[i] as the sum of last i boxes.
- 2 towers can be made using the last i boxes if suf[i] - dp[i][K] \geq K.
- Find the max i for which the above condition is true, the answer(if it exists) will be n-i.
EXPLANATION:
Subtask 1
Knowledge of knapsack is not required for the first subtask. Create a dp array where dp[i][j][k] : the minimum number of boxes required to build two towers of height exactly i and j respectively, if we can only use the first k boxes. The recurrence relation for each height[i] will be :
dp[0][0][0] = 0;
int ans = INF;
// height is sorted in non-increasing order
for(int idx = 1; idx <= n; idx++){
for(int i = MAX; i >= 0; i--)
for(int j = MAX; j >= 0; j--){
if(i >= height[idx-1])
dp[i][j][idx] = min(dp[i][j][idx], dp[i - height[idx-1]][j][idx-1] + 1);
if(j >= height[idx-1])
dp[i][j][idx] = min(dp[i][j][idx], dp[i][j - height[idx-1]][idx-1] + 1);
}
}
then after the whole computation check the minimum value of dp[i][j] for all i, j \geq k .
This solution of time complexity \mathcal O(N^{3}) will pass the first subtask.
Now coming to the final subtask.
For the rest of the editorial we will assume the heights are sorted in non-decreasing order.
Subtask 2
Main Observation
If we take t boxes then it is always optimal to take the t tallest boxes. One subset of these t boxes will be used to create the first tower and the remaining will be used for the second tower.
Create a dp array where dp[i][s] : minimum height greater or equal than s that can be reached using only the last i elements. Therefore dp[i][K] is the minimum height greater than equal to K that can be reached using only the last i elements, or using only the largest i elements. If the sum of heights of the last i elements - dp[i][K] is greater than equal to K means, if a certain subset(which dp[i][K] denotes) having a value of at least K is taken out, the remaining boxes still sum to at least K. Thus it will be possible to create 2 towers with the last i elements if this condition is true.
Calculate dp[i][K] for each i and find the largest i for which the above condition will be true, the least number of boxes required will be then n-i.
If no i exists such that suf[i] - dp[i][K] \geq K output -1.
Time complexity for this solution will be \mathcal O(N^{2}).
Testerâs Solution
The tester uses an optimised knapsack with bitsets. In that solution dp[i] denotes: is it possible to create a towers of height i from some of the boxes considered till now ?
Here âsumâ denotes the sum of height of the boxes considered till now and get_ones(L, R) returns a bitset with all 1âs from index L to R both included. The previous explanation follows from here. Iterate for each box i and check if it is possible to create a towers of height in the range [k, sum - k](denoted as L, R) provided R \geq L. If it is then answer exists and is equal to n - i.
Time Complexty - \mathcal O(N^{2}).
FURTHUR IMPROVEMENTS
It is interesting to note that every time while computing the dp we require
only the current and previous states. Creation of dp[N][K] can thus be minimised
to just dp[2][K], which decreases the memory used greatly. Implementing this solution is left as a task for the reader 
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MAX = 1e9;
const ll N = 4001;
//
//
int dp[N][N];
int height[N], suffix[N];
void solve(){
int n, k;
cin>>n>>k;
for(int i = 0; i < n; i++)
cin>>height[i];
sort(height, height + n);
suffix[n] = 0;
for(int i = n-1; i >= 0; i--)
suffix[i] = suffix[i+1] + height[i];
for(int i = 0; i <= n ; i++)
for(int j = 0; j <= k; j++)
dp[i][j] = MAX;
dp[n][0] = 0;
for(int i = n-1; i >= 0; i--){
for(int j = k; j >= 0; j--){
if(j <= height[i]){
dp[i][j] = height[i];
continue;
}
if(dp[i+1][j-height[i]] == MAX)
dp[i][j] = MAX;
else
dp[i][j] = min(dp[i+1][j], dp[i+1][j-height[i]] + height[i]);
}
}
for(int i = n-1; i >= 0; i--)
if(suffix[i] - dp[i][k] >= k){
cout<<n-i<<"\n";
return ;
}
cout<<-1<<"\n";
}
int main(){
hs;
ll t;
t=1;
cin>>t;
for (int i=1; i<=t; i++){
solve();
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (int)1e4 + 42;
int n, k;
int w[MAXN];
void read() {
cin >> n >> k;
for(int i = 0; i < n; i++) {
cin >> w[i];
chkmin(w[i], k);
}
}
bitset<MAXN * 2> dp, ones, emp;
bitset<MAXN * 2> get_ones(int l, int r) {
// beautiful
return (((ones >> l) << l) << (2 * MAXN - r - 1)) >> (2 * MAXN - r - 1);
}
void print(bitset<MAXN * 2> bs) {
for(int i = 0; i <= 2 * k; i++) {
cout << bs[i];
}
cout << endl;
}
void solve() {
dp = emp;
for(int i = 0; i < MAXN * 2; i++) {
ones[i] = 1;
}
// We can prove that we'll always use the largest M numbers
sort(w, w + n);
int sum = 0;
dp[0] = 1;
for(int i = n - 1; i >= 0; i--) {
dp = dp | (dp << w[i]);
sum += w[i];
int L = k, R = min(sum - k, 2 * MAXN);
if(L <= R && (get_ones(L, R) & dp).count()) {
cout << n - i << endl;
return;
}
}
cout << -1 << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
VIDEO EDITORIAL:
As always, different approach is welcome in the comments 