PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Le Duc Minh, Nguyen Anh Quân
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh
DIFFICULTY:
Medium
PREREQUISITES:
Pigeonhole Principle, Graphs
PROBLEM:
You are given a full binary tree of height n rooted at 1. A positive integer a_i is written on node i.
A primeful cycle is a set of k > 2 nodes x_1, x_2, \dotsc, x_k such that
- k is a prime number
-
gcd(a_{x_1}, a_{x_2}) \text{ mod } k = gcd(a_{x_2}, a_{x_3}) \text{ mod } k = \dotsc = gcd(a_{x_k}, a_{x_1}) \text{ mod } k
The height of a node is defined to be the number of nodes visited on the path from it to the root, including itself. So, the height of the root is 1.
The beauty value of a primeful cycle is the sum of heights of the nodes in it.
You are given q queries, each being a node x. Find out the minimum possible beauty value of a primeful cycle considering only nodes in the subtree of x - or state that a primeful cycle doesn’t exist.
EXPLANATION:
First, we prove a couple of lemmas.
Lemma 1: Given any 7 nodes, some 3 of them form a primeful cycle.
Proof
Any 3 multiples of 3 will form a primeful cycle, as their pairwise GCD modulo 3 is 0.
Now, consider the other case, when at most two of the 7 are divisible by 3.
The pigeonhole principle lets us choose 6 of the numbers such that at most one of them is a multiple of 3 - and the pairwise GCDs of these 6 numbers can only be 1 or 2, modulo 3.
Consider the complete graph on 6 nodes with the these numbers, with an edge between two nodes colored red if their pairwise GCD is 1, and colored blue otherwise.
It is well known that such a graph contains a triangle with all edges having the same color - and so by choosing the 3 nodes corresponding to this triangle, we have a primeful cycle of size 3.
Lemma 2: It is always optimal to choose a primeful cycle with 3 nodes, if possible.
Proof
Consider a node x with height a. If it has at most 3 nodes in its subtree, it is obviously impossible to find a primeful cycle of size >3.
Otherwise, because the binary tree is full, x has at least 7 nodes in its subtree - 1 with height a, 2 with height a+1, 4 with height a+2. Some 3 of these form a primeful cycle, with beauty at most 3a+6$.
Choosing a primeful cycle with \geq 5 nodes gives us a minimum beauty of 5a + 2 + 4 = 5a + 6 > 3a + 6, so 3 is optimal.
Now, we know from the above proof that for a node x with height a, we can find a primeful cycle with beauty at most 3a+6 - this implies that we do not need to consider any nodes which are height beyond a+5, because a + (a+1) + (a+6) = 3a+7 > 3a+6.
This gives us a bruteforce solution which can pass the first subtask - for each query x with height a, simply bruteforce all triples of vertices whose height is at most a+5. There are (2^6-1)^3 = 250047 such pairs, so with q \leq 10 this is not a problem.
Optimizing Further
Note that it suffices to find out whether the answer is at most 3a + 5 - if it isn’t, the answer is guaranteed to be 3a + 6.
Thus, we only consider the heights a, a+1, a+2, a+3, a+4 in the subtree of x.
Also, when considering triplets, the order of nodes doesn’t really matter anymore - so it is enough to check only one permutation, which saves a factor of 6.
Now, let us look at the possible cases for the answer to be \leq 3a+5:
-
a+4
If we are to pick a node from height a+4, only one such node can be chosen - and others must be x and a child of x, i.e, a node at height a+1. There are 2^4 \times 2^1 \times 2^0 = 32 possible choices. -
a+3
Similarly, we can pick at most one node from height a+3 - and if we do, we can pick either node x and another node from either height a+1 and a+2, or we can pick both nodes which are at height a+1 - for a total of 2^3\times (2^0\times(2^1 + 2^2) + 1) = 56 ways. - Finally, we are left with the 7 nodes at heights a, a+1, a+2 - there are \binom{7}{3} = 35 ways to choose a triplet here, simply test all of them.
The total number of triplets tested is thus 32 + 56 + 35 = 123, so doing this for each query is fast enough.
TIME COMPLEXITY
~123 operations per query.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int maxN = 20;
const int maxM = (1 << maxN) + 5;
int n, q;
int m;
int a[maxM];
int depth[maxM];
bool is_cycle(int i, int j, int k) {
int x = __gcd(a[i], a[j]) % 3;
int y = __gcd(a[j], a[k]) % 3;
int z = __gcd(a[k], a[i]) % 3;
return x == y && y == z;
}
bool valid(int x, int h1, int h2, int h3) {
if ((x << h3) > m) return 0;
assert((x << h3) + (1 << h3) - 1 <= m);
for (int i = (x << h1); i < (x << h1) + (1 << h1); i++)
for (int j = max(i + 1, (x << h2)); j < (x << h2) + (1 << h2); j++)
for (int k = max(j + 1, (x << h3)); k < (x << h3) + (1 << h3); k++)
if (is_cycle(i, j, k)) return 1;
return 0;
}
int solve(int x) {
int h = depth[x];
// h, h + 1 and h + 1
if (valid(x, 0, 1, 1)) return 3 * h + 2;
if ((x << 2) > m) return -1;
// h, h + 1 and h + 2
if (valid(x, 0, 1, 2)) return 3 * h + 3;
// h, h + 2 and h + 2
if (valid(x, 0, 2, 2)) return 3 * h + 4;
// h + 1, h + 1 and h + 2
if (valid(x, 1, 1, 2)) return 3 * h + 4;
// h, h + 1 and h + 3
if (valid(x, 0, 1, 3)) return 3 * h + 4;
// h + 1, h + 2 and h + 2
if (valid(x, 1, 2, 2)) return 3 * h + 5;
// h, h + 2 and h + 3
if (valid(x, 0, 2, 3)) return 3 * h + 5;
// h + 1, h + 1 and h + 3
if (valid(x, 1, 1, 3)) return 3 * h + 5;
// h, h + 1 and h + 4
if (valid(x, 0, 1, 4)) return 3 * h + 5;
return 3 * h + 6;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q;
m = (1 << n) - 1;
for (int i = 1; i <= m; i++) cin >> a[i];
int v = 1, r = 2;
for (int i = 1; i <= m; i++) {
if (i == r) v++, r *= 2;
depth[i] = v;
}
while (q--) {
int x;
cin >> x;
cout << solve(x) << '\n';
}
}
Tester's Solution
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i=0;i<e;++i)
#define forsn(i,s,e) for(int i=s;i<e;++i)
#define ln '\n'
typedef long long ll;
const int LIM=2e6+5,MOD=1e9+7;
int n, q;
int sz;
int a[LIM];
vector<pair<int,int>> v;
void dfs(int node, int depth){
if(node > sz) return;
if(depth > 4) return;
v.pb(mp(depth, a[node-1]));
dfs(node*2, depth+1);
dfs(node*2+1, depth+1);
}
int main(){
fastio;
cin>>n>>q;
sz = (1<<n) - 1;
forn(i,sz){
cin>>a[i];
}
forn(quer, q){
int x;
cin>>x;
v.clear();
dfs(x, 0);
sort(all(v));
int mi = 1e9;
forn(i,v.size()){
if(3 * v[i].fi >= mi) break;
forsn(j,i+1,v.size()){
if(v[i].fi + 2 * v[j].fi >= mi) break;
forsn(k,j+1,v.size()){
if(v[i].fi + v[j].fi + v[k].fi >= mi) break;
int temp = __gcd(v[i].se, v[j].se) % 3;
if(temp == __gcd(v[i].se, v[k].se) % 3){
if(temp == __gcd(v[j].se, v[k].se) % 3){
mi = min(mi, v[i].fi + v[j].fi + v[k].fi);
}
}
}
}
}
int l = 0;
while(x){
l++;
x /= 2;
}
if(mi < 1e9){
cout<<3*l+mi<<ln;
}
else cout<<-1<<ln;
}
return 0;
}