MUNCHMOD - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: munch_01
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given an array A, find the maximum possible value of A_i \bmod (A_j + A_k) across all triplets (i, j, k) of pairwise distinct indices.

EXPLANATION:

A simple first observation is to note that A_i \bmod (A_j + A_k) can never be greater than A_i.
Either it will equal A_i itself (if A_j + A_k \gt A_i), or it will be something smaller than A_i.

This seems obvious, but is actually quite helpful - it tells us that if we fix the index i, no matter what we choose for j and k, we cannot obtain a result larger than A_i itself.

It’s now not hard to see that in almost every case, for a fixed i it’s possible to obtain A_i by choosing j and k appropriately.

To see why, let’s first sort the array for convenience, so that A_1 \leq A_2 \leq\ldots\leq A_N. This doesn’t change the answer.
Now, for any i \lt N, we can choose j = N and k to be anything (other than i or N) - the sum A_N + A_k will definitely be larger than A_i because A_N is the largest element, so we’ll always have A_i \bmod (A_N + A_k) = A_i, as we wanted.

So, among all the choices of i \lt N, the best we can do is just A_{N-1}, i.e. the second maximum element of the array.

This leaves the case of i = N.
However, here we can use the constraint of N \leq 5000, and simply iterate through all pairs of j and k to compute the maximum possible value of A_N \bmod (A_j + A_k).

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = a[-2]
    
    for i in range(n-1):
        for j in range(i+1, n-1):
            ans = max(ans, a[-1] % (a[i] + a[j]))
    print(ans)
2 Likes
2

not convinced with this proof,nvm got it now

1 Like
3

Thanks! for the editorial, it’s helped me to understand

4

include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector;
define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
define all(x) (x).begin(), (x).end()

bool exists_pair_with_sum_greater(const vll &a, int i) {
int n = a.size();
int left = 0, right = n - 1;
ll x = a[i];
while (left < right) {
if (left == i) { left++; continue; }
if (right == i) { right–; continue; }
if (a[left] + a[right] > x) return true;
else left++;
}
return false;
}

int main() {
fast_io;
int t;
cin >> t;
while (t–) {
int n;
cin >> n;
vll a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(all(a));

    ll ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (exists_pair_with_sum_greater(a, i)) {
            ans = a[i];
            break;
        }
    }

    cout << ans << '\n';
}
return 0;

}
why this fails anyone