PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: arbitrary_aman
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
3145
PREREQUISITES:
None
PROBLEM:
You’re given an array A of length N.
Some elements of A are -1's.
An array is called special if its elements are distinct positive integers, and (A_i + A_j + A_k) is not a multiple of 5 for any 1 \leq i \lt j \lt k \leq N.
Find a way to turn A into a special array by replacing the -1's, or claim that this is impossible.
If it is possible, find also the minimum possible sum of such an array.
EXPLANATION:
Let’s analyze the structure of a special array.
The elements being distinct aside, to check the divisibility by 5 condition clearly we can just replace each element by its remainder modulo 5.
Let c_i be the number of elements with remainder i (modulo 5) in the array.
Henceforth, all arithmetic between elements of the array will be modulo 5 (so “summing to 0” really means "summing to a multiple of 5).
Then, we make the following observations:
- c_0 \leq 2, otherwise we have three zeros and can add them to get 0, not allowed.
- If c_x \gt 1 for some x \neq 0, then -2x (modulo 5) can’t occur in the array at all, i.e, c_{-2x} = 0 should hold.
Observe that this gives us a ‘cycle’ of the form 1\to 3\to 4\to 2\to 1, where for each element, if it occurs more than once in the array then its successor can’t appear at all. - If x+y+z = 0, and x, y, z are all distinct, then one of them has to be a 0.
This is easily verified by noting that no three among \{1, 2, 3, 4\} sum to 0. - If x+y+z = 0, then x=y=z is impossible unless x = 0.
So, there are only two constraints we really need to care about:
- The first is the condition given by the 1\to3\to4\to2\to1 cycle, where if one of them occurs more than once its successor can’t occur at all.
This covers the case when x+y+z = 0, and two of them are equal. - The second is when c_0\gt 0, in which case we also have to ensure that 0+2+3 and 0+1+4 don’t occur either.
Of course, c_0 \leq 2 should still hold.
This gives us a few different types for what a special array can look like.
Let’s go over them all.
First, let’s consider c_0 \gt 0.
Without loss of generality, suppose c_1 \gt 1 as well.
Then, note that:
- 3 can’t appear at all, being the successor of 1.
- 4 can’t appear at all, otherwise we’d have 0+1+4.
- 2 can appear at most once, since 1 is the successor of 2.
So, we have (at most) two occurrences of 0, at most one occurrence of 2, and everything else should be 1.
The same applies if we chose some x \neq 1 as well: 0 appears at most twice, its predecessor can appear at most once, and it must take all the rest.
If this non-zero x is fixed, constructing a valid array with minimum sum is easy: keep picking the smallest integer not already in A that ensures that these conditions are satisfied.
Next, let’s look at c_0 = 0.
Once again, wlog let c_1 \gt 1.
Then, we have some constraints:
- 3, the successor of 1, can’t appear at all.
- 2, the predecessor of 1, can appear at most once.
- If 2 appears once, its own predecessor 4 can appear at most once.
- If 2 doesn’t appear, there are no constraints on 4: it can appear as many times as we like.
So, there are two options:
- Every element is either 1 or 4; or
- There’s a 2, at most one 4, and everything else is 1.
This is easily extended to any non-zero x other than 1 as well.
Once again, if the ‘type’ of the answer is fixed, constructing an answer is not hard: keep picking the minimum valid element.
Try every case, then output the minimum answer among each valid array constructed.
There’s a lot of symmetry among cases, so though it might seem daunting, the implementation is simplified a lot if you make your code a bit modular.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f(ll i)
{
ll j = (-2*i)%5;
return (j+5)%5;
}
ll rem0(set<ll> &original_elements, vector<ll>& freq, ll r, ll k, ll n, ll sum) // f(r) can occur more than once, r can occur at max once
{
if(freq[r]>1) return -1;
if(freq[f(f(r))] || freq[f(f(f(r)))]) return -1;
vector<ll> new_elements;
if(freq[0]==0)
{
new_elements.push_back(5);
new_elements.push_back(10);
}
else if(freq[0]==1)
{
if(original_elements.count(5)==1)
new_elements.push_back(10);
else
new_elements.push_back(5);
}
if(freq[r]==0)
new_elements.push_back(r);
ll fr=f(r);
for(ll times=1; times<=min(n, 2LL); times++)
new_elements.push_back((times-1)*5+fr);
sort(new_elements.begin(), new_elements.end());
for(ll times=min(n, 2LL)+1; times<=n; times++)
new_elements.push_back((times-1)*5+fr);
for(int i=0; i<new_elements.size() && k>0; i++)
{
if(original_elements.count(new_elements[i])==1)
continue;
sum+=new_elements[i];
k--;
}
return sum;
}
ll diagonal_only(set<ll> &original_elements, vector<ll>& freq, ll r, ll k, ll n, ll sum) // only r and f(f(r)) can occur
{
if( r > f(f(r))) return -1;
if(freq[f(r)] || freq[f(f(f(r)))] || freq[0]) return -1;
vector<ll> new_elements;
for(ll times=1; times<=n; times++)
{
new_elements.push_back((times-1)*5+r);
new_elements.push_back((times-1)*5+f(f(r))); // r < f(f(r)) to maintain ascending order
}
for(int i=0; i<new_elements.size() && k>0; i++)
{
if(original_elements.count(new_elements[i])==1)
continue;
sum+=new_elements[i];
k--;
}
return sum;
}
ll unimajority(set<ll> &original_elements, vector<ll>& freq, ll r, ll k, ll n, ll sum) // only r and f(f(r)) can occur
{
if(freq[f(r)] || freq[0] || freq[f(f(r))]>1 || freq[f(f(f(r)))]>1) return -1;
vector<ll> new_elements;
new_elements.push_back(r);
if(freq[f(f(f(r)))]==0)
new_elements.push_back(f(f(f(r))));
else if(freq[f(f(r))]==0)
new_elements.push_back(f(f(r)));
sort(new_elements.begin(), new_elements.end());
for(ll times=2; times<=n; times++)
new_elements.push_back((times-1)*5+r);
for(int i=0; i<new_elements.size() && k>0; i++)
{
if(original_elements.count(new_elements[i])==1)
continue;
sum+=new_elements[i];
k--;
}
return sum;
}
ll (*cases[3])(set<ll> &, vector<ll>& , ll, ll, ll, ll) = {rem0, diagonal_only, unimajority};
ll allcases(vector<ll>& arr, ll n)
{
set<ll> original_elements;
vector<ll> freq(5);
ll sum=0, k=0;
bool repition=false;
for(auto &x : arr)
{
if(x!=-1)
{
freq[x%5]++;
if(original_elements.count(x)==1)
repition=true;
original_elements.insert(x);
sum+=x;
}
else
k++;
}
if(repition) return -1;
if(freq[0] >=3) return -1;
for(int i=1; i<5; i++)
{
if(freq[i] && freq[f(f(i))] && freq[0]) return -1;
if(freq[i]>=2 && freq[f(i)]) return -1;
}
ll final_ans=-1;
for(int i=0; i<3; i++)
{
for(int r=1; r<5; r++)
{
ll temp=cases[i](original_elements, freq, r, k, n, sum);
if(temp==-1) continue;
if(final_ans==-1)
final_ans=temp;
else
final_ans=min(final_ans, temp);
}
}
return final_ans;
}
void solve()
{
ll n; cin>>n;
vector<ll> arr(n);
for(auto &x : arr)
cin>>x;
cout<<allcases(arr, n)<<endl;
}
int main()
{
int t; cin>>t;
while(t--)
solve();
return 0;
}
Editorialist's code (Python)
successor = [0, 3, 1, 4, 2]
predecessor = [0, 2, 4, 1, 3]
def check(a):
freq = [0]*5
for k in a:
freq[k % 5] += 1
if freq[0] > 2: return False
if freq[0] > 0:
if freq[1] > 0 and freq[4] > 0: return False
if freq[2] > 0 and freq[3] > 0: return False
for k in range(1, 5):
if freq[k] > 1 and freq[successor[k]] > 0: return False
return True
def calc(x, a, type):
s = set(a)
s.discard(-1)
afreq = [0]*5
for y in a:
if y != -1: afreq[y%5] += 1
ptr, cur = 0, 1
n = len(a)
while ptr < n and a[ptr] == -1:
if cur in s:
cur += 1
continue
if cur%5 == 0 and type == 0:
if afreq[0] < 2:
a[ptr] = cur
ptr += 1
afreq[0] += 1
if cur%5 == x:
a[ptr] = cur
ptr += 1
if cur%5 == predecessor[x] and type != 2:
if afreq[predecessor[x]] == 0:
a[ptr] = cur
afreq[predecessor[x]] = 1
ptr += 1
if cur%5 == successor[successor[x]]:
if type == 2:
a[ptr] = cur
ptr += 1
elif type == 1 and afreq[successor[successor[x]]] == 0:
a[ptr] = cur
ptr += 1
afreq[successor[successor[x]]] = 1
cur += 1
if check(a): return sum(a)
return 10**18
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 10**18
for x in range(1, 5):
ans = min(ans, calc(x, a[:], 0))
ans = min(ans, calc(x, a[:], 1))
ans = min(ans, calc(x, a[:], 2))
if ans > 10**17: print(-1)
else: print(ans)