PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Setter: Daksh Garg, Aditya Kumar Singh
Tester: Daanish Mahajan
DIFFICULTY:
Easy
PREREQUISITES:
Binary search, Greedy
PROBLEM:
Given K array of length N with the value of integers from L to R. The function value of an array is the sum of all the N numbers. In one operation you can change at most one number in all the array in the given range (L, R). Find the minimum number of operation required to make all the array’s function value
EXPLANATION:
For each array, we can calculate m_i and M_i, where m_i is the minimum function value which can be achieved after ith operations and similarly M_i is the maximum function value. So after getting these ranges for all K Array, we have to check if all the ranges have any common point, then the answer is possible after ith operations. To get the m_i we have to change all i maximum elements to L and then calculate the minimum function value. Similarly, for M_i we have to change all i minimum elements to R and then calculate the function values.
Both can be calculated in O(i*k) after we already sorted all the arrays. So we can do a binary search on i to get the answer in O(n*k*log(R-L)).
But this can be done without using binary search and in O(n*k), starting from i=0 operating check for all the conditions and if all are fulfilled then break it and print the answer otherwise increment i, but the catch here is we can calculate m_i and M_i in O(k) using the values of m_{i-1} and M_{i-1}. For m_i we just have to change the ith largest element to L and add the changes according to it… Similarly, for M_i we have to make i_{th} smallest element to R.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin("input.txt");ofstream fout("output.txt");
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
void solve()
{
ll k,n,l,r;
cin>>k>>n>>l>>r;
ll a[k][n];
vi mi(k),ma(k);
rep(i,0,k)
{
ll s=0;
rep(j,0,n)
{
cin>>a[i][j];
s+=a[i][j];
}
sort(a[i],a[i]+n);
mi[i]=s;
ma[i]=s;
}
for(int i=0;i<=n;i++)
{
ll maoma=0,miomi=1e18;
int iind=i-1,deci=n-i;
for(int j=0;j<k;j++)
{
if(iind>=0)
{
mi[j]=mi[j]+r-a[j][iind];
ma[j]=ma[j]+l-a[j][deci];
}
maoma=max(maoma,ma[j]);
miomi=min(miomi,mi[j]);
}
if(maoma<=miomi)
{
cout<<i<<endl;
return;
}
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.in", "r", stdin);
freopen("outputf.in", "w", stdout);
#endif
fast;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
# define pb push_back
# define pll pair<ll, ll>
# define pli pair<ll, int>
# define mp make_pair
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cout << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
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,' ');
}
const int maxn = 1e5, maxk = 1e5, maxnk = 1e5, maxt = 5, maxv = 1e9;
int main()
{
int t = readIntLn(1, maxt);
while(t--){
int k = readIntSp(1, maxk), n = readIntSp(1, maxn), l = readIntSp(1, maxv), r = readIntLn(l, maxv);
assert(n * k <= 100000);
vector<int> v[k]; vector<pll> range;
ll pv = -1; bool no = true;
for(int i = 0; i < k; i++){
v[i].clear();
ll sum = 0;
for(int j = 0; j < n; j++){
int x = j == n - 1 ? readIntLn(l, r) : readIntSp(l, r);
v[i].pb(x);
sum += x;
}
sort(v[i].begin(), v[i].end());
range.pb(mp(sum, sum));
if(pv == -1)pv = sum;
no &= (pv == sum);
}
int ans = no ? 0 : n;
vector<pli> end;
for(int i = 0; i < n && ans != 0; i++){
ll maxr = -1, minr = 1e15;
for(int j = 0; j < k; j++){
maxr = max(maxr, range[j].first -= v[j][n - i - 1] - l);
minr = min(minr, range[j].second += r - v[j][i]);
}
if(maxr <= minr){
ans = i + 1;
break;
}
}
cout << ans << endl;
}
assert(getchar()==-1);
}