CAMC - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

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;
}
11 Likes

Please explain the objective of this loop.

2 Likes

We have:

while (r < n && cnt0 > 0){ cnt0 -= cnt[a[r].S] == 0; cnt[a[r++].S]++; }

Re-writing this a little:

while (r < n && cnt0 > 0)
{ 
    if (cnt[a[r].S] == 0)
    {
        cnt0--; 
    }
    cnt[a[r].S]++; 
    r++;
}

i.e. it’s a very cryptic way of writing the equivalent of the loop beginning at line 53 in my solution, with cnt0 being similar to my numColoursInRange (except cnt0 is more like numColoursNotYetInRange i.e. the inverse of numColoursInRange!); r is the same as my rightIndex ; and the cnt array is the same as my numOfColourInRange. I think :slight_smile:

9 Likes

I’ve used a partially different approach if anyone finds it useful :slight_smile:
CodeChef: Practical coding for everyone

1 Like

Link to my approach, have used unordered_map for better efficiency instead of set and have added comments:

3 Likes

I have used almost same logic but i still got wrong answer. Can anyone Explain me why i am getting wrong answer? Where my logic is wrong?
My code link is:
https://www.codechef.com/viewsolution/27874762

1 Like

It gives the wrong answer for e.g.

1
6 3
15 14 36 1 33 38 

(The answer should be 21:

Best choice:
[ 15]  14 [ 36]   1 [ 33]  38 
  R    G    B    R    G    B  
max - min = 21

)

1 Like

How is overall complexity O(N) after sorting?
I solved it by learning a new data structure simultaneous minMax heap.
https://www.codechef.com/viewsolution/27819250

Let N = 10 and M = 3
15,10,25,30,45,60,35,20,55,40
After sorting them to their respective colors
v[0] = {15, 30, 35, 40};
v[1] = {10, 20, 45};
v[2] = {25, 55, 60};
The minimum difference should be 15 - 10 = 5, but according to the code mentioned above the ans is 10. Why is it so?

1 Like

1
6 3
1 2 10 12 3 8

Take this as a test case
if i color them like
RGBRBG
it satisfies all the requirements in the problem set
So the answer should be 2(3-1)

But according to editorial and editorials code it gives 7

Have i understood anything wrong , please someone explain

Every M(=3) consecutive boxes should have distinct colors. Your way of coloring is wrong (BRB).

2 Likes

Thanks a lot , i misjudged the statement

IF WE ARE USING SORTING, how can the overall complexity be O(N)

2 Likes

I found using an array of priority_queue was better even though the complexity was a bit off than linear time

your coloring is wrong. For every m consecutive boxes colors should be unique
In your case you are doing RGBRBG here for index 2 you see from 2 to 4 index BRB 2nd and 4th index color is same so this configuration is wrong.
Possible configurations are RGBRGB or RBGRBG or GBRGBR or GRBGRB or BRGBRG or BGRBGR

For the given test case ans would be 7 if you pick 1st box, 5th and 6th box

1 Like

This question is solved exactly by using the following link from GeeksforGeeks -

Find smallest range containing elements from k lists

1 Like

My solution is nearly with same approach but still i cant find error .Please help me where my code is failing

https://www.codechef.com/viewsolution/27821329

It fails on the testcase:

1
5 3
4 1 3 11 4 

(the answer should be 1, from choosing both 4s and the 3:

Best choice:
[  4]   1 [  3]  11 [  4]
  R    G    B    R    G  
max - min = 1

)

1 Like

After changing still i getting error please help
https://www.codechef.com/viewsolution/27887844

The testcase:

1
5 2
12 17 16 8 1 

triggers an out-of-bounds std::vector access in your code.

1 Like