PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester & Editorialist: iceknight1093
DIFFICULTY:
1442
PREREQUISITES:
None
PROBLEM:
There are N empty boxes, and A_i balls of color i (for 1 \leq i \leq M).
The balls must be distributed to the boxes such that:
- Every ball is placed in a box
- Each box contains balls of distinct colors
Find the minimum number of boxes that have balls of all M colors.
EXPLANATION:
Let’s try to place the balls in the boxes one color at a time, i.e, from 1 to M.
A box will be called bad if it contains a ball of all colors seen so far, and good otherwise.
Our objective is to have as few bad boxes (or equivalently, as many good boxes) as possible in the end.
For each i from 1 to M, notice that:
- We can freely place balls of color i in any existing good boxes: they will still remain good.
This is because a good box at this stage must be missing a color that’s \lt i, which it will continue to not have in the future. - If we place a ball of color i in a bad box, it will remain bad.
- If we don’t place a ball of color i in a bad box, it will turn good after this step.
Given that our aim is to maximize the number of good boxes, clearly the optimal strategy is to place balls in good boxes first, and only then place them in bad boxes.
This ensures that we convert as many bad boxes to good, as possible.
In particular, we have the following algorithm:
Suppose there are currently x bad boxes and y good ones.
Initially, x = N and y = 0.
For each i from 1 to M:
- We can place \min(A_i, y) balls into good boxes; so let’s do that first.
- The remaining A_i - \min(A_i, y) balls must be placed into bad boxes; and only these boxes will remain bad.
- So, we can update x \to A_i - \min(A_i, y) and y \to N - x.
Finally, print the value of x.
TIME COMPLEXITY
\mathcal{O}(M) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
void solve()
{
di(n) di(m)
vi a(m);
take(a,m);
int cl=n,op=0;
rep(i,0,m){
if(a[i]<=op){cout<<"0\n";return;}
int rem = a[i]-op;
cl = rem;
op = n-cl;
}
cout<<cl<<"\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
di(t)
while(t--)
solve();
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
good, bad = 0, n
for x in list(map(int, input().split())):
rem = max(0, x - good)
good += bad - rem
bad = rem
print(bad)
