MXMODSUM - Editorial

editorial
, , , ,
21

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
22

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
23

Update the time complexity, its not linear

24

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

25

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

26

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
27

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

28

i will try to clear my question in a better way.
in my code, i am calculating the value of mod1,mod2,mod3,mod 4 using findMod function.
for each variable, the findMod function should get executed.
but when i tried to debugg, some weird things were happening.

for example:-
for test case 2, only mod1 and mod4 were calculated.
and for 4 only mod 4 was calculated.

now when i run it again, that issue is not happening. so i guess issue was with my ide

29

why fixing A[i] to be Amax is not same as fixing A[j] to be Amax?
More formally why taking (A[i]-Amax )mod m is better than (Amax-A[i])mod m when either of them can be greater?
Edit- I understood
this is when res=( Amax -A[i]) mod m
// a[i]=29,a[n]=80,res=3
// a[i]=58,a[n]=80,res=2
// a[i]=79,a[n]=80,res=1 --notice
// a[i]=80,a[n]=80,res=0
// a[i]=80,a[n]=80,res=0
// 160
this is when res=( A[i]-Amax) mod m
a[i]=29,a[n]=80,res=1
a[i]=58,a[n]=80,res=2
a[i]=79,a[n]=80,res=3 --notice
a[i]=80,a[n]=80,res=0
a[i]=80,a[n]=80,res=0
162
Here we can observe more the value is closer to maximum ,answer of A[i]-Amax would be bigger while than Amax-A[i] will get smaller. Hence Amax + closer value +with (A[i]-Amax)mod m would give higher output.

1 Like