Binary Inversion ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 You are given 

N$N$ binary strings S1,S2,…,SN$S_1,S_2,\dots ,S_N$, each of length M$M$. You want to concatenate all the N$N$ strings in some order to form a single large string of length N⋅M$N\cdot M$. Find the minimum possible number of inversions the resulting string can have.

A binary string is defined as a string consisting only of '0$0$' and '1$1$'.

An inversion in a binary string S$S$ is a pair of indices (i,j)$(i,j)$ such that i<j$i<j$ and Si$S_i$ = '1$1$', Sj$S_j$ = '0$0$'. For example, the string S=$S=$ "01010$01010$" contains 3$3$ inversions : (2,3)$(2,3)$, (2,5),$(2,5),$ (4,5)$(4,5)$.

Note that you are not allowed to change the order of characters within any of the strings Si$S_i$ - you are only allowed to concatenate the strings themselves in whatever order you choose. For example, if you have "00$00$" and "10$10$" you can form "0010$0010$" and "1000$1000$", but not "0001$0001$".

Input Format

• The first line of input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N,M$N,M$.
• N$N$ lines follow, the ith$i^{th}$ of which contains the string Si$S_i$ of length M$M$.

Output Format

For each test case, print a single line containing one integer - the minimum possible number of inversions in the resulting string.

Constraints

• 1≤T≤103$1\le T\le {10}^3$
• 2≤N≤105$2\le N\le {10}^5$
• 1≤M≤105$1\le M\le {10}^5$
• 2≤N⋅M≤2⋅105$2\le N\cdot M\le 2\cdot {10}^5$
• |Si|=M$|S_i|=M$
• Si$S_i$ contains only characters '0$0$' and '1$1$'.
• Sum of N⋅M$N\cdot M$ over all test cases does not exceed 106${10}^6$.

Sample Input 1 

4
2 1
0
1
3 2
10
00
01
2 4
0010
1011
3 4
1011
1101
0101

Sample Output 1 

0
2
3
11

Explanation

Test case 1$1$: Two strings can be formed : S1+S2=$S_1+S_2=$"01$01$", S2+S1$S_2+S_1$= "10$10$". The first string does not have any inversion while the second has one inversion : (1,2)$(1,2)$.

Test case 2$2$: Both S2+S1+S3=$S_2+S_1+S_3=$"001001$001001$", S2+S3+S1=$S_2+S_3+S_1=$"000110$000110$" contain 2$2$ inversions. It can be verified that no other order results in fewer inversions.

• Tweet
• Share
• Share
• Share
• Share

Related Post