Can someone help me find the bug in my solution? Here it is. I am doing exactly like the editorial states.
Yeah, you get so used to positive-only questions that you donât even notice when they can be negative. Anyway, donât you think it is nice to know that you knew everything you needed to solve the problem. I think thatâs far more important than handing in an AC solution in time.
3 Likes
can you explain more about mistake @priyansh19077
here is my solutionâŚplease look at this too
https://www.codechef.com/viewsolution/34624892
Nice Idea, I have added a new snippet with this to sublime text
I have also added modpow and modinv for the modular power function and the modular inverse. On top of that I have added some inline variants.
I might actually turn it into a class with operator+, operator-, operator*, operator/ to allow calculations as normal and handle modular arithmetic in the background. And then of course turn that class into a snippet.
1 Like
nvm, figured it out. I was calculating mod 2c instead of just c. Still gives errors. Here is the updated code
Hi guys checkout this video solution 
3 Likes
I agree, itâs great to see that I got all the right ideas in my head, 100%. Much more important than the AC.
try out the case when you have the numbers 1, 5, 17. If you find out the average for this it will be (1+5+17)/3 which will not be an integer. Now, if you talk about the average element that can be integer, then you can consider it like this. suppose 1 is the 1st term in the AP, then 17 will be the 5th term in this AP. So by this if you take the 3rd term as the average it will be 9. The number of moves for 9 will be (9-1)/4 + (9-5)/4 + (17-9)/4 = 5
Now, if you take the median element which is 5, the answer will be (5-1)/4 + (5-5)/4 + (17-5)/4 = 4
So, clearly taking the median element and not the average in any way can get you the right answer. I was doing the same mistake during the contest but realized it only after reading the editorial.
1 Like
Sure.
- DONâT use set or unordered set anytime in this problem as the points given in the input can also be same. I had used set to keep the numbers and also the pairs sorted, but this will fail when you want to calculate the exact number of moves.
- While calculating the number of moves for each sub-group, take the median of these elements and not the average of these numbers, or the average integer of these numbers.
- Check for the case where your code might be taking the mod of any negative numbers, because there can be really weird exceptions in that. For handling this, you can just subtract the value of the first number from each element of the particular group, by this the modulus of these numbers wonât be affected and all the numbers will become positive when you will take the mod.
- Make use of C++ STL as much as possible, the code will become easy to understand and debug.
2 Likes
can somebody help me find the issue . I coded this after reading the editorial because i could not solve it during the contest. seems like i couldnât solve even after reading the editorial.
https://www.codechef.com/viewsolution/34633642
Consider c = 1 and points
1 1
2 2
3 3
4 4
100 100
1 Like
Let a = x-y
b = (x%c + c)%c
Can we make key as a + b + a*b in hashmap ?
Someone please help me in finding bug. I havenât found any yet
Link - CodeChef: Practical coding for everyone
Can anyone tell why i am getting TLE in this https://www.codechef.com/viewsolution/34620865.
I have the same logic as in editorial but getting TLE in python.
Same issue I am also facing I guess in python.
Check my sol : CodeChef: Practical coding for everyone
although I just realised that this has costed me 130+ points 
only because I choose Java and not C/C++ ⌠this is life
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