HackerEarth Arrays problem solution

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.

#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("%lldn", C);
    return 0;
}//

coding problems