PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: alpha_ashwin
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming, sorting
PROBLEM:
There are N matches to be scheduled, the i-th with length h_i.
What’s the fewest of them that can be finished in H days such that no other match can be played in the break times between matches?
Matches can start at any time.
EXPLANATION:
Let’s first sort the lengths, so that h_1 \leq h_2 \leq \ldots\leq h_N.
This clearly doesn’t change the answer.
Since we want to hold as few matches as possible, it makes sense to try and schedule longer matches over shorter ones.
Also, notice that the only thing that matters for a schedule is the shortest match that isn’t scheduled: it’s enough to ensure that the shortest unchosen match can’t be fitted in anywhere.
So, let h_i be the shortest unchosen match.
That means the first i-1 matches will definitely be on the schedule.
Next, let’s look at what happens with the other matches - the ones chosen with index \gt i.
Among them, suppose we choose x matches with a total time of y.
The total number of matches is then K = x+i-1, and the total time they need is T = y + h_1 + h_2 + \ldots + h_{i-1}.
Of course, if T \gt H it’s not possible to even play all these matches, so we only deal with T \leq H.
Since there are K matches, we have (at most) K+1 opportunities to insert breaks between them (one before the first match, one after the last one, and K-1 between them).
Also, each break should have a length that’s strictly less than h_i, otherwise we could fit match i in there.
This is possible if and only if (K+1) \cdot h_i + T \gt H.
Why?
Suppose (K+1) \cdot h_i + T \gt H.
This means that, if we arrange things as follows:
- A break of length h_i, then the first match.
- A break of length h_i, then the second match.
\vdots - A break of length h_i, then the last match, then another break of length h_i.
We end up taking strictly more than H hours.
Now, all the breaks can be shortened by some very small number, say 10^{-100}, and the total time taken will still be more than H.
Next, keep shrinking breaks till the total time taken equals H, which is always possible since we started out with T \leq H.
Because of our initial shrinking, all the breaks are of length \lt h_i, and so the match can’t be fit inside any of them, as required.
Conversely, suppose (K+1) \cdot h_i + T \leq H
Then, there are K+1 breaks, and it can be seen that at least one of them will have length \geq h_i — if all the breaks were \lt h_i in length, the total time taken would be strictly less than (K+1) \cdot h_i + T, and hence strictly less than H as well; which is not allowed.
Since one break is of length \geq h_i, match i can be placed into it, which is not what we want.
Notice that once i, x, and y were fixed, the resulting check can be done in \mathcal{O}(1) time.
All we need to know is: among matches i+1, i+2, i+3, \ldots, N, is it possible to choose exactly x of them with a total time of y?
This can be done with the help of dynamic programming.
Let \text{dp}[i][x][y] be a boolean value denoting whether x matches with a total time of y can be chosen from among the suffix starting from i.
Then, we have
based on whether the i-th match is chosen or not.
This dp has \mathcal{O}(N^2 H) states, each with \mathcal{O}(1) transitions, so computing it all is fast enough.
Once all the dp values are known, we can do the following:
- Fix 1 \leq i \leq N, 0 \leq x \leq N, and 0 \leq y \leq H.
- Then, check three conditions:
- \text{dp}[i+1][x][y] should be
True - y + h_1 + h_2 + \ldots + h_{i-1} \leq H
- (K+1) \cdot h_i + T \gt H, where K = i-1+x and T = y + h_1 + h_2 + \ldots + h_{i-1}
- \text{dp}[i+1][x][y] should be
- If all three conditions are satisfied, minimize the answer with x+i-1.
The overall time complexity is \mathcal{O}(N^2 H).
TIME COMPLEXITY:
\mathcal{O}(N^2 H) per testcase.
CODE:
Author's code (C++)
// Constraints + Formatting Validator
#include<bits/stdc++.h>
using namespace std;
// -------------------- Input Checker Start --------------------
// This function reads a long long, character by character, and returns it as a whole long long. It makes sure that it lies in the range [l, r], and the character after the long long is endd. l and r should be in [-1e18, 1e18].
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
if(!(fi == -1))
cerr << "- in between integer\n";
assert(fi == -1);
is_neg = true; // It's a negative integer
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0'; // fi is the first digit
cnt++;
// There shouldn't be leading zeroes. eg. "02" is not valid and assert will fail here.
if(!(fi != 0 || cnt == 1))
cerr << "Leading zeroes found\n";
assert(fi != 0 || cnt == 1);
// "-0" is invalid
if(!(fi != 0 || is_neg == false))
cerr << "-0 found\n";
assert(fi != 0 || is_neg == false);
// The maximum number of digits should be 19, and if it is 19 digits long, then the first digit should be a '1'.
if(!(!(cnt > 19 || (cnt == 19 && fi > 1))))
cerr << "Value greater than 1e18 found\n";
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
// We've reached the end, but the long long isn't in the right range.
cerr << "Constraint violated: Lower Bound = " << l << " Upper Bound = " << r << " Violating Value = " << x << '\n';
assert(false);
}
return x;
}
else if((g == ' ') && (endd == '\n'))
{
cerr << "Extra space found. It should instead have been a new line.\n";
assert(false);
}
else if((g == '\n') && (endd == ' '))
{
cerr << "A new line found where it should have been a space.\n";
assert(false);
}
else
{
cerr << "Something weird has happened.\n";
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
if(!(l <= cnt && cnt <= r))
cerr << "String length not within constraints\n";
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF()
{
char g = getchar();
if(g != EOF)
{
if(g == ' ')
cerr << "Extra space found where the file shold have ended\n";
if(g == '\n')
cerr << "Extra newline found where the file shold have ended\n";
else
cerr << "File didn't end where expected\n";
}
assert(g == EOF);
}
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
bool checkStringContents(string &s, char l, char r) {
for(char x: s) {
if (x < l || x > r) {
cerr << "String is not valid\n";
return false;
}
}
return true;
}
bool isStringBinary(string &s) {
return checkStringContents(s, '0', '1');
}
bool isStringLowerCase(string &s) {
return checkStringContents(s, 'a', 'z');
}
bool isStringUpperCase(string &s) {
return checkStringContents(s, 'A', 'Z');
}
bool isArrayDistinct(vector<int> a) {
sort(a.begin(), a.end());
for(int i = 1 ; i < a.size() ; ++i) {
if (a[i] == a[i-1])
return false;
}
return 1;
}
bool isPermutation(vector<int> &a) {
int n = a.size();
vector<int> done(n);
for(int x: a) {
if (x <= 0 || x > n || done[x-1]) {
cerr << "Not a valid permutation\n";
return false;
}
done[x-1]=1;
}
return true;
}
// -------------------- Input Checker End --------------------
int main(){
ios::sync_with_stdio(false);cin.tie(0);
// CODE TO BE MODIFIED
int t;
t=readIntLn(1,500); // This reads an integer whose value is 1 <= t <= 100, and the line should end right after this integer.
long long s = 0, sumT = 3e5;
while(t--)
{
int n;
n = readIntSp(1,500);
int H;
H = readIntLn(1,500);
int ans = n;
vector<int> h;
h = readVectorInt(n,1,H);
sort(h.begin(), h.end());
bool cases[n+1][H+1];
for (int i=0;i<n+1;i++){
for(int j =0;j<H+1;j++){
cases[i][j] = false;
}
}
cases[0][0] = true;
for (int i=n-1;i>=0;i--){
int t1 = 0;
for (int j =0;j<i;j++){t1+=h[j];}
if (i < n-1){
for (int l=n-1;l>=0;l--){
for(int m =0;m<H+1-h[i+1];m++){
if (cases[l][m]){cases[l+1][m+h[i+1]] = true;}
}
}
}
for (int l=0;l<n+1;l++){
for(int m =0;m<H+1;m++){
if (cases[l][m]){
int tt = t1+m;
if (h[i]*(i+l+1)>(H-tt) && tt<=H && i+l>0){
ans = min(ans,i+l);
}
}
}
}
}
cout<<ans<<endl;
}
// This reads an integer whose value is 1 <= x <= 1000, and the line should end right after this integer.
readEOF(); // This ensures that there is nothing more to read in the input file.
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
//input_checker inp;
const int T = 500;
const int N = 500;
const int H = 500;
const int BS = 505;
int sumn = 0;
void Solve()
{
int n, h;
// n = inp.readInt(1, N); inp.readSpace();
// h = inp.readInt(1, H); inp.readEoln();
// vector <int> a = inp.readInts(n, 1, h); inp.readEoln();
// sumn += n;
// assert(sumn <= N);
cin >> n >> h;
vector <int> a(n);
for (auto &x : a) cin >> x;
vector <int> f(h + 1, 0);
for (auto x : a){
f[x]++;
}
bitset <BS> bs[n + 1];
bs[0].set(0);
int ans = n;
for (int miss = h; miss >= 1; miss--){
int c = 0, s = 0;
for (int i = 1; i < miss; i++){
c += f[i];
s += f[i] * i;
}
for (int fr = 0; fr < f[miss]; fr++){
for (int i = 0; i <= n; i++){
for (int j = 0; j <= h; j++){
if (bs[i].test(j)){
int c1 = c + i;
int s1 = j + s;
// cout << miss << " " << fr << " " << i << " " << j << "\n";
// cout << c1 << " " << s1 << "\n";
if (s1 > h) continue;
int x = (c1 + 1) * (miss) + s1;
if (x > h) ans = min(ans, c1);
}
}
}
c++;
s += miss;
}
for (int fr = 0; fr < f[miss]; fr++){
for (int i = n; i >= 1; i--){
bs[i] |= bs[i - 1] << miss;
}
}
}
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);
// t = inp.readInt(1, T);
// inp.readEoln();
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
// inp.readEof();
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;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, H = map(int, input().split())
h = sorted(list(map(int, input().split())))[::-1]
dp = [ [0 for _ in range(H+1)] for _ in range(n+1)]
dp[0][0] = 1
ans, rem = n, sum(h)
for k in range(n):
x = h[k]
rem -= x
for i in reversed(range(ans)):
for j in range(H+1):
if dp[i][j] == 1 and rem + j <= H:
if rem + j + x*(n-k + i) > H:
ans = min(ans, n-k-1 + i)
if i >= 1 and j >= x: dp[i][j] |= dp[i-1][j-x]
print(ans)