| Submit | All submissions | Best solutions | Back to list |
HAROWS - A - Crazy Rows |
Crazy Rows
You are given an N x N matrix with 0 and 1 values. You can swap any two adjacent rows of the matrix.
Your goal is to have all the 1 values in the matrix below or on the main diagonal. That is, for each X where 1 ≤ X ≤ N, there must be no 1 values in row X that are to the right of column X.
Return the minimum number of row swaps you need to achieve the goal.
Input
The first line of input gives the number of cases, T. T test cases follow.
The first line of each test case has one integer, N. Each of the next N lines contains N characters. Each character is either 0 or 1.
Output
For each test case, output
Case #X: K
where X is the test case number, starting from 1, and K is the minimum number of row swaps needed to have all the 1 values in the matrix below or on the main diagonal.
You are guaranteed that there is a solution for each test case.
Limits
1 ≤ T ≤ 60
1 ≤ N ≤ 8
| Input | Output |
| 3 2 10 11 3 001 100 010 4 1110 1100 1100 1000 |
Case #1: 0 Case #2: 2 Case #3: 4 |
| Added by: | Alvaro Javier Medina Balboa |
| Date: | 2010-10-15 |
| Time limit: | 1.009s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 NODEJS OBJC VB.NET |
hide comments
|
2016-06-13 00:58:14
Great Question. Think carefully, maintain the invariance. |
|
|
2016-03-15 06:26:17 Ahmed M. Nasser
@Abeer Khan: you probably didn't get that "Your goal is to have all the 1 values in the matrix below or on the main diagonal." This means that the first row does not have to go the last row. So, the steps will be: 1. move last row up 2. move that row again upward 3. move that row again one last time the first row and you will have this shape: 1000 1110 1100 1100 4. You will only need one last step which is to move the 2nd row downward Last edit: 2016-03-15 06:33:01 |
|
|
2014-12-08 11:06:32 Abeer Khan
Can someone explain output 3? I'm working it out to be 5 :/ |
|
|
2010-10-15 03:00:19 David Gómez
This is a problem of the Google Code Jam. You should write that information in the problem resource. |
RSS