CAMC - Editorial

editorial
, , , , ,
21

but why it fails on intial testcase

22

Thanks @ssjgz finally got right answer…Thanks you very much for helping me so much.

1 Like
23

Nice job - happy to help :slight_smile:

1 Like
24

Hi,

Need help

6 3
10 9 8 6 4 2
R G B R G B

After sort

2 4 6 8 9 10

as mentioned we need to selected first item in sorted(based on ball number) and continue selecting till we get all the color
but 2, 4,6 I have all the color but difference 4(6-2)
So, best possible 8 9 10 which give me difference 2(10-8)

25

A suggestion, to Setter, Editor, Tester, while writing your code, please keep in mind that people expect it to be somewhat readable, so that those who are not able to solve can actually make something out of it.
A few lines of comments or an easy to understand code doesn’t take much.

10 Likes
26

The editorial’s solution is unnecessarily iterating till last pass - when the number of remaining elements in current window is less than M.
It should iterate till l <= N-M.

Edited line:
for (int l = 0; l <= n-m; l++){ ... }

27

cnt0 - number of found distinct colors.
cnt[i] - occurences of a color i in choosen m boxes.
l - left side pointer, r - right side pointer
a - array of pairs where a[i].F = number of balls ith box, a[i].S = color of ith box
Inner loop start with r & advances r till it reaches end or found m colors. Decrements cnt0 if color was not found earlier.
Once cnt0 is zero we have found m colors store it. Repeat the same process for each index.

1 Like
28

https://www.codechef.com/viewsolution/27905163
where am i wrong ?? plzzz help

29

Yours fails on the testcase:

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
3 Likes
30

After reading the quick hint, I tried it on my own…
Although I did almost the same, it is still not optimized…Can’t understand why ?

I have just used 2 nested loops like the editorialist’s solution & terminated the inner loop once we select ‘m’ (in my code k) values…

Can anyone help me out ?
My Solution (CAMC)

31

You’re resetting c and j for each i, giving an O(N^2) solution.

Edit:

For a concrete testcase that triggers O(N^2) computations, consider this one.

2 Likes
32

On your testcase my implementation solves it in around 0.5 seconds. I think this is because I skip the similar colors when I encounter them in the sorted sequence.
What I mean by that is say after sorting you have some sequence of colors RGRAGBA... now if the sequence is not complete and you encounter a similar color you can discard the previous occurrence of that color and replace it by the new occurrence.
https://www.codechef.com/viewsolution/27771209

1 Like
33

@ssjgz I have used the same approach , still it is giving tle for the 2nd subtask ?
link to my solution

#include<bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#define ll long long int
#define ull unsigned long long int
#define big cpp_int
using namespace std;
using namespace boost::multiprecision;

struct data{
    ll val;
    int ind;
};

bool compare(data a, data b){
    return a.val < b.val;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        data a[n];
        ll ans = INT_MAX;
        ll k;
        for(int i=0;i<n;i++){
            cin>>k;
            a[i].val = k;
            a[i].ind = i%m;
        }

        sort(a,a+n,compare);
        int cnt[m] = {0};
        int cnt0 = 0;
        int r = 0;
        for(int i=0;i<n;i++){
            cnt0 = 0;
            r = i;
            while(cnt0<m && r<n){
                if(cnt[a[r].ind]<=i){
                    cnt0++;
                    cnt[a[r].ind]++;
                }
                r++;
            }
            if(cnt0==m){
                ans = min(ans,a[r-1].val-a[i].val);
            }
        }
        cout<<ans<<endl;
    }
	return 0;
}
34

Yours seems to time out on the same testcase as this guy, and for the same reason :slight_smile:

Edit:

This testcase is even “better” for your solution.

1 Like
35

I don’t understand this part of the editorialist’s code, why he is incrementing by 1, whenever cnt[l].S == 0 ?
@ssjgz Also The previous color cnt[l].S can occur in between the range of l and r, when selecting next box as l but the while loop will always look for the color cnt[l].S after the r of previous box.

36

The colour a[l].S used to be in the range l-r, but we’re about to increment l and then it won’t be.

37

@ssjgz correct, but why increment only when cnt[l].S ==0, it should always increment , so shouldn’t it be cnt0++ instead of cnt0 += cnt[a[l].S] == 0;

1 Like
38

If cnt[a[l].S] != 0, then there are still other occurrences of the colour a[l].S in the range even after we increment l, in which case we should not increment cnt0.

2 Likes
39

Thanks a lot :smiley:

1 Like
40

i m not getting the point in solution…Can anyone explain it in a more easy way
.