In this HackerEarth Arrays problem solution Mike has 3 arrays a,b,c of length n and a number k. He wants to find minimal value of max(i=1,n) (((ai + t) mod k) K ((bi + t) mod k) + ((ci + t) mod k)). over all non-negative integer values of t.


HackerEarth Arrays problem solution


HackerEarth Arrays problem solution.

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
const int N = (int)(1e6) + 5;
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int s[N][3];
vi q[N][3];
int cnt[N];
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;++i)
for (int j = 0;j < 3;++j)
scanf("%d",&s[i][j]);
vi ss;
for (int i = 1;i <= n;++i)
for (int j = 0;j < 3;++j)
ss.pb(m - s[i][j]);
ss.pb(0);
sort(all(ss));
ss.resize(unique(all(ss)) - ss.begin());
for (int i = 1;i <= n;++i)
for (int j = 0;j < 3;++j)
q[lower_bound(all(ss),m - s[i][j]) - ss.begin()][j].pb(i);
for (int i = 1;i <= n;++i)
for (int j = 0;j < 3;++j)
cnt[i] += s[i][j];
multiset < int , greater < int > > w;
for (int i = 1;i <= n;++i)
w.insert(cnt[i]);
int ans = *w.begin();
int sz = ss.size();
for (int i = 1;i < sz;++i)
{
for (int j = 0;j < 3;++j)
for (auto it : q[i][j])
{
w.erase(w.find(cnt[it]));
cnt[it] -= m;
w.insert(cnt[it]);
}
ans = min(ans,*w.begin() + 3 * ss[i]);
}
cout << ans << '\n';
return 0;
}

Second solution

#include"bits/stdc++.h"
using namespace std;

#define MAX 300002

int n;
int k;

vector<pair<int,int> > ev;
vector<long long int> A;
vector<long long int> B;
vector<long long int> C;

long long int val(int idx, long long int t) {
long long int r = (A[idx] + t) % k;
r += (B[idx] + t) % k;
r += (C[idx] + t) % k;
return r;
}

priority_queue<pair<long long int, int> > q;

long long int calc(int idx) {
long long int ans = -1;
for (int i = 0; i < A.size(); i++) {
ans = max(ans, val(i,idx));
}
return ans;
}
long long int res_val[MAX];

int main() {
cin >> n >> k;
assert(n<=300000);
assert(n>=1);
assert(k<=100000000);
assert(k>=1);
for (int i = 0; i < n; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
int dist1 = k - a;
int dist2 = k - b;
int dist3 = k - c;
ev.push_back(make_pair(dist1, i));
ev.push_back(make_pair(dist2, i));
ev.push_back(make_pair(dist3, i));
A.push_back(a);
B.push_back(b);
C.push_back(c);
res_val[i] = val(i,0);
q.push(make_pair(res_val[i], i));
}
sort(ev.begin(), ev.end());
long long int C = calc(0);
long long int ans = LLONG_MAX;
for (int i = 0; i < ev.size(); i++) {
long long int c = val(ev[i].second, ev[i].first);
res_val[ev[i].second] = c - ev[i].first * 3LL;
q.push(make_pair(res_val[ev[i].second], ev[i].second));
while (!q.empty()) {
int b = q.top().second;
long long int val = q.top().first;
if (res_val[b] != val) {
q.pop();
continue;
}
break;
}
C = min(C, q.top().first+ev[i].first*3LL);
}
assert(C>=0);
printf("%lld\n", C);
return 0;
}//