PROBLEM LINK:
Author: Vikas Pandey
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia
DIFFICULTY:
Easy
PREREQUISITES:
Bitwise AND, Bit Manipulation, Number Theory.
PROBLEM:
Given a graph with N vertices, numbered from 1 to N, and no edges, adding an edge between vertices x and y costs (x\&y). An edge can only be added if it has a positive cost. Find the minimum cost to make the graph connected, or state that it is impossible.
HINTS:
Not the full solution. Just some hints to help you if you are stuck at some point. As soon as you encounter a hint that you had not thought of, try solving the problem on your own.
Hint 1:
A solution doesn’t exist if N is a power of 2. What is unique about powers of 2? They have only a single set bit in their binary representation.
Try it.
If N=2, can vertex 2 be connected to vertex 1?
If N=4, can vertex 4 be connected to any other vertex?
Similarly, try to think why this holds whenever N is a power of 2.
Hint 2:
The minimum positive cost with which a vertex numbered x can be connected to some vertex in the graph is equal to the value of the lowest set bit in x.
For example, 6, (binary representation: 110), can’t be connected with a cost less than 2.
Try to find the connection between the lowest set bit of a number in its binary representation, and the minimum positive cost to connect it to some vertex.
Hint 3:
Let’s divide the vertices into groups, based on the position of their lowest set bit. The number of vertices in a group is \lfloor \frac{N+2^i}{2^{i+1}} \rfloor, where i is the position of their lowest set bit. If there are V number of vertices in a group, it will take V-1 edges to connect them. Each of these edges will cost 2^i.
Try to think about this.
Hint 4:
Now that the vertices have been connected to their group members, how do we connect the vertices of different groups with minimum possible positive cost?
The smallest vertex in each group is the vertex 2^i. It can always be connected to the vertex 2^i+1, for a cost of 2^i. Why is this so? Can you find the connection between this hint and the first one?
QUICK EXPLANATION:
show
A solution doesn’t exist if N is a power of 2. Else, the vertices can be grouped based on the position of their lowest set bit and each vertex of a group i can be connected to its group members for a cost of 2^i per edge, i denoting the position of the lowest set bit. Finally the groups can be connected to one another. This can be done by connecting each vertex 2^i, (i \gt 0) with the vertex 2^i+1, for a cost of 2^i.
EXPLANATION
show
We need to make the vertices of the graph connected with minimum possible cost, such that any vertex is reachable from any other vertex, and the edge costs are positive (i.e., \gt 0). The cost of an edge, between vertices numbered x and y respectively, is (x\&y), where ‘\&’ denotes the bitwise AND operator.
What is the minimum positive cost with which a vertex numbered x can be connected to any other vertex in the graph?
The minimum possible positive cost with which x can be connected to some vertex in the graph is equal to the value of the lowest set bit in x.
why
Let’s look at the binary representation of x. In the binary representation of x, at least one of the bits will be set (as 1 \le x \le N). When we \& x with any other vertex, say, y, the resulting cost will be a number, which will have only those bits set which are set in both x and y. All other bits will be unset.
As the cost of an edge should be positive, at least one common bit should be set in both x and y. A lower positioned bit which is set in both x and y will contribute less to the cost, as compared to a common higher positioned bit.
Example: Let’s try to connect vertices 11 and 14. The resulting cost is 10, as the bits positioned 3 and 1 are common in both of them (bits are positioned from 3 to 0 here, left to right). The bit positioned 1 contributes 2^1=2 to the cost, while the bit positioned 3 contributes 2^3=8 to the cost. Thus, a lower positioned bit which is set in both x and y will contribute less to the cost, as compared to a common higher positioned bit.
So, to connect x to some vertex in the graph with minimum possible positive cost, we should connect it to a vertex which has only the lowest set bit in x common with x.
For example, we should connect vertex 3 with vertex 1, or with vertex 9, or 13, etc., any vertex which has only the lowest set bit in 3, i.e. bit at position 0, common with 3, with a cost of 2^0=1. Similarly, we should connect vertex 10 with any vertex which has only the bit at position 1 common with 10. Some example vertices with have this property are: 2, 6, 18, etc. This will cost 2^1=2, which is the minimum possible cost to connect 10 with some vertex in the graph.
Let’s group the vertices based on their lowest set bit:
Group 0: {1, 3, 5, 7, 9, etc.}
Group 1: {2, 6, 10, 14, 18, etc.}
Group 2: {4, 12, 20, 28, 36, etc.}
Group 3: {8, 24, 40, 56, 72, etc.}
Group 4: {16, 48, 80, 112, 144, etc.}
.
.
.
Group i: {2^i, 2^i+2^{i+1}, 2^i+2*(2^{i+1}), 2^i+3*(2^{i+1}), 2^i+4*(2^{i+1}), etc.}
There will be (\log_{2} N) such groups, as the number of bits in N is (\log_{2} N).
We can connect the vertices of each group with the smallest member of that group, and this will ensure that each vertex will be connected to some vertex in the graph with minimum possible cost. Thus, every vertex in group 0 (other than 1), will be connected to vertex 1 with a cost of 1 per edge, every vertex in group 1 (other than vertex 2) will be connected to vertex 2 with a cost of 2 per edge, and so on.
If a group has V vertices, each of the V-1 vertices will be connected to the smallest numbered vertex with an edge, which will cost 2^i, where i is the group number, or the position of the lowest set bit in each number of the group. Thus, the total cost for connecting the vertices of a group is:
- (V-1)*2^i
But what is V? What is the number of vertices in group i ?
The number of vertices in group i, in the range 1 \le x \le N is:
- V= \lfloor{\frac{N+2^i}{2^{i+1}}} \rfloor
why
Let’s try to get the intuition using some examples.
Let’s look at group 1: {2, 6, 10, 14, 18, etc.}
It starts from 2, and then every number after it has a gap of 4 with the previous number. Let’s say N is in the range [2,5]. Then the number of vertices in group 1 is 1. If N is less than 2, then there is no vertex in this group. If N is from 2 to 9, the number of vertices is 2, and so on.
For N in range [2,5], we want 1 as the count of vertices. If we add 2 to N and divide it by 4, we get 1 for this range. Similarly, for N in range 6,9, this will give us 2, and so on, for any value of N. Here, 2=2^i, while 4=2^{i+1}.
Similarly, for any group, if we add the first term of the group to N, and divide this by the gap between the numbers of that group, we shall get the number of vertices \le N in the group.
The first term of a group i is 2^i, while the gap between the numbers is 2^{i+1}.
After the vertices of each group are connected to the smallest vertex in their respective groups, we have (\log_{2} N) disjoint connected components. Now we need to connect these components. Thus, we need to find a way to connect one vertex of a component to some vertex of another component, for each component, with minimum positive cost.
The vertices of a group i were connected with each other with a cost of 2^i per edge, but they can’t be connected to vertices of a higher group with this cost. However, they can be connected to some vertices of a lower group with this cost. In particular, we can always connect the smallest vertex of a group i, (i \gt 0), vertex numbered 2^i with with the vertex 2^i+1 (which belongs to group 0) with a cost of 2^i (the smallest possible cost for group i).
why
Since i \gt 0, vertex 2^i has the lowest bit unset. This means that vertex 2^i+1 will have bit at position 0 set, as the lowest set bit, while i set as the next lowest set bit. On performing \& on them, i will be the only common bit position. Thus, it will always cost 2^i for adding an edge between vertices 2^i and 2^i+1.
We can verify that vertex 2^i+1 is the smallest vertex with which vertex 2^i can be connected, with a cost of 2^i.
Thus, it will cost 2+4+8+ \ldots + 2^{\log_{2} N} to connect all the groups. This can be calculated using a loop, or using the formula:
- 2^{1+\log_{2} N}-2
Will a solution always exist?
No, a solution won’t exist if N has only one set bit in its binary representation.
why
A solution won’t exist if N has only one set bit in its binary representation because this implies that N is a power of 2, and N is of the form 2^i. A vertex of the form 2^i belongs to group i and is the smallest vertex in it. For a vertex 2^i to be connected to the graph, the smallest numbered vertex which can make this possible is the vertex 2^i+1. Since N=2^i, there aren’t enough vertices in the graph to make this possible. Thus, a solution won’t exist if N has only one set bet in its binary representation.
This too can be checked using a loop, or by checking if N \& (N-1) =0 (refer to this for the explanation).
Thus, to solve the problem,
- Check if N is a power of 2. If this is true, then a solution doesn’t exist. Else,
- Count the number of vertices belonging to each group, based on the position of the lowest set bit in them, multiply this by the value of the lowest set bit and calculate the total cost of connecting vertices belonging to each group to other vertices belonging to the same group.
- Finally, add the cost of connecting all the groups together.
TIME COMPLEXITY:
show
The time complexity is: O(\log_{2} N) per test case.
Why?
Group i contains vertices which have i as the lowest set bit in its binary representation. As N is the highest numbered vertex, there can only be \log_{2} N bits, thus, \log_{2} N groups, and all the operations that are performed on the groups take constant time.
SOLUTIONS:
Setter
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ff first
#define ss second
void solve()
{
int n;
cin>>n;
if(!(n&(n-1)))
{
cout<<-1<<endl;
return;
}
int ans=0;
for(int i=1; i<=n; i<<=1)
ans+=((n-i)/(i<<1))*i;
for(int i=2; i<n; i<<=1)
ans+=i;
cout<<ans<<endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
Tester
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,i,val,ans=0;
cin>>n;
f(i,1,31){
if((1<<i)==n){
break;
}
}
if(i!=31){
cout<<"-1"<<endl;
continue;
}
rep(i,31){
val=n/(1<<i);
val=(val+1)/2;
ans+=(val-1)*(1<<i);
if(i!=0){
ans+=(1<<i);
}
}
cout<<ans<<endl;
}
return 0;
}
Editorialist
//created by Whiplash99
import java.io.*;
import java.util.*;
class A
{
public static void main(String[] args) throws IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int i,N;
int T=Integer.parseInt(br.readLine().trim());
StringBuilder sb=new StringBuilder();
while(T-->0)
{
N=Integer.parseInt(br.readLine().trim());
//does the highest vertex number have only 1 set bit
//in its binary representation? (is it a power of 2?)
if((N&(N-1))==0)
{
//if so, then it can't be connected to any other vertex
//in the graph with a positive cost, thus, impossible case.
sb.append(-1).append("\n");
continue;
}
long cost=0;
for(i=1;i<=N;i<<=1) //i is the value of the lowest set bit
{
//how many numbers have i as the lowest set bit
//in their binary representation?
long count=(N+i)/(i<<1);
//connecting x of them will require (x-1) edges.
//each of these edges will cost i
cost+=(count-1)*i;
}
cost+=i-2; //connecting all groups together
sb.append(cost).append("\n");
}
System.out.println(sb);
}
}
Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions 
