I came across this question from USACO SILVER 2025, being new on cf took me hour(s) to crack it, and when I did, it used a basic property that SUM(abs(a[i]-x)) 1<=i<=n in an array a , is minimum if x is median. Sharing my approach and solution, Open for suggestions on how to improve thought process.↵
↵
CODE->↵
↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)↵
↵
#define int long long↵
#define double long double↵
↵
typedef long long ll;↵
typedef unsigned long long ull;↵
↵
typedef vector<int> vi;↵
typedef vector<ll> vll;↵
typedef pair<int,int> pii;↵
typedef pair<ll,ll> pll;↵
↵
#define pb push_back↵
#define ff first↵
#define ss second↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
↵
#define YES cout << "YES\n"↵
#define NO cout << "NO\n"↵
#define endl '\n'↵
↵
#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;↵
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];↵
↵
const ll INF = 1e18;↵
const int MOD = 1e9 + 7;↵
void solve() {↵
int n,m;↵
cin>>n>>m;↵
vector<int> a(n),pref(2*n+1,0);↵
for(int i=0;i<n;++i){↵
int y;↵
cin>>y;↵
a[i]=y%m;↵
}↵
sort(all(a));↵
for(int i=0;i<n;++i){↵
a.pb(a[i]+m);↵
}↵
for(int i=1;i<=2*n;++i){↵
pref[i]=pref[i-1]+a[i-1];↵
}↵
int ans=INF;↵
for(int i=0;i<n;++i){↵
// window from i to i+n-1 is sorted and shows unwraping of circle, its median minimizes cost ↵
// each cut fixes x%m, there are n distinct cuts, so n distinct x%m that can minimize cost↵
// make min cost over them↵
// for a fixes cut this is just linear absolute sum --> min at median if sorted, which is!!↵
int me=i+n/2;↵
int t1=(me-i)*a[me];↵
int t2=(pref[me]-pref[i]);↵
int t3=(pref[n+i]-pref[me]);↵
int t4=(n+i-me)*a[me];↵
ans=min(ans,t1+t3-t2-t4);↵
}↵
cout<<ans<<endl;↵
}↵
↵
int32_t main() {↵
fastio();↵
int t = 1;↵
cin >> t;↵
while(t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
↵
CODE->↵
↵
↵
~~~~~↵
Your code here...↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define fastio() ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)↵
↵
#define int long long↵
#define double long double↵
↵
typedef long long ll;↵
typedef unsigned long long ull;↵
↵
typedef vector<int> vi;↵
typedef vector<ll> vll;↵
typedef pair<int,int> pii;↵
typedef pair<ll,ll> pll;↵
↵
#define pb push_back↵
#define ff first↵
#define ss second↵
#define all(x) (x).begin(), (x).end()↵
#define rall(x) (x).rbegin(), (x).rend()↵
↵
#define YES cout << "YES\n"↵
#define NO cout << "NO\n"↵
#define endl '\n'↵
↵
#define IN_VEC(v,n) vector<int> v(n); for(auto &i : v) cin >> i;↵
#define IN_ARR(arr,n) for(int i=0;i<n;i++) cin >> arr[i];↵
↵
const ll INF = 1e18;↵
const int MOD = 1e9 + 7;↵
void solve() {↵
int n,m;↵
cin>>n>>m;↵
vector<int> a(n),pref(2*n+1,0);↵
for(int i=0;i<n;++i){↵
int y;↵
cin>>y;↵
a[i]=y%m;↵
}↵
sort(all(a));↵
for(int i=0;i<n;++i){↵
a.pb(a[i]+m);↵
}↵
for(int i=1;i<=2*n;++i){↵
pref[i]=pref[i-1]+a[i-1];↵
}↵
int ans=INF;↵
for(int i=0;i<n;++i){↵
// window from i to i+n-1 is sorted and shows unwraping of circle, its median minimizes cost ↵
// each cut fixes x%m, there are n distinct cuts, so n distinct x%m that can minimize cost↵
// make min cost over them↵
// for a fixes cut this is just linear absolute sum --> min at median if sorted, which is!!↵
int me=i+n/2;↵
int t1=(me-i)*a[me];↵
int t2=(pref[me]-pref[i]);↵
int t3=(pref[n+i]-pref[me]);↵
int t4=(n+i-me)*a[me];↵
ans=min(ans,t1+t3-t2-t4);↵
}↵
cout<<ans<<endl;↵
}↵
↵
int32_t main() {↵
fastio();↵
int t = 1;↵
cin >> t;↵
while(t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
↵
