All Tracks Algorithms Graphs Graph Representation Problem

Utkarsh in Gardens
Tag(s):

Medium

Problem
Editorial
Analytics

Problem Statement
Utkarsh has recently put on some weight. In order to lose weight, he has to run on boundary of gardens.
But he lives in a country where there are no gardens. There are just many bidirectional roads between cities.
Due to the situation, he is going to consider any cycle of length four as a garden. Formally a garden is considered to be a unordered set of 4 roads {r0, r1, r2, r3} where ri and ri+1 mod 4 share a city.

Now he wonders how many distinct gardens are there in this country.


Input format:
The first integer contains N, the number of cities in the country.
It is followed by space separated elements of N*N binary matrix G.
G[i][j] = 1 denotes there is a road between ith city and jth city.
A pair of cities has atmost one road connecting them.
No road connects a city to itself.
G is symmetric.


Output format:
Print the total number of gardens.


Constraints:
1 ≤ N ≤ 2000

SAMPLE INPUT
8
0 1 0 1 1 0 0 0 
1 0 1 0 0 1 0 0 
0 1 0 1 0 0 1 0 
1 0 1 0 0 0 0 1 
1 0 0 0 0 1 0 1 
0 1 0 0 1 0 1 0 
0 0 1 0 0 1 0 1 
0 0 0 1 1 0 1 0 
SAMPLE OUTPUT
6
Explanation

The Country here is a cube. A cube consists of 6 square faces denoting 6 gardens.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?