PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Narhan Kamzabek
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium
PREREQUISITES:
Constructive, Maths
PROBLEM:
Chef has an array a_1,\ldots,a_n of n elements. Initially, all elements of the array are equal to 1. There are two types of operations.
-
1 i: Take the index i (1 \le i \le n), and multiply it by 2 (a_i := 2 \cdot a_i).
-
2 i j: Take two indexes i and j (1 \le i, j \le n, i \ne j), and subtract a_j from a_i, (a_i := a_i - a_j).
All elements must be positive after each operation, and at most 10^9.
Besides, you are given an array b. Chef wants to make b from a. Help Chef to reach the array b in no more than 43\ 000 operations, or determine it is impossible.
EXPLANATION:
The most effective way for such problems is to reverse the problem. We will try to make array A from array B by changing the operations too as:
-
Take the index i (1 \le i \le n), and divide it by 2 (b_i := b_i / 2), if b_i is divisible by 2
-
Take two indexes i and j (1 \le i, j \le n, i \ne j), and add b_j to b_i, (b_i := b_i + b_j).
Now let’ see when it’s impossible to convert all the elements of the array B into 1. We claim that:
Claim: Array B is convertible to array A only and only if the largest prime that divides all the elements of B is at most 2.
Proof
Suppose p>2 is the prime number, that divides all the elements of the array B. Then it’s possible to write all the elements of the array B in terms of multiple of p i.e B[i]=p*x_i.
Now let’s see what happens if we apply the operation 1:
- As all the prime numbers greater than 2 are odd and hence they are not divisible by 2. So if we apply the operation 1 any number of times, the resultant number can still be written in terms of multiple of p.
Let’s see what happens if we apply the operation 2:
- If we take any pair of indices i and j from the array B and apply the operation 2 on them, let’s see what is the resultant number:
We can see that the prime p will always divide every element of the array B whatever the operations we apply and hence it’s impossible to convert array B into an array A.
In all other cases, it’s always possible to convert the array B into an array A. Let’s assume that all the numbers are odd, else we would keep on dividing them by 2 until they become odd. Let’s try to find the subset whose gcd equals 1.
The length of this subset will always be less than or equal to 7.
Why
A number x can have at most 6 distinct prime factors such that x is odd and less than 10^6.
If we pick a number x into our set, then the gcd of the set is x. We will now add only those numbers in our set such that adding those numbers decreases the gcd of the set. Now the gcd can be decreased at most 6 times and hence we can add a maximum of 6 more numbers in our set.
That means that it is always possible to have a subset of size less than or equal to 7 whose gcd equals 1.
After applying operations on this set, it guarantees us that there will be 1 eventually.
How
Suppose we had two numbers x and y such that the gcd of these two numbers is g. We can make both numbers equal to g by applying the operations some number of times. Like the numbers, x and y can be represented in terms of multiples of g and since g is always odd, it won’t be possible to make a number less than g as proved above.
Now as the gcd of the subset is 1 and hence there will be 1 eventually.
A number can be halved at most logC times, and it can be replaced with average at most logC times before the next time it’s halved. Hence the number of operations that will be required to get at least one number of set 1 is at most log^2(C) * si, where si is the size of the set.
As soon as we get any element of the array B equal to 1. We can use this element to reduce all the elements of the array B to 1 as the gcd of this element with any other element of the array will be 1. This will take at most 2*N*log(C) operations.
So the total number of operations will be always less than the 43 000, hence it is always possible to convert all the elements of the array B to 1.
ALTERNATIVE SOLUTIONS:
There are some alternative simple solutions. Can you prove or disprove these solutions?
Solution 1:
Suppose all the numbers are odd, else we would keep on dividing them by 2 until they become odd. Now instead of finding a subset whose gcd equals 1, each time we take the maximum and minimum elements of the array. Let mx and mi be the maximum and minimum elements of the array respectively.
Now we perform the operations on these elements until they become equal. Eventually, they will become equal to the gcd of the mx and mi, as proved above. Can you prove that the number of operations will always be less than 43,000?
Solution 1
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
const int maxn = (int)1e4 + 12;
int n, type, a[maxn];
vector<array<int, 3> > oper;
set<pair<int, int> > vals;
inline void normalize(int i){
while(a[i] % 2 == 0) oper.push_back({1, i, -1}), a[i] /= 2;
}
int main () {
int t;
t = 1;
while(t--){
int g = 0;
oper.clear();
vals.clear();
cin >> n;
assert(1 <= n && n <= 1000);
for(int i = 0; i < n; i++){
cin >> a[i];
assert(1 <= a[i] && a[i] <= 1000000);
normalize(i);
g = __gcd(g, a[i]);
vals.insert({a[i], i});
}
if(g > 1){
puts("-1");
continue;
}
while(1){
auto it1 = *vals.begin();
auto it2 = *vals.rbegin();
if(it1.f == it2.f && it1.f == 1) break;
while(it2.f!=it1.f){
if(it2.f<it1.f)swap(it1,it2);
vals.erase(it2);
a[it2.s] = it2.f + it1.f;
//cout << it1.f << " " << it2.f << "\n";
oper.push_back({2, it2.s, it1.s});
normalize(it2.s);
it2.f = a[it2.s];
vals.insert({a[it2.s], it2.s});
//cout << it1.f << " " << it2.f << "\n";
}
}
cout << oper.size() << "\n";
reverse(oper.begin(), oper.end());
for(auto x : oper){
cout << x[0] << " " << x[1] + 1;
if(x[2] != -1) cout << " " << x[2] + 1;
cout << "\n";
}
}
}
Solution 2:
Again suppose all the numbers are odd, else we would keep on dividing them by 2 until they become odd.
In this solution, we try to perform the operations until all the elements of the array B become 1. In this case, we take the first element of the array B and then for every index i=2,3,\dots, N of the array B, we perform the operations until B[1] and B[i] becomes equal. By performing operations many number of times they will become equal to gcd of B[1] and B[i], as proved above.
Solution 2
#include <bits/stdc++.h>
//#include "testlib.h"
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
using namespace std;
const int maxn = (int)2e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7;
const double pi = acos(-1.0);
#define inf (int)2e9
#define INF (ll)1e18
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef array<int, 3> triple;
int n, a[maxn], g;
vector<triple> oper;
inline void add(int type, int x, int y){
oper.pb({type, x, y});
}
inline void normalize(int pos){
while(a[pos] % 2 == 0) a[pos] /= 2, add(1, pos, -1);
}
void solve(){
oper.clear();
cin >> n;
g = 0;
int l = (1 << 19);
forn(i, 1, n){
cin >> a[i];
normalize(i);
g = __gcd(g, a[i]);
}
if(g > 1){
cout << "-1\n";
return;
}
g = 0;
while(1){
bool bad = 0;
forn(i, 1, n)
if(a[i] > 1)
bad = 1;
if(!bad) break;
forn(j, 1, n){
int i = 1;
while(a[i] != a[j]){
if(a[i] < a[j]) swap(i, j);
a[i] += a[j];
add(2, i, j);
normalize(i);
}
}
}
cout << sz(oper) << "\n";
reverse(all(oper));
for(auto x : oper){
cout << x[0] << " " << x[1];
if(x[2] != -1) cout << " " << x[2];
cout << "\n";
}
}
int main () {
int t = 1;
while(t--) solve();
}
TIME COMPLEXITY:
O(N*log(C) + log^2(C))
SOLUTIONS:
Setter
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ll long long
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
using namespace std;
const int maxn = (int)2e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int) 1e6 + 7;
const double pi = acos(-1.0);
#define inf (int)2e9
#define INF (ll)1e18
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef array<int, 3> triple;
int n, a[maxn], g;
vector<triple> oper;
inline void add(int type, int x, int y){
oper.pb({type, x, y});
}
inline void normalize(int pos){
while(a[pos] % 2 == 0) a[pos] /= 2, add(1, pos, -1);
}
void solve(){
oper.clear();
cin >> n;
g = 0;
forn(i, 1, n){
cin >> a[i];
normalize(i);
g = __gcd(g, a[i]);
}
if(g > 1){
cout << "-1\n";
return;
}
g = 0;
vi good; // set of numbers with gcd = 1
forn(i, 1, n){
int base = 1, x = a[i];
for(int p = 2; p * p <= x; p++){
if(x % p == 0){
while(x % p == 0) x /= p;
base *= p;
}
}
if(x > 1) base *= x;
if(!g){
g = base;
good.pb(i);
}
if(__gcd(g, base) < g){
g = __gcd(g, base);
good.pb(i);
}
if(g == 1) break;
}
assert(g == 1);
assert(sz(good) <= 7);
while(1){
int mx = -1, mn = -1;
for(auto pos : good){
if(mx == -1 || a[mx] < a[pos])
mx = pos;
if(mn == -1 || a[mn] > a[pos])
mn = pos;
}
if(a[mx] == 1) break;
while(a[mn] != a[mx]){
if(a[mx] < a[mn]) swap(mx, mn);
a[mx] += a[mn];
add(2, mx, mn);
normalize(mx);
}
}
forn(i, 1, n){
if(a[i] == 1) continue;
while(a[i] > 1){
add(2, i, good[0]);
a[i]++;
normalize(i);
}
}
cout << sz(oper) << "\n";
reverse(all(oper));
for(auto x : oper){
cout << x[0] << " " << x[1];
if(x[2] != -1) cout << " " << x[2];
cout << "\n";
}
}
int main () {
int t = 1;
while(t--) solve();
}
Tester
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
struct op {
int ty, i, j;
};
// about 2 log^3 C + 2n log C operations
void solve() {
int n;
cin >> n;
vi b(n + 1);
ll g = 0;
vector<int> pos;
vector<op> ops;
auto add = [&](int i, int j) {
b[i] += b[j];
ops.push_back({2, i, j});
};
auto div2 = [&](int i) {
b[i] /= 2;
ops.push_back({1, i});
};
rep(i, 1, n + 1) {
cin >> b[i];
while(b[i] % 2 == 0) div2(i);
ll g2 = gcd(g, b[i]);
if(g2 != g) {
g = g2;
pos.push_back(i);
}
}
if(g != 1) {
cout << -1 << '\n';
return;
}
int idx = 0;
for(int i = 1; i < sz(pos); i++) {
ll d = gcd(b[pos[idx]], b[pos[i]]);
while(b[pos[idx]] != d && b[pos[i]] != d) {
if(b[pos[idx]] % 2 == 0) div2(pos[idx]);
else if(b[pos[i]] % 2 == 0) div2(pos[i]);
else if(b[pos[idx]] < b[pos[i]]) add(pos[i], pos[idx]);
else add(pos[idx], pos[i]);
}
if(b[pos[i]] == d) idx = i;
}
rep(i, 1, n + 1) {
while(b[i] != 1) {
if(b[i] % 2 == 0) div2(i);
else add(i, pos[idx]);
}
}
reverse(all(ops));
cout << sz(ops) << '\n';
for(auto &o : ops) {
cout << o.ty << ' ' << o.i;
if(o.ty == 2) cout << ' ' << o.j;
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct operation{
int type;
int ind1;
int ind2;
};
void solve()
{
int n;
cin>>n;
int a[n];
vector <operation> ans;
int g=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
while(a[i]%2==0){
a[i]/=2;
operation o1;
o1.type=1;
o1.ind1=i+1;
o1.ind2=-1;
ans.push_back(o1);
}
g=__gcd(a[i],g);
}
if(g!=1)
{
cout<<-1<<"\n";
return;
}
vector <int> num_set;
g=0;
for(int i=0;i<n;i++)
{
int pr=1;
int temp=a[i];
for(int p=2;p*p<=temp;p++)
{
if(temp%p==0)
{
while(temp%p==0)
temp/=p;
pr*=p;
}
}
if(temp>1)
pr*=temp;
if(!g)
{
g=pr;
num_set.push_back(i);
}
if(__gcd(g,pr)<g)
{
g=__gcd(g,pr);
num_set.push_back(i);
}
}
for(int i=1;i<num_set.size();i++)
{
int j=num_set[0],k=num_set[i];
while(a[j]!=a[k])
{
while(a[j]%2==0)
{
a[j]/=2;
operation o1;
o1.type=1;
o1.ind1=j+1;
o1.ind2=-1;
ans.push_back(o1);
}
while(a[k]%2==0)
{
a[k]/=2;
operation o1;
o1.type=1;
o1.ind1=k+1;
o1.ind2=-1;
ans.push_back(o1);
}
if(a[j]<a[k])
{
a[k]+=a[j];
operation o1;
o1.type=2;
o1.ind1=k+1;
o1.ind2=j+1;
ans.push_back(o1);
}
else if(a[j]>a[k])
{
a[j]+=a[k];
operation o1;
o1.type=2;
o1.ind1=j+1;
o1.ind2=k+1;
ans.push_back(o1);
}
}
}
int ind=num_set[0];
for(int i=0;i<n;i++)
{
while(a[i]!=1)
{
if(a[i]%2==0)
{
a[i]/=2;
operation o1;
o1.type=1;
o1.ind1=i+1;
o1.ind2=-1;
ans.push_back(o1);
}
else
{
a[i]+=1;
operation o1;
o1.type=2;
o1.ind1=i+1;
o1.ind2=ind+1;
ans.push_back(o1);
}
}
}
reverse(ans.begin(),ans.end());
cout<<ans.size()<<"\n";
for(auto itr: ans)
{
cout<<itr.type<<" "<<itr.ind1<<" ";
if(itr.ind2!=-1)
cout<<itr.ind2;
cout<<"\n";
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}