It’s one of the most well-written editorials I have ever seen. Thank you @taran_1407 for the same.
@taran_1407 you explained the solution quite amazingly however during the contest instead of taking median of elements i was taking average so can you please tell me why would taking the average won’t work in this question please?
can you please share your code?
@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
@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.
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?
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.
I also tried this
n = a+b
Key = (n*(n+1)) /2 + a
Can you provide me a case where this will fail
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 
(especially in a short contest).
Select any. It wont matter.
Thanks a lot! I was facing the BUG1 really helped me debug really fast.
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.
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.
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.
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
Yeah, but that will increase a lot lines of code. I will also be a solution in this case.
1 Like
CodeChef: Practical coding for everyone.
I am not getting why my code is throwing a TLE, any help would be appreciated.
Thanks mate …i got it!
Thanks a ton man, you saved my time for Bug1.