CROADS - Editorial

PROBLEM LINK:

Practice
Contest

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,

  1. Check if N is a power of 2. If this is true, then a solution doesn’t exist. Else,
  2. 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.
  3. 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 :slight_smile:

14 Likes

I got stuck at calculating no of vertices in a group in O(1). Nice Editorial.

6 Likes

Another way to calculate this, probably more intuitive, used by the tester, is to notice that the vertices in a group are simply the odd multiples of the first term.

How many odd multiples of a number are there less than or equal to N?

There will be \lfloor \frac{N}{x} \rfloor multiples of x \le N. Let’s call this M.
How many of these are odd? \lfloor \frac{M+1}{2} \rfloor of these are odd.

12 Likes

I got stuck there as well. I am still not able to get it, can you explain?

1 Like

Please check my comment. This should help, hopefully.

1 Like

I am unable to find editorial of CHFIMPRS. Wanted to see your approach. Is it not posted yet?

CHFIMPRS, CHEFTRIP and CURSCURS haven’t been posted yet. CHFIMPRS and CHEFTRIP should be posted by today evening.

1 Like

https://www.codechef.com/viewsolution/33319497

I got the logic in just 30 mins. But wasted the whole time in debuggin. Pls helppp.

I have debugged it: here.
The cost of connecting the groups always needs to be added, and not only when i*3 \gt N.

Ohhh I just created a forest. And didnt join the trees. How silly

Fact that vertices in a group are odd multiples of first term can be easily understood by the fact that all other set bits other than bit at position i are even multiple of 2^i i.e. first term(think in terms of left shift).

1 Like

For all who want to understand in more shorter manner Commented code with understable variables :slight_smile:
See : https://www.codechef.com/viewsolution/33319944

Any doubt Plz ask :slight_smile:

2 Likes

I had a similar approach. It’s probably an extension of the solution mentioned here.

First of all, check if N is a power of 2. If no, we can proceed further.

Connect all the odd numbers (> 1) to 1. This will add N-N/2-1 to the answer.

Now there’s an observation: For an integer X which is not a power a 2, if it is divisible by 2^y (y\geq 1), then the y^{th} bit of X will be the lowest set bit in X. So for such an integer X, we add 2^y to the answer.

If an integer X is a power of 2, we can simply connect it with X+1 (which is odd). And for such an integer X, we add X to the answer.

Now, if you observe carefully, all odd numbers are connected to each other, and all powers of 2 are connected to some odd number, and finally, all the remaining numbers are connected to some power of 2. Thus, we have managed to connect all the integers from 1 to N.

Refer this for better understanding.

5 Likes

“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”
can you please explain why ?
like if I take 14 and 6 as example, the LSB is 2 for both, How could we have a road in bw those so the cost is 2 ?

You got it wrong. For some vertex numbered x, it is possible to choose to another vertex y which will give minimum cost equal to value of lowest set bit in x.
And if we follow this property for every vertex, then, out total cost will be minimum.
That’s why for x = 14, you cannot take y = 6 because cost here will be 6 instead of 2.
Check out my video editorial for better understanding.

Nice Editorial.

1 Like

My approach was entirely different. You can notice a pattern repeats at every 2^i. I pre-calculated answer for all 2^i in a vector ans . And simplified result\; += ans[ \text{power of 2 just below N}] and now N = N\; \% \; \text{power of 2 just below N} . Keep on calculating till N reaches 1 or 0.

Submission : https://www.codechef.com/viewsolution/33305207

We are not connecting 14 to 6 by a direct edge. The lowest set bit in x is like a limit for it, as in, it is not possible to make a vertex connected to the graph with a cost of less than the value of its lowest set bit.

14 and 6 have bits of value 2 and value 4 common. It doesn’t mean that we are connecting them. Since their lowest set bit is common, we are simply placing them inside the same connected component, i.e., the component of vertex 2. They will be connected to 2 by a direct edge, and this will cost 2.

Did exactly the same … :slight_smile:

How did you come up with the formula of V ?