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. 
Come here any time a contest takes place, and learn new stuff.