PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: gunpoint_88
Tester and Editorialist: iceknight1093
DIFFICULTY:
2929
PREREQUISITES:
Bitwise operations, finding connected components
PROBLEM:
You’re given an undirected graph with N vertices and M edges.
Vertex i has the value A_i written on it.
Find the minimum cost of choosing a connected subset of K vertices from this graph, where the cost of choosing vertices x_1, x_2, \ldots, x_K is
Print -1 if no such subset exists.
EXPLANATION:
Let’s rewrite the cost a bit.
Notice that (A_{x_1} \mathbin{\&}A_{x_2} \mathbin{\&} \ldots \mathbin{\&} A_{x_K}) is always a submask of (A_{x_1} \mid A_{x_2} \mid \ldots \mid A_{x_K}).
So, the difference between them is also just their XOR.
Thus, the cost can be written as
Everything’s a bitwise operation now, so we can look at bits one-by-one.
In particular, a bit b is present in the cost if and only if:
- At least one of the A_{x_i} has bit b set
- At least one of the A_{x_i} has bit b unset
Our aim is to minimize the cost. Since we’re dealing with bits one at a time, this can be attempted greedily — that is, if we can avoid taking bit b even at the cost of taking all of bits 0, 1, \ldots, b-1; then it’s better to do so.
With this in mind, let’s attempt a greedy solution.
Initially, we have all the vertices available to us. Let this set be V.
Let’s look at b = 29, the highest possible bit.
If we are to avoid having b in the answer, then:
- Either all the vertices we choose must not have bit b set; or
- All the vertices we choose must have bit b set.
Notice that this splits us into independent problems.
That is, if L is the subset of V whose elements don’t have b set; and R is the subset of B whose elements do have b set, we’re essentially trying to recursively solve for both L and R, independently.
If any one of them have a solution, we can definitely avoid taking b into the answer.
The issue is when neither of them have solutions: then, we must have 2^b present in the answer.
When this is the case however, we can simply try to partition based on the next bit; after all, that’s what the greedy approach would do.
This gives us a recursive formulation:
Let f(V, b) be the answer for the vertex set V, if we’re considering bit b.
f(V, b) returns \infty (in implementation, some sufficiently large number) if we can’t choose a connected subset of size K from V.
Let L be the subset of V that doesn’t have b set, and R be the other elements.
Then,
- First, set f(V, b) = \min(f(L, b-1), f(R, b-1)) recursively.
- Now, if f(V, b) \neq \infty, this is the correct value of f(V, b) (and in particular doesn’t include 2^b) so we can just return it.
- Otherwise, return 2^b + f(V, b-1).
We need to take care of a couple of details: mainly the base cases for the recursion.
- First, let’s decide if f(V, b) = \infty or not.
This is (theoretically) quite simple: consider only vertices from V, and edges between these vertices. If the resulting graph has a connected component of size \geq K then the answer is not \infty; otherwise there is no way to choose K connected vertices so we have f(V, b) = \infty.
If f(V, b) = \infty you can return it immediately, no further processing required.
Returning \infty early like this is important! - Next, the base case: if b = -1, we’ve processed all the bits, so we can return 0 immediately.
With proper implementation care, this is indeed enough to get AC (its time complexity seems a bit dubious - we’re recursing with sets?).
As for implementation details; the main thing to be careful about is the connected component size
check — it can be done using BFS/DFS and directly iterating across the elements of V and their neighbors, just be careful not to create auxiliary arrays of size N each time (to denote marked/visited vertices and such); instead you can keep global arrays and only use the cells you need.
Now, let’s look at how fast this actually is.
Let’s look at the recursion tree, level by level.
At the top level, we have all the vertices and b = 29.
Next, one of two things happens:
- We create sets L and R and check if f(L, 28) and f(R, 28) are \infty or not.
- If one (or both) are not \infty, then we recurse into them. However, across the entire second level, each vertex appears only at most once since L and R are disjoint.
- If both are \infty, we remain with the same set when recursing: again, each vertex appears only once.
It’s not hard to see that this is maintained: as we go down the tree, any particular level will still contain every vertex only at most once.
There are only 30 levels, so this isn’t really an issue.
For the same reason, all the DFS/BFS-es we’re doing to find connected components also aren’t an issue.
Across each level, each edge will only be considered at most twice - once for each of its endpoints. Whether the edge is ignored or not doesn’t matter.
So, the connected component checks across an entire level still take \mathcal{O}(N + M) time, leading to \mathcal{O}(30\cdot (N + M)) time in total, which is good enough.
It’s possible to implement this algorithm iteratively, which makes the time more obvious.
Let’s keep S: a list of sets of vertices; and the answers corresponding to each set.
Initially, S contains only the single set \{1, 2, \ldots, N\}. The answer corresponding to it is 2^{30} - 1, i.e, it contains all 30 bits.
Then, for each b from 29 down to 0:
- Iterate over all the sets X in S. For the set X whose answer is \text{val}_X,
- Split X into L and R, based on bit b.
- If L contains a component of size \geq K, add L into S; with its corresponding answer being \text{val}_X \oplus 2^b.
- If R contains a component of size \geq K, add R into S; with its corresponding answer being \text{val}_X \oplus 2^b.
- If either L or R were added to S, then X can be deleted from S.
- The final answer is the maximum answer among all sets remaining in S; and
-1if no sets remain.
This way, it should be obvious that at each bit we do \mathcal{O}(N + M) work, for \mathcal{O}(30\cdot (N + M)) in total.
TIME COMPLEXITY
\mathcal{O}(B \cdot (N + M)) per test case; where B = 30 for this problem.
CODE:
Author's code (C++, iterative)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#ifdef ANI
#include "D:/DUSTBIN/local_inc.h"
#else
#define dbg(...) 0
#endif
class Testcase{
public:
ll N,M,K,ans;
vector<vector<ll>> e;
vector<ll> a;
};
ll solution(Testcase T) {
vector<ll> a=T.a;
vector<vector<ll>> edges=T.e;
ll k=T.K;
ll n=a.size();
vector<vector<ll>> e(n);
for(auto x:edges) {
e[x[0]-1].push_back(x[1]-1);
e[x[1]-1].push_back(x[0]-1);
}
vector<ll> init(n); iota(init.begin(),init.end(),0);
vector<vector<ll>> current={init};
function<ll(ll,ll,ll,vector<ll>&,vector<ll>&)> bfs=[&](ll root,ll bit,ll is,vector<ll>&vis,vector<ll>&have)->ll{
if(vis[root] or ((a[root]>>bit)&1)!=is) return 0;
queue<ll> q; q.push(root);
ll res=0; vis[root]=1;
while(!q.empty()) {
ll cur=q.front(); q.pop(); res++; vis[cur]=1;
for(ll node:e[cur]) {
if(!vis[node] && have[node] && ((a[node]>>bit)&1)==is) {
q.push(node); vis[node]=1;
}
}
}
return res;
};
ll ans=(1ll<<32)-1,mx=ans;
for(ll bit=31;bit>=0;bit--) {
vector<vector<ll>> next;
vector<ll> have(n,0),vis(n,0);
for(vector<ll>&v: current) {
array<vector<ll>,2> c;
for(ll i:v) {
have[i]=1;
c[(a[i]>>bit)&1].push_back(i);
}
array<ll,2> sz({0,0});
for(ll z=0;z<2;z++) {
for(ll i:v) {
sz[z]=max(sz[z],bfs(i,bit,z,vis,have));
}
}
for(ll i:v) {
have[i]=0;
vis[i]=0;
}
if(sz[0]<k && sz[1]<k) {
continue;
}
for(ll z=0;z<2;z++) {
if(sz[z]>=k) {
ans&=(mx-(1ll<<bit));
next.push_back(c[z]);
}
}
}
if(!next.empty())
current=next;
}
return ans==((1ll<<32)-1)?-1:ans;
}
int main() {
int t=1;
cin>>t;
while(t--) {
Testcase T;
cin>>T.N>>T.M>>T.K;
T.a=vector<ll>(T.N);
for(ll i=0;i<T.N;i++)
cin>>T.a[i];
vector<vector<ll>> e;
for(ll i=0;i<T.M;i++) {
ll u,v; cin>>u>>v;
e.push_back({u,v});
}
T.e=e;
cout<<solution(T)<<"\n";
}
}
Editorialist's code (C++, recursive)
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, m, k; cin >> n >> m >> k;
vector<int> a(n);
for (int &x : a) cin >> x;
vector adj(n, vector<int>());
for (int i = 0; i < m; ++i) {
int u, v; cin >> u >> v;
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
vector<int> mark(n);
int ops = 0;
auto bfs = [&] (int src) {
queue<int> q;
q.push(src);
mark[src] = 2;
int sz = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
++sz;
ops += adj[u].size();
for (int v : adj[u]) {
if (mark[v] == 1) {
mark[v] = 2;
q.push(v);
}
}
}
return sz;
};
auto solve = [&] (const auto &self, const auto &vals) -> int {
// For this set of values, min cost of having a component of size >= k
// INT_MAX if impossible
if (vals.size() < k) return INT_MAX;
int mxsz = 0;
for (auto &[x, id] : vals) mark[id] = 1;
for (auto [x, id] : vals) {
if (mark[id] == 2) continue;
mxsz = max(mxsz, bfs(id));
}
for (auto &[x, id] : vals) mark[id] = 0;
if (mxsz < k) return INT_MAX;
if (vals[0][0] == vals.back()[0]) return 0;
int rem = vals[0][0] ^ vals.back()[0];
int highbit = 31 - __builtin_clz(rem);
vector<array<int, 2>> left, right;
for (auto &x : vals) {
if (x[0] & (1 << highbit)) {
right.push_back(x);
right.back()[0] ^= 1 << highbit;
}
else left.push_back(x);
}
int ret = min(self(self, left), self(self, right));
if (ret < INT_MAX) return ret;
for (auto &x : right) left.push_back(x);
inplace_merge(left.begin(), left.end()-right.size(), left.end());
return (1 << highbit) | self(self, left);
};
vector<array<int, 2>> vals;
for (int i = 0; i < n; ++i) vals.push_back({a[i], i});
sort(begin(vals), end(vals));
int ans = solve(solve, vals);
if (ans == INT_MAX) cout << -1 << '\n';
else cout << ans << '\n';
}
}