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

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

@demystify can you help please.
been stuck here from yesterday.

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

I’m sorry but I could not understand your question. However, I have a few comments that may help you.

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