the time complexity of your approach is O(n*n) so it will get TLE
why we have calculate mod like this (((a[i]+ma[n]%m)%m;)) ??
can’t we simply write ((a[i]+a[n]  (a[n])a[i])%m)) ?
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,n2,n1,m);
ll mod2=findMod(arr,n1,n2,m);
ll mod3=findMod(arr,n1,0ll,m);
ll mod4=findMod(arr,0ll,n1,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 +(M1) (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.
issue with mod calculation:
lets say you have a[i]=3,a[j]=7 and m=9;
then there are two possible cases:
(37)%9 =5 and (73)%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]
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
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
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;
}
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[n1];
if( def < 0) def = m  ((a[n1]  a[i]) % m );
else def = (a[i]  a[n1]) % m;
sum =a[i] + a[n1] + 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[n1] + (a  a[n1]) % 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[n1] + ((a  a[n1] ) % m + m) % m;
maxVal = Math.max(maxVal , term);
}
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).
Update the time complexity, its not linear
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 bruteforce 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.
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”, precalculate 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