PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Primality testing
PROBLEM:
You’re given an array A. Find any pair of its elements whose sum is not prime.
EXPLANATION:
One of the easiest ways to obtain a sum that isn’t prime, is to try and make said sum even (and greater than 2, of course).
In particular, note that:
- If A contains at least two even numbers, their sum is an even number larger than 2 and hence not prime.
- If A contains at least two odd numbers, of which one is \geq 3, their sum is again an even number larger than 2.
Both above cases are easy to check.
If both checks fail, the elements of A are rather restricted in what they can be: there’s at most one even element, and the odd elements are either all 1, or there’s only odd element.
In particular, there’s at most one distinct even element, and one distinct odd element.
Let x be the even element and y be the odd element. (Note that if x doesn’t exist, we can immediately say that no valid pair exists.)
If x+y is not prime we’ve found our pair, otherwise no pair exists.
So, we only really need to perform a single primality check, and since A_i \leq 100 this will be done on a number that’s \leq 200 and hence pretty fast.
It’s possible to simplify implementation a fair bit by simply brute-forcing it.
From above, any valid pair must definitely include an element that’s \gt 1.
So,
- Fix an index i_1 such that A_{i_1} is even, and try every j from 1 to N.
- Fix an index i_2 such that A_{i_2} is odd and greater than 1, and try every j from 1 to N.
If a valid pair exists, it’ll definitely be found by checking just these two indices (to see why, go through the cases we had earlier).
This way, we need to perform at most 2N primality checks, which is not an issue since the numbers being tested are \leq 200.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
bool prime(int x){
for (int i = 2; i < x; i++){
if (x % i == 0) return false;
}
return true;
}
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
for (int x = 0; x < n; x++) if (a[x] != 1){
for (int y = 0; y < n; y++) if (y != x){
if (!prime(a[x] + a[y])){
cout << x + 1 << " " << y + 1 << "\n";
return;
}
}
}
for (int x = 0; x < n; x++) if (a[x] == 1){
for (int y = 0; y < n; y++) if (y != x){
if (!prime(a[x] + a[y])){
cout << x + 1 << " " << y + 1 << "\n";
return;
}
}
break;
}
cout << -1 << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (Python)
def prime(n):
i = 2
while i*i <= n:
if n%i == 0: return 0
i += 1
return 1
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
evens, odds = [], []
mxodd = 1
for i in range(n):
if a[i]%2 == 0: evens.append(i)
else:
odds.append(i)
mxodd = max(mxodd, a[i])
if len(evens) >= 2:
print(evens[0]+1, evens[1]+1)
elif len(odds) >= 2 and mxodd > 1:
x, y = 0, 0
while a[odds[x]] == 1: x += 1
if x == 0: y = 1
if x > y: x, y = y, x
print(min(odds[x], odds[y])+1, max(odds[x], odds[y])+1)
else:
if len(evens) == 0: print(-1)
else:
x, y = evens[0], odds[0]
if x > y: x, y = y, x
if prime(a[x] + a[y]): print(-1)
else: print(x+1, y+1)