CAMC - Editorial

editorial
, , , , ,
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
.

41

Can anybody please tell at which test case this code is giving WA: CodeChef: Practical coding for everyone

42

It fails on the testcase:

1
2 2
50 16
43

Thanks for the test case.

1 Like
44

Hi coders,

Please help me out with the test case for which my code fails as I am getting WA on submissions. I have tried to cover all boundary cases however I feel I am not able to cover all. Link to my code is:
https://www.codechef.com/viewsolution/27940370

Thanks,
Learner

45

Your solution fails for the testcase:

1
6 2
95 38 9 41 57 5

(the answer should be 4:

Best choice:
  95   38 [  9]  41   57 [  5]
  R    G    R    G    R    G  
max - min = 4

)

3 Likes