PROBLEM LINK:
Author: Ojas Bansal
Tester: Yash Chandnani
Editorialist: Michael Nematollahi
DIFFICULTY:
EASY
PREREQUISITES:
Two-Pointers
PROBLEM:
You are given two integers N and M. There are N boxes arranged in a line, each painted using one of the only M existing colours. The arrangement is such that there are no two boxes of the same colour among any M consecutive boxes.
We know that the i^{th} box in the line has a_i balls inside it. Your task is to choose M boxes, each of a distinct colour, such that the maximum difference between the number of balls in any two of them is minimized.
QUICK EXPLANATION:
First, observe that the colour of the i^{th} box is the same as the colour of the (i \mod M)^{th} box (zero-based).
Now, sort the boxes by the number of balls. Fix the box with the smallest number of balls, then keep increasing the threshold for the maximum number of balls until you have M boxes of different colours. You can speed up the process by using the two pointers technique. The overall complexity should be O(N).
EXPLANATION:
First, let’s figure out how the boxes are coloured.
The fact that the colouring of the boxes is not given in the input should hint that it is uniquely determined.
To understand how the colouring works, start with the first M boxes. Let’s denote the colour of the i^{th} box by c_i. We know that there is exactly one instance of c_1 in the first M boxes. Hence, the colour of the (M+1)^{th} box should be the same as c_1, otherwise the second M consecutive boxes would not have an instance of c_1.
We can continue this observation and find out that the color of the (M+2)^{th} box is the same as c_2, the colour of the (M+3)^{th} box is the same as c_3 and so on. Generally, the colour of the i^{th} box is the same as c_{((i-1) \mod M) + 1}.
Now that we have the color c_i of every box, let’s sort the boxes by the number of balls inside them. From now on, we’ll assume a_i \le a_j if i \le j.
Consider the final selection of the boxes. The maximum difference between the number of balls in any two chosen boxes is equal to the difference between the number of balls inside the first and last box (because they are sorted).
Having made the above observation, we fix and start with the first chosen box l and keep taking the next box as long as we don’t have at least one instance of every colour. Assume the last box we take is labelled r. Once we have at least one instance of every colour, we can discard the excess boxes of each colour so that we end up with exactly one instance of every colour. This is the optimal selection if our first selected box is l, because there are no instances of colour c_r among the boxes l, l+1, \dots, r-1.
The complexity of the above solutions is O(N^2), as we need to fix the first box and possibly iterate through the rest of the boxes. However, we can use the two pointers technique to reduce the complexity to O(N). To do so, we keep an array cnt, where cnt[i] denotes the number of instances of colour i in our current range. Once the number of colours j where cnt[j] = 0 reaches 0 (denoted by cnt0 in the editorialist’s code), we will have at least one instance of every colour.
To view an implementation of the described solution, refer to the editorialist’s code below.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define maxN 1000005
#define rep(i,n) for(int i=0;i<n;i++)
#define refv(i,l,r) for(int i=l;i<r;i++)
#define rerv(i,l,r) for(int i=l;i>r;i--)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll> >
int power(int x, unsigned int y){int res = 1;while (y > 0){ if (y & 1){res = res*x;} y = y>>1;x = x*x;}return res;}
int powermod(int x, unsigned int y, int p){int res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1; x = (x*x) % p;}return res;}
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define inf 10000000000000
#define F first
#define S second
#define mod 1000000007
#define printvector(v) for(int i= 0;i<v.size();i++) {cout<<v[i]<<" ";} cout<<endl;
#define printset(s) for(auto it = s.begin();it!=S.end();it++){cout<<*it<<" ";} cout<<endl;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endl '\n'
using namespace std;
int32_t main()
{
//freopen("input1.in", "rb", stdin);
//freopen("output1.in", "wb", stdout);
fastio;
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
int a[n];
rep(i,n)
{
cin>>a[i];
}
vector<int> v[m];
rep(i,m)
{
for(int j=i;j<n;j+=m)
{
v[i].pb(a[j]);
}
sort(all(v[i]));
}
int ind[m]={0};
set<pi> s;
int ans=inf;
rep(i,m)
{
s.insert(mp(v[i][0],i));
}
while(1)
{
pi mini=*s.begin();
pi maxi=*(s.rbegin());
ans=min(ans,maxi.F-mini.F);
s.erase(mini);
if(ind[mini.S]+1>=v[mini.S].size())
{
break;
}
s.insert(mp(v[mini.S][++ind[mini.S]],mini.S));
}
cout<<ans<<endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
int lst[100009];
void solve(){
int n=rint(' '),m=rint('\n');
assert(n>=2&&n<=100000);
assert(m>=2&&m<=n);
vector<pii> z;
rep(i,n){
int x;
if(i!=n-1) x= rint(' ');
else x= rint('\n');
assert(x>=1&&x<=1000000000);
z.pb(mp(x,i%m));
}
sort(all(z));
set<pii> s;
memset(lst,-1,sizeof(lst));
int ans = 1e9;
trav(i,z){
if(lst[i.snd]!=-1) s.erase(mp(lst[i.snd],i.snd));
lst[i.snd] = i.fst;
s.insert(i);
if(sz(s)==m){
ans=min(ans,s.rbegin()->fst-s.begin()->fst);
}
}
cout<<ans<<'\n';
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n=rint('\n');
assert(n>=1&&n<=5);
rep(i,n) solve();
assert(getchar()==EOF);
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
const int MAXN = 1e5 + 10;
int n, m, cnt[MAXN], cnt0;
pii a[MAXN];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
cin >> n >> m;
for (int i = 0; i < n; i++){
cin >> a[i].F;
a[i].S = i%m;
}
sort(a, a + n);
int ans = 2e9;
for (int i = 0; i < m; i++) cnt[i] = 0;
cnt0 = m;
int r = 0;
for (int l = 0; l < n; l++){
while (r < n && cnt0 > 0){
cnt0 -= cnt[a[r].S] == 0;
cnt[a[r++].S]++;
}
if (cnt0 == 0)
ans = min(ans, a[r-1].F - a[l].F);
cnt[a[l].S]--;
cnt0 += cnt[a[l].S] == 0;
}
cout << ans << "\n";
}
return 0;
}