All Tracks Data Structures Arrays Multi-dimensional Problem

Monk and Inversions
Tag(s):

Data Structures, Easy

Problem
Editorial
Analytics

Monk's best friend Micro, who happen to be an awesome programmer, got him an integer matrix $$M$$ of size $$N \times N$$ for his birthday. Monk is taking coding classes from Micro. They have just completed array inversions and Monk was successful in writing a program to count the number of inversions in an array. Now, Micro has asked Monk to find out the number of inversion in the matrix $$M$$. Number of inversions, in a matrix is defined as the number of unordered pairs of cells $$\{(i, j), (p, q)\}$$ such that $$M[i][j] \gt M[p][q]\space \&\space i \le p\space \& \space j \le q$$.
Monk is facing a little trouble with this task and since you did not got him any birthday gift, you need to help him with this task.

Input:
First line consists of a single integer $$T$$ denoting the number of test cases.
First line of each test case consists of one integer denoting $$N$$. Following $$N$$ lines consists of $$N$$ space separated integers denoting the matrix $$M$$.

Output:
Print the answer to each test case in a new line.

Constraints:
$$1 \le T \le 100$$
$$1 \le N \le 20$$
$$1 \le M[i][j] \le 1000$$

SAMPLE INPUT
2
3
1 2 3
4 5 6
7 8 9
2
4 3
1 4
SAMPLE OUTPUT
0
2
Explanation

In first test case there is no pair of cells $$(x_1, y_1)$$, $$(x_2, y_2)$$, $$x_1 \le x_2 \space \& \space y_1 \le y_2$$ having $$M[x_1][y_1] > M[x_2][y_2]$$, so the answer is $$0$$.
In second test case $$M[1][1] > M[1][2]$$ and $$M[1][1] \gt M[2][1]$$, so the answer is $$2$$.

Time Limit: 1.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: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Arrays & Strings)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications