1
\$\begingroup\$

Question- enter image description here

My approach

I noticed that the minimum of a row is when t=k-one of the numbers of that row. Suppose in the above sample case, t=4 which is 6-2. Since we have to find the minimum maximum testing all k-no will give the solution. Any tips to improve this technique as for cases where each number is unique and number of rows is high this will become slow?

  • plus stores unique k-no
  • curmax stores the current maximum for the current 't'.
  • ans is the minimum of all those maximums.

Code

#include<iostream>
#include<set>
using namespace std;
int main()
{
    set<int>plus;
    int n,k;
    cin>>n>>k;
    int a[n],b[n],c[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        plus.insert(k-a[i]);
        plus.insert(k-b[i]);
        plus.insert(k-c[i]);
    }
    int ans=1000000000,curmax=-1,tempsum;
    for(auto x:plus)
    {
        curmax=-1;
        for(int i=0;i<n;i++)
        {
            tempsum=(a[i]+x)%k+(b[i]+x)%k+(c[i]+x)%k;
            if(tempsum>curmax)
                curmax=tempsum;
        }
        if(curmax<ans)
            ans=curmax;
    }
    cout<<ans;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.