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: CodeChef: Practical coding for everyone
Correct implementation: CodeChef: Practical coding for everyone
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
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