CHKPTS - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: tasmeemreza
Tester: Raja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Observation, Basic Implementation.

PROBLEM:

Given a set of N points in cartesian plane and an integer c. You are allowed to perform operations of the type: choose a point (x_i, y_i) and change it to (x_i-c, y_i-c) or (x_i+c, y_i+c).

You need to set up checkpoints (represented by points) and perform operations such that each of the N points is located at one of the checkpoints.

You need to find the minimum number of checkpoints required, and then the minimum number of operations to move all points into the above checkpoints.

QUICK EXPLANATION

  • Any number of operations doesn’t affect x_i-y_i for any point, so let’s group all points with the same d = x_i-y_i. After grouping, y_i shall behave the same as x_i-d within the group, so let’s ignore y_i
  • Each group can be seen as points on number line, and we can move each point left or right by c, So let’s further divide these groups based on x_i \bmod c.
  • All points within same group can move to same point. So the number of groups now is the number of checkpoints. Consider each group in sorted order of x_i. It is optimal to choose the median of this group as the checkpoint, as it minimizes the number of operations required to move all points to this point.

EXPLANATION

As mentioned in the quick explanation, we can easily notice that any number of operations do not affect x_i-y_i. This implies that if initially two points (x_i, y_i) and (x_j, y_j) exist such that x_i-y_i \neq x_j-y_j, then they can never move to the same checkpoint.

Hence, let’s group all points with same x_i-y_i into the same group. We can solve this problem independently of each group and then take the sum of answers for each group. So let’s focus on one group only.

Within this group, y-coordinate of each point shall behave the same as x_i-d, where d = x_i-y_i is the same for the whole group, so we can discard y-coordinate of each point, and consider all these points as points on a number line.

Now we have some points on number line and an integer c, we are allowed to move any point left or right by c units in one operation.

To move a point from x_i from x_j, we need c | (x_i-x_j) which implies x_i = x_j \pmod c

Hence, a pair of points x_i and x_j cannot be moved to the same point if x_i = x_j \pmod c doesn’t hold. So, lets group these points by x_i \bmod c

Now, we can move all points within same group to same point. Hence the number of such groups is the minimum number of checkpoints required.

Finding the minimum number of operations needed
We need to choose one checkpoint for each such group. For this, try to work out the following examples, where x_i and c are given.

0 1 2 4 6

we have c = 1.

working out example

Let’s denote checkpoint by X (We are still in one dimension), we want to choose such X such that \sum_{i = 1}^N |X-x_i|/c is minimized.
X = 0 gives 0+1+2+4+6 = 13
X = 1 gives 1+0+1+3+5 = 10
X = 2 gives 2+1+0+2+4 = 9
X = 3 gives 3+2+1+1+3 = 10
X = 4 gives 4+3+2+0+2 = 11
X = 5 gives 5+4+3+1+1 = 14
X = 6 gives 6+5+4+2+0 = 17

We can prove that choosing the median shall minimize the number of operations (Can be easily proved by exchange argument). In case of an even number of elements, any median shall work. Hence, we have found the checkpoint, we can easily take a sum of \displaystyle\frac{|X-x_i|}{c} to get the required number of operations.

TIME COMPLEXITY

The time complexity is O(N*log(N)) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n, c;
  scanf("%d %d", &n, &c);
  map <pair <int, int>, vector <pair <int, int>>> cont;
  for(int i = 1; i <= n; i++) {
	int x, y;
	scanf("%d %d", &x, &y);
	cont[make_pair(x - y, ((x % c) + c) % c)].emplace_back(x, y);
  }
  int checkpoint = cont.size();
  long long moves = 0;
  for(auto i : cont) {
	auto v = i.second;
	sort(v.begin(), v.end());
	auto pivot = v[v.size() / 2];
	for(auto j : v) {
	  moves += abs(pivot.first - j.first) / c;
	}
  }
  printf("%d %lld\n", checkpoint, moves);
}
int main() {
  int t;
  scanf("%d", &t);
  for(int cs = 1; cs <= t; cs++) {
	solve();
  }
  return 0;
}
Tester's Solution
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


//std::ios::sync_with_stdio(false);

int x[500005],y[500005];
vector<vi>vec(500005),pos(500005);
map<int,int>mapi;
map<int,int>::iterator it;
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,c,i,j,k,moves=0,chkpoint=0,m,num,temp,siz,res;
		cin>>n>>c;
		mapi.clear();
		rep(i,n){
			cin>>x[i]>>y[i];
			mapi[y[i]-x[i]]=1;
		}
		m=0;
		for(it=mapi.begin();it!=mapi.end();it++){
			it->ss=m++;
		}
		rep(i,n){
			vec[mapi[y[i]-x[i]]].pb(y[i]);
		}
		rep(i,m){
			sort(all(vec[i]));
			mapi.clear();
			temp=vec[i][0];
			rep(j,vec[i].size()){
				vec[i][j]-=temp;
				mapi[vec[i][j]%c]=1;		
			}
			num=0;
			for(it=mapi.begin();it!=mapi.end();it++){
				it->ss=num++;
			}
			rep(j,vec[i].size()){
				pos[mapi[vec[i][j]%c]].pb(vec[i][j]);
			}
			rep(j,num){
				chkpoint++;
				siz=pos[j].size();
				res=pos[j][siz/2];
				rep(k,siz){
					moves+=(abs(res-pos[j][k])/c);
				}
				pos[j].clear();
			}
			vec[i].clear();
		}
		cout<<chkpoint<<" "<<moves<<endl;
	}
	return 0;
} 
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHKPTS{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int N = ni();
	    long C = nl();
	    long[][] P = new long[N][3];
	    for(int i = 0; i< N; i++){
	        P[i][0] = nl();
	        P[i][1] = nl();
	        P[i][2] = (P[i][0]%C+C)%C;
	    }
	    Arrays.sort(P, (long[] l1, long[] l2) -> {
	        if(l1[0]-l1[1] != l2[0]-l2[1])return Long.compare(l1[0]-l1[1], l2[0]-l2[1]); //Points with same xi-yi appear together now
	        if(l1[2] != l2[2])return Long.compare(l1[2], l2[2]);//Points with same xi-yi and xi%c appear together now
	        return Long.compare(l1[0], l2[0]);//Points with same xi-yi and xi%c appear together now in sorted order of x_i
	    });
	    int cnt = 0;
	    long dist = 0;
	    for(int i = 0, j = 0; i< N; i = j){
	        int median = i-1;
	        while(j < N && P[j][0]-P[j][1] == P[i][0]-P[i][1] && P[i][2] == P[j][2]){
	            j++;
	            if((j-i)%2 == 1)median++;
	        }
	        //segment [i, j) represent a single group, which is merged at P[median][0]
	        cnt++;
	        for(int k = i; k< j; k++)
	            dist += Math.abs(P[k][0]-P[median][0])/C;
	    }
	    pn(cnt+" "+dist);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader("C:/users/user/desktop/0.in");
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new CHKPTS().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

18 Likes

Such quick editorials in CodeChef contests are a rarity. Thank You!

14 Likes

I did the exact same thing. If somebody can just look at my code once, it would really help me. I am getting a wrong answer. Thanks in advance.
Here is the link to my submission:
https://www.codechef.com/viewsolution/34611088

After grouping by x_i-d, why don’t we need to, for a group, check if all points other than the median can be shifted to the median? Is it always possible?
Also, what is the optimal choice when there are two medians?

It has been a long time since I participated in a short contest, so I was a bit sloppy. It took a lot of debugging but eventually I got it working. Here are my two bugs for anyone that needs it

Bug 1

Modular arithmetic in C++ is weird with negative numbers. I can’t understand why someone would choose -3 % 2 = -1. Instead of a % b you should use ((a % b) + b) % b

Bug 2

I grouped the points using a sort. This sort first compared the difference (above called d), then if those were equal it compared the modulo of x. I forgot to add that if those were equal then it should compare the actual values of x, otherwise the middle element isn’t the median

I hope this helps others find bugs in their programs

17 Likes

I did the same thing can anyone help me debug this code
https://www.codechef.com/viewsolution/34616709

Can someone help me in finding bug in my code. Thanks in advance
Link - https://www.codechef.com/viewsolution/34614832

I tried same thing but could not find a way to minimize number of operation.

If the number is negative you can’t do abs(number)%c.
For example -6%7 should be 1 and not 6.
I too made the same mistake and spent a good amount of time before realizing it

3 Likes

I understood my mistake. I was using set to keep everything in a sorted manner but what I didn’t realise was that there can be same points also in the input. If anybody else is also using set to keep things sorted, swtich to a vector and then sort it later.

1 Like

I’m not sure but I think you’ve done the same mistake.
Read my comment above

Edit: Oh you got your mistake, nevermind then

I did the very same thing, in Java, got TLE: https://www.codechef.com/viewsolution/34614179

I guess Java performs poorer, despite that the time threshold is increased for it.

thanks bro

very nice problem !!
thanks!!

Nice problem. Setter’s implementation is clever. I had to group coordinates twice because of not using pair for mapping. And I thought about selecting the median, but I wasn’t sure about this. Luckily I found out that the cost function is uni-modal. So I used ternary search to find the number of moves.

1 Like

and for this all kind of modular arithmetic i made some functions so that in contest time , at least these type of error will not happen -

ll modmul(ll a, ll b) {
    return ((a%mod) * (b%mod)) % mod;
}

ll modadd(ll a , ll b){
    return((a%mod)+(b%mod)+mod)%mod;
}

ll modsub(ll a , ll b){
    return((a%mod) - (b%mod) + mod)%mod;
}

2 Likes

I knew how to deal with mod on negative numbers but still got WA.I didn’t read the constraints that the co-ordinates could be negative.

Code which got WA on 47th minute of the contest
AC code
Both of them differ only in line 62.
Goodbye, 5 stars dream!

Goodbye, 5 stars dream!

Why?! Come on, just see how fluctuating my rating is! That’s because I never guard it as a treasure, and always participate, so that I can learn new things. And that’s why I have been destroying it dozens of times. I used to be 5 stars once.
Of course your dream is not gone. One day it will happen. Believe in yourself! :slight_smile: Come here any time a contest takes place, and learn new stuff.

Also, see my Java code, it does exactly what the editorial says, but it gets TLE. What should I say? :slight_smile: It is not fair to get advantage only because your language of choice is C/C++. But this is life. It is hard-to-impossible to say simply that JavaLimit = 2*CLimit.

1 Like

I think the problem statement states that c > 0. Hence the answer should be no.

Ahh yeah …even I did same mistake :persevere:

1 Like