MXMODSUM - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: TheScrasse
Tester: Harris Leung
Editorialist: Trung Dang

DIFFICULTY:

1370

PREREQUISITES:

None

PROBLEM:

You are given an array A containing N integers, and a positive integer M. Find the maximum value of

A_i + A_j + ((A_i - A_j) \bmod M)

across all pairs 1 \leq i, j \leq N.

EXPLANATION:

Note that the quantity A_j + ((A_i - A_j) \bmod M) has a specific meaning: it is the smallest value larger or equal to A_j that is congruent to A_i modulo M. From this meaning, we see that regardless of our choice of A_i, our best choice of A_j is going to be the largest value in A. Therefore, the solution is just to loop over A_i, while having \max_A as A_j.

TIME COMPLEXITY:

Time complexity is O(N) per test case.

SOLUTION:

Preparer's Solution
for _ in range(int(input())):
	N, M = map(int, input().split())
	a = list(map(int, input().split()))
	mx = max(a)
	print(max([x + mx + (x - mx)%M for x in a]))
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n;
ll m;
ll a[500001];
void solve(){
	cin >> n >> m;
	for(int i=1; i<=n ;i++) cin >> a[i];
	sort(a+1,a+n+1);
	ll ans=-1e18;
	for(int i=1; i<=n ;i++){
		ll res=(a[i]+m-a[n]%m)%m;
		ans=max(ans,a[i]+a[n]+res);
	}
	cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(false);
	int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n, m; cin >> n >> m;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = max(ans, a[i] + a[n - 1] + ((a[i] - a[n - 1]) % m + m) % m);
        }
        cout << ans << '\n';
    }
}
1 Like

Can someone please elaborate more, why A[j] is Amax ??

6 Likes

Meaning: it is the smallest value larger or equal to Aj that is congruent to Ai modulo M
Can anyone elaborate this?

Because j = n-1.

If you look at the code, you can see that the list is sorted prior to all the calculations. So the biggest value is at the end of the list, at index n-1.

I think the confusion comes from not distinguishing between the mathematical formula and the actual code. It’s not that some random A[j] = Amax, but we want A_j in the mathematical formula to be the max value. We choose A_j to be the max value. And the max value is at the end of the list, because it gets sorted.

I hope that helps :slight_smile:

1 Like

If you have fixed A_i, then you know what mod A_j + (A_i - A_j) \bmod M should have. Suppose you take A_j that is smaller than A_{max}, then there is no way the next value of A_j should be larger than the next value of A_{max}, since you have fixed which modulo this next value should land in.

Let’s take a concrete example. Say A_i = 3, A_j = 9 and M = 5. Then A_j + (A_i - A_j) \bmod M is the smallest value larger or equal to 9 that has modulo 3 when divided by 5 (the answer is 13).

2 Likes

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

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n;
int m;
cin>>n>>m;
int a[n];
int mx=INT_MIN;
sort(a,a+n);
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
{
int mod=abs((a[i]-a[j])%m);
int restcalculation=a[i]+a[j]+mod;
mx=max(mx,restcalculation);
}
}
cout<<mx<<endl;

}
return 0;

}
i got some test cases wrong can you help me with my approach

the time complexity of your approach is O(n*n) so it will get TLE

1 Like

why we have calculate mod like this (((a[i]+m-a[n]%m)%m;)) ??
can’t we simply write ((a[i]+a[n] - (a[n])-a[i])%m)) ?

1 Like

can you please tell me why only some of the mod variables(mod1,mod2,mod3,mod4) getting calculated? when i tried debugging , i noticed that only 1 or 2 of those lines are getting calculated in my code.

#include"bits/stdc++.h"
#define ll long long int
#define MOD 1000000007
using namespace std;


ll findMod(vector<ll> &arr,ll i,ll j,ll m)
{
    if(arr[i]-arr[j]>=0)
    {
        return (arr[i]+arr[j]+  ((arr[i]-arr[j])%m));
    }


    ll thirdTerm;
    if(abs(arr[i]-arr[j])%m==0)
      thirdTerm=0;
    else
      thirdTerm= arr[i]-arr[j]+ m*( (abs(arr[i]-arr[j])/m)+1);

    return (arr[i]+arr[j] + thirdTerm);
}

int main()
{
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m;
        cin>>n>>m;
        vector<ll> arr(n);
        for(ll i=0;i<n;i++)
        {
            cin>>arr[i];
        }

        sort(arr.begin(),arr.end());

        
        ll mod1=findMod(arr,n-2,n-1,m);
        ll mod2=findMod(arr,n-1,n-2,m);
        ll mod3=findMod(arr,n-1,0ll,m);
        ll mod4=findMod(arr,0ll,n-1,m);


        cout<<max(mod1,max(mod2,max(mod3,mod4)))<<endl;

    }
    return 0;
}

Write my thoughts here.
(I think this is the simplest way of thinking)

  • Aj + ((Ai - Aj) mod M)

Let’s increase Aj by 1.

  • (left side) : always +1
  • (right side) : -1 or +(M-1) (when Ai=Aj mod M)

By considering the left side and the right side together,
you can see that there is no loss in increasing Aj.
(Because the change is always 0 or +M)

Therefore, it is best to use Amax for Aj.

1 Like

issue with mod calculation:
lets say you have a[i]=3,a[j]=7 and m=9;
then there are two possible cases:
(3-7)%9 =5 and (7-3)%9=4

so one of the mod value is greater than other(may be equal)
your mod calculation works wrongly when a[i]<a[j]

1 Like

Why the test case as following:

N=4 M=18
A=[3, 3, 3, 3]

not included
some solutions have passed not considering the above mentioned test case

for example, this solution:
https://www.codechef.com/viewsolution/64900842

3 Likes

Weak test case

Track only the biggest and second biggest numbers. Even a sorting is not needed.

It passes, but should not: Solution: 64979357 | CodeChef
Correct implementation: Solution: 64981354 | CodeChef

Your code fails for the test case mentioned by @aryan_sinha .

2 Likes

Oh, thanks for pointing it out. I have updated the comment

Yeah not needed

why it is partially accept

can someone tell me what is wrong with it

#include <bits/stdc++.h>

using namespace std;

int main() {
// your code goes here
int tt;
cin>>tt;
int maxi=0;
while(tt–){
int n,m;
cin>>n>>m;

    if(m>=1000 && m<=2){
        continue;
    }
    
    int arr[n];
    maxi=0;
    
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    
    for(int i=0;i<n;i++){
        int first=arr[i];
        for(int j=0;j<n;j++){
            int second=arr[j];
            int mod= ((first % m) - (second % m) + m)% m;
            int mini=first+second+mod;
            
            
            maxi=max(maxi,mini);
        }
    }
    cout<<maxi<<endl;
    
}

return 0;

}

1 Like
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner sc = new Scanner (System.in);
		int t = sc.nextInt();
		while(t!=0){
		    int n = sc.nextInt();
		    int m = sc.nextInt();
		    int [] a = new int [n];
		    for(int i=0;i<n;i++){
		        a[i] = sc.nextInt();
		    }
		    int def=0,sum=0, max=0;
		    for(int i=0;i< n -1;i++){
		        def =a[i] - a[n-1];
		        if( def < 0) def = m - ((a[n-1] - a[i]) % m );
		        else def = (a[i] - a[n-1]) % m;
		        sum =a[i] + a[n-1] +  def;
		        if(sum>max) max = sum;
		    }
		    System.out.println(max);
		    t--;
		}
	}
}

This gave me the output but the test cases failed …