CROADS - Editorial

editorial
, , , , , , , ,
4

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

1 Like
5

Please check my comment. This should help, hopefully.

1 Like
6

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

7

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

1 Like
8

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

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

9

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

11

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

12

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
13

For all who want to understand in more shorter manner Commented code with understable variables :slight_smile:
See : CodeChef: Practical coding for everyone

Any doubt Plz ask :slight_smile:

2 Likes
14

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
15

“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 ?

16

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.

17

Nice Editorial.

1 Like
18

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 : CodeChef: Practical coding for everyone

19

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.

21

Did exactly the same … :slight_smile:

22

How did you come up with the formula of V ?

23

i am unable to understand the logic for
lli total_element_whose_i_th_bit_set = (n+1)/2;

and n = n/2;

Can you please tell me how you got these ?

24

Read comments bro :slight_smile: I think i mentioned all the things clearly

25

Just sharing my commented code :slight_smile: .

Code 
#include <bits/stdc++.h>
using namespace std;
//the following array contains powers of 2. Index 1 will contain 2^1 = 2, and so on
long long two[35] = {0};

bool Compare(long long n) { //a function to check whether the given number is a power of 2 or not
    for(long long i = 0; i < 35; i++) {
        if(two[i] == n)
            return true;
    }
    return false;
}

void Solve() {
    long long n; //inputting n
    cin >> n;
    if(Compare(n)) { //if n is a power of 2, answer is -1
        cout << "-1" << endl;
        return;
    }
    long long ans = 0;
    for(long long i = 0; i < 34; i++) {
        if(two[i] > n) //don't require further iterations
            break;
        long long start = two[i] + two[i + 1]; //first number which will be connected to 2^i(there is a pattern if you observe)
        if(start > n) { //if the number is greater than n
            ans += two[i]; //to connect the graph
            continue;
        }
        long long lol = (n - start) / two[i + 1] + 1; //this integer basically stores the count of numbers which the current element has to be connected with
        ans += (two[i] * lol); //for all the numbers, two[i] must be added each
        if(i != 0) //if i == 0, we don't have to connect the number to anything else
            ans += two[i]; //else we need to connect the graph
    }
    cout << ans << endl;
}

void power() {
    two[0] = 1;
    two[1] = 2;
    for(long long i = 2; i <= 35; i++) {
        two[i] = two[i - 1] * 2;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    power();
    int t;
    cin >> t;
    while(t--) {
        Solve();
    }
    return 0;
}