[Closed] Help Needed

Question : Utkarsh in Gardens

include<bits/stdc++.h>
using namespace std;

int main(){

``````int v,n;
cin>>v;
bitset<2005>c[2005];
for(int i=0; i<v; i++){
for(int j=0; j<v; j++){
cin>>n;
c[i][j] = n;
}
}
long long int ans=0;
for(int i=0; i<v; i++){
for(int j=i+1; j<v; j++){
n = (c[i]&c[j]).count();
ans += (n*(n-1))/2;
}
}
cout<<ans/2;

return 0;
``````

}

Someone please explain the solution I will be very grateful. Thanks in advance.

A very elegant solution

For each vertex the corresponding row in the adjacency matrix is saved as a bitset for efficiency. It could have been saved as an `int` array too but that would give TLE. Now for a pair of vertices `i` and `j`, the AND of their two bitsets will give a bitset that represents the vertices connected to both `i` and `j`. Let this bitset contain `n` such vertices. If we consider `i` and `j` the opposite vertices of the garden of 4 vertices, then we can pick any 2 vertices out of these `n` vertices to complete a loop of length 4. The number of ways to pick 2 elements out of `n` is nC2, which is `(n*(n-1))/2`. Summing up for all `i,j` pairs will give us twice the total, because each loop will be counted twice, once by each pair of opposite vertices. Hence the `ans/2` at the end.

Feel free to ask if something is not clear

Sir , while entering the values we accessed the bitset using c[i][j] but in the loop c[i] and c[j]. Why?

Got it. Thanks

Hi, I do not have enough karma points to ask a separate question(sorry for posting the question here. But I badly want to solve this problem). Can someone please help me to decipher this question. I do not understand the sample output given.

Microâ€™s math teacher just taught him about Modular Arithmetic, and gave him an assignment to solve. Assignment is really large and will take a lot of his time. Micro wants to go out and play as soon as possible. The assignment consists of some decimal numbers and Micro has to find out the value of their modulo 10^9+7.

Input:
First line consists of T denoting the number of test cases. Each of the following T lines consists of a decimal number.

Output:
For each test case print the value of decimal number modulo 10^9, and if modulo does not exists print -1. Print a new line after each test case.

Constraints:
1â‰¤Tâ‰¤5Ă—10^5
1â‰¤Total number of digits in the numberâ‰¤18
1â‰¤Number of digits after decimal pointâ‰¤9

SAMPLE INPUT

``````2
1.23
4.0
``````

SAMPLE OUTPUT

``````110000002
4
``````

Thanks.

1 Like

@terriblecoder I have up voted you. Now you can ask questions separately.

1 Like

Hi Deepansh, thank you very much

If you consider a bitset as an array of bits that will make it easier to understand. So `c` is an array of bitsets, or a 2D array of bits. `c[i]` is a single bitset, or a 1D array of bits. And `c[i][j]` is the jth bit in the bitset `c[i]`.
While taking input each bit needs to be set according to the input, so each bit is accessed as `c[i][j]`. And while calculation we just need to AND 2 bitsets, which are `c[i]` and `c[j]`.
For more about bitsets see [here][1].
[1]: C++ bitset and its application - GeeksforGeeks

1 Like

No problem

Can any one help on this please.