PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: utkarsh_25dec
Testers: iceknight1093, mexomerf
Editorialist: iceknight1093
DIFFICULTY:
2650
PREREQUISITES:
None
PROBLEM:
You are given an array A. In one move, you can pick i \lt j and set both A_i and A_j to A_i + A_j.
Find the minimum number of moves to make every element divisible by 3.
EXPLANATION:
Clearly, only the value of each element modulo 3 matters.
So, take every element modulo 3: now we have to deal with only arrays consisting of 0, 1, 2, and our objective is to make everything 0.
Combining a 1 and a 2 gets us two zeros, which is nice: we’d like to do this as much as possible.
In fact, this is the only way to get zeros from two non-zero numbers, so we’d like to set things up to have as many zeros as possible.
In particular, it’d be nice if the number of 1's and 2's was close to equal.
Note that combining two 1's gets us two 2's, and vice versa.
So, if the difference between the number of 1's and 2's is very large, we can use this to bring their numbers closer together.
In particular, if there are x ones and y twos, then as long as |x-y| \geq 3, performing this move appropriately is optimal since it reduces the difference by at least 2.
Now we’re left with only |x-y| \leq 2. For convenience, let’s assume x \leq y.
Deal with each case separately.
x = y
Nothing more needs to be done: we simply perform x moves to bring everything to 0.
y = x+1
There are two cases to consider here: x = 0 and x \gt 0.
If x = 0, we have an array of the form [2, 0, 0, 0, \ldots, 0].
Working this by hand, you can see it takes 6 moves.
If x \gt 0, in particular there is at least one 1 in the array.
Combine a 1 and a 2 till you reach the array [1, 2, 2, 0, 0, 0, \ldots, 0].
Now, instead of forming two more zeros, first convert it to [1, 2, 2, 1, 0, \ldots, 0], which can then be solved in two moves: this is optimal, and uses x+2 moves.
y = x+2
Again, there are a couple of minor special cases to consider.
If x \geq 2, then we can bring the array to the state [1, 2, 2, 2, 0, 0, \ldots, 0], then use 2 moves to make it [1, 2, 2, 2, 1, 1, 0, \ldots, 0], after which we need 3 moves move; for a total of x+4 moves.
In fact, the above method only needs one free position (and x \geq 1), since we can perform the moves [1, 2, 2, 2, 0, \ldots] \to [1, 2, 2, 2, 1, \ldots] \to [0, 0, 2, 2, 1, \ldots] \to [0, 1, 2, 2, 1, \ldots], which still takes a total of x+4 moves.
The only remaining cases are:
- x = 0, when we have [2, 2, 0, 0, \ldots, 0]; which needs 5 moves
- x = 1 and no free position, i.e, the array [1, 2, 2, 2]. This needs 6 moves.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Setter's code (C++)
//Utkarsh.25dec
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int sumN=0;
void solve()
{
int n=readInt(4,100000,'\n');
sumN+=n;
assert(sumN<=200000);
int A[n+1];
int one=0,two=0;
for(int i=1;i<=n;i++)
{
if(i==n)
A[i]=readInt(1,100000,'\n');
else
A[i]=readInt(1,100000,' ');
A[i]%=3;
if(A[i]==1)
one++;
else if(A[i]==2)
two++;
}
int ans=0;
if(one>two)
swap(one,two);
if(one==0 && two==0)
{
cout<<0<<'\n';
return;
}
if(one+two == n)
{
one--;
two--;
ans++;
}
if(one==0 && two==1)
{
ans+=2;
two=3;
}
else if(one==0 && two==2)
{
ans++;
two=3;
}
int diff=abs(one-two);
while(true)
{
if(diff<=2)
break;
ans++;
diff-=4;
}
diff=abs(diff);
ans+=diff;
int cnt=one+two+diff;
ans+=(cnt/2);
cout<<ans<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,1000,'\n');
while(T--)
solve();
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int ans = 0;
int a[3] = {}, temp;
for (int i = 0; i < n; i++)
{
cin >> temp;
temp %= 3;
a[temp]++;
}
if (a[1] > a[2])
{
swap(a[1], a[2]);
}
while (abs(a[2] - a[1]) > 2)
{
a[1] += 2;
a[2] -= 2;
ans++;
}
if (a[1] > a[2])
{
swap(a[1], a[2]);
}
if (a[1])
{
a[0] += 2 * (a[1] - 1);
a[2] -= a[1] - 1;
ans += a[1] - 1;
a[1] = 1;
while(a[2] > a[1] && a[0] > 0){
a[1]++;
a[0]--;
ans++;
}
a[0] += 2 * (a[1] - 1);
a[2] -= a[1] - 1;
ans += a[1] - 1;
a[1] = 1;
while(a[2] > a[1] && a[0] > 0){
a[1]++;
a[0]--;
ans++;
}
ans += a[1];
a[0] += 2 * a[1];
a[2] -= a[1];
a[1] = 0;
}
if (a[2])
{
ans += 7 - a[2];
}
cout << ans << "\n";
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
for i in range(n): a[i] %= 3
x, y = a.count(1), a.count(2)
x, y = min(x, y), max(x, y)
ans = 0
while y >= x + 3:
ans += 1
x += 2
y -= 2
x, y = min(x, y), max(x, y)
if y == x+1:
if x > 0: ans += 2
else: ans += 6
if y == x+2:
if x > 1 or (x > 0 and x+y < n): ans += 4
else: ans += 5
print(ans + x)