CHKPTS - Editorial

editorial
, , ,
48

@supplexcity Sure. But sorry for ugly implementation. I wasn’t thinking straight during contest time. I added some comments though.

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=500005;
vector <int> v[MX],u[MX];

// calculate the number of moves to move all points of k'th to p
ll cost(int k,ll c,ll p)
{
    int l=u[k].size();
    ll r=0;
    for(int i=0;i<l;i++) r+=abs((ll)u[k][i]-p)/c;
    return r;
}

// ternary search to find the minimum number of moves
ll f(int k,ll c)
{
    ll l=*min_element(begin(u[k]),end(u[k]));
    ll r=*max_element(begin(u[k]),end(u[k]));
    ll mn=LLONG_MAX;
    while(true){
        if(r-l<4ll*c){
            while(l<=r){
                ll cs=cost(k,c,l);
                mn=min(mn,cs);
                l+=c;
            }
            break;
        }
        ll m1=l+((r-l)/(c*3ll))*c;
        ll m2=r-((r-l)/(c*3ll))*c;
        ll cs1=cost(k,c,m1);
        ll cs2=cost(k,c,m2);
        if(cs1>cs2) l=m1;
        else r=m2;
    }
    return mn;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        ll mv=0;
        int n,c,x,y,ans=0,k=0,cp=0;
        scanf("%d %d",&n,&c);
        map <int,int> mp;
        for(int i=0;i<n;i++){
            scanf("%d %d",&x,&y);

            // group by y-x
            int p=y-x;
            if(mp.find(p)==end(mp)){
                v[mp[p]=k++].push_back(x);
            }
            else{
                v[mp[p]].push_back(x);
            }
        }
        for(int i=0;i<k;i++){
            int l=v[i].size(),z=0;
            ll m=*min_element(begin(v[i]),end(v[i]));
            if(m<0) m=-m;
            else m=0;

            // group by mod c
            map <ll,int> mm;
            for(int j=0;j<l;j++){
                ll x=((ll)v[i][j]+m)%(ll)c;
                if(mm.find(x)==end(mm)){
                    u[mm[x]=z++].push_back(v[i][j]);
                }
                else{
                    u[mm[x]].push_back(v[i][j]);
                }
            }
            v[i].clear(),cp+=z;

            // sum up number of moves for all groups
            for(int j=0;j<z;j++){
                mv+=f(j,c);
                u[j].clear();
            }
        }
        printf("%d %lld\n",cp,mv);
    }
    return 0;
}
1 Like
49

@priyansh19077 Thank you:) I also got it after some time. I took this example:

c=3
numbers: 0,9,9

average = 6
number of moves=2+1+1=4

median = 9
number of moves=3+0+0=3 which is lesser.

50

Use Python. Brief and concise.

1 Like
51

Correct me if I’m wrong. Let’s say one point gives a = 2, b = 3, and another point give a = 3, b = 2. Now won’t you be storing them under the same group, when they are clearly a part of two different groups?

52

My approach was a little different than the ones I am seeing here. Still got accepted . Just sharing my approach. For any point (X,Y) , I found the point (A,B) such that B is either 0 or B is closest possible positive value it can take for the given C , i.e the point just above the X axis.
Now , it is clear that if 2 points gives same (A,B) , they can be converged into same points. So, simply the number of distinct checkpoints. Hence , number of Checkpoints needed is number of distinct (A,B).
Now, for number of Opeartions. Say (X1,Y1) ,(X2,Y2) … (Xk , Yk) have same (A,B). Then I can simply sort these K points and the checkpoint will have to me the (k/2)th point in the sorted list.
I simply found the sum of distance (either X or Y) of (K/2)th point from all points and number of operations = (Distance/C).
I did this for all possible (A,B) that was generated.
Proof : - If you have N points on a Line, then the sum of distance of a point from all other points is a decreasing function till (N/2) points and then an increasing fucntion. So, N/2 is the minima.

53

I also tried this
n = a+b
Key = (n*(n+1)) /2 + a
Can you provide me a case where this will fail

54

That is some brilliant hashing. I don’t think there will be collisions. Are you sure the rest of your algorithm is solid?

[UPD]: I tried the hash that you have specified with my (AC) algorithm and it gives a WA. The problem has to be the hash function. I was able to find a case with -ve b. I know b cannot be negative, but I’m sure we’ll be able to find a collision for a,b > 0.
Pair 1: a = 3, b = -2
Pair 2: a = 1, b = 1

In general, it’s always better to use the std hash to hash the pairs. This can be easily done by initializing your hashmap as unordered_map<pair<int, int>, typename>. This is always better than coming up with a custom hash for pairs :stuck_out_tongue: (especially in a short contest).

55

Select any. It wont matter.

57

Thanks a lot! I was facing the BUG1 really helped me debug really fast.

58

Can someone tell mistake in my code, it is almost same as in editorial

Please find my solution here:- My solution

PS: I even tried ((x % c) + c) % c) in map from editorial but still WA.

59

You need to find the minimum number of times that so that you move the checkpoints.

Consider this example in 1D plane 1 3 8 and let c be 1, here mean is 4 and the median is 3. If you move them to mean you will move all 3 to 4 and that gives me 3 + 1 + 4 but in case of median we have 2 + 0 + 5.

60

Yeah, I understood there must be some collision. Actually i write code in java so i have to write custom pair class to go to. I tried with custom pair class by manipulating hash and equals function and it got AC. Didn’t work out during contest. It’s good that i atleast learned something. Would be great if i could able to find the collision.

61

Oh! To tackle that maybe you can use a 2D map? Map<Integer, Map<Integer, ArrayList>> . I don’t know java, i’m just guessing.

1 Like
62

Yeah, but that will increase a lot lines of code. I will also be a solution in this case.

1 Like
63

CodeChef: Practical coding for everyone.
I am not getting why my code is throwing a TLE, any help would be appreciated.

64

Thanks mate …i got it!

66

Thanks a ton man, you saved my time for Bug1.

67

I just forgot to divide my answer by c. Btw thanks for your help and suggestions @priyansh19077

68

can you plzz help me.
i am getting WA
can u tell me what i am doing wrong
https://www.codechef.com/viewsolution/35763007

69

After finding the groups on basis of (x-y), for each of the group_i, again form group_{ij} on basis of x mod c. Also, take care for negative values of the remainder.
The number of checkpoint is count(group_{ij}) and no. of moves needed should be summed over all such groups.
You need to start by creating groups from the vector on line 60 in your linked submission.

1 Like