# MXMODSUM - Editorial

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() {
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
{
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 …

I have the same doubt.

for (int a: arr) {
int term = a + a[n-1] + (a - a[n-1]) % m;
maxVal = Math.max(maxVal , term);
}


Why does the above approach not work, but the lower one does? Is this related to distributive property of modulo in some way? Please advise me on this.

for (int a: arr) {
int term = a +  a[n-1] + ((a - a[n-1] ) % m + m) % m;
maxVal = Math.max(maxVal , term);
}

1 Like

For some languages, a % m can be negative if a is negative. That’s why you need to fix it (by adding m back to make it positive before modding again).

3 Likes

Update the time complexity, its not linear

been stuck here from yesterday.

The editorial explanation and the Preparer’s Solution are both linear.

What editorial is saying is "When A_i is fixed, it is always optimal to choose A_{max} as A_j". In other words, “If you brute-force A_i for A_j = A_{max}, you will find the optimal solution.”

It is not enough to search only some A_i; you must try all possibilities as A_i.

By the way,

    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);


this code is very technical and probably correct. But writing ((a[i] - a[j]) % m + m) % m is the simplest and recommended.

1 Like

Here is another solution.
I used this solution during the contest. Many others may have used this solution.

Let’s use the “division into cases” and “variable separation” techniques to remove the \mathrm{mod}.
This idea can be also applied to \mathrm{abs}(a - b), \min(a, b), \max(a, b), etc. In my experience, I often use this technique to remove \mathrm{abs}.

Before “division into cases”, pre-calculate m[i] = A[i] \, \% \, M. Let us also define f(i,j) = A[i] + A[j] + ((A[i] - A[j]) \mod M) = A[i] + A[j] + ((m[i] - m[j]) \mod M).

• Case 1: m[i] = m[j]

• f(i,j) = A[i] + A[j]
• Case 2: m[i] > m[j]

• f(i,j) = (A[i] + m[i]) + (A[j] - m[j])
• Case 3: m[i] < m[j]

• f(i,j) = (A[i] + m[i]) + (A[j] - m[j]) + M

Let us consider Case 2. For any i, we can write

• \max_{j} \{ f(i,j) \, | \, m[i] > m[j] \} = (A[i] + m[i]) + \max_{j} \{ A[j] - m[j] \, | \, m[i] > m[j] \}.

Since \max_{j} \{ A[j] - m[j] \, | \, m[i] > m[j] \} can be managed by priority_queue etc., the optimal solution of Case 2 can be obtained by processing in ascending order of m[i]. The total complexity is O(N \log N). The same is true for Case 3.

In implementation, after processing Case 1, make m[i] unique before processing Case 2 and Case 3 (leaving the larger A[i] as the tiebreaker for m[i]).

Here is my code (sorry for the mess…).
https://www.codechef.com/viewsolution/64893142