[Closed] Help Needed

general
1

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.

2

A very elegant solution :smiley:

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 :slight_smile:

3

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

4

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]: http://www.geeksforgeeks.org/c-bitset-and-its-application/

1 Like
5

Got it. Thanks

6

No problem :slight_smile:

7

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
8

Can any one help on this please.

9

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

10

Hi Deepansh, thank you very much :slight_smile: