ZIO 2012 Problem 3
Editorialist : Sudheera Y S
Problem Link : ZIO 2012 Problem 3
Prerequisites : Logic
Problem statement :
There is a grid given and each cell contains a number. We can move from cell x to cell y if they both are in the SAME ROW or SAME COLUMN and the number written in cell y is strictly less than the number written in the cell x . We want to color some cells red so that :
• Every cell can be reached by starting at a red cell and following a sequence of ZERO or MORE moves as defined above.
• The number of red cells is as small as possible
You should report the following information:
• The number of red cells.
• The smallest number appearing amongst all red cells.
Quick Explanation :
Let us consider a cell. It will be reachable from another cell ( which is in the same row or same column ) if there is a cell ( in the same row and column ) which is strictly more than that
But if the cell is the maximum value in the row or column , we have to colour it red so that it is reachable.
For every row and column , find the maximum value , and colour all the values which are equal to the maximum value ( because if two cells have the same maximum value , both of them should be coloured red )
Subtask A :
Grid :
Maximum in
Row 1 → 55
Row 2 → 59
Row 3 → 59
Row 4 → 40
Row 5 → 55
Row 6 → 54
Row 7 → 40
Row 8 → 59
Maximum in
Column 1 → 55
Column 2 → 54
Column 3 → 55
Column 4 → 59
Column 5 → 59
Column 6 → 40
Column 7 → 55
Now let us consider the row maximum one by one and make sure the column maximum is not greater than the value. If it is greater than the value , then we need not colour it though it is the maximum in the row because there is another maximum in the column.
Row 1 →
Maximum : 55
Occurs at columns 1,5,7
Column 1 max = 55 , we need to colour this cell red
Column 5 max = 59 , we need not colour this cell
Column 7 max = 55 , we need to colour this cell red
Row 2 →
Maximum : 59
Occurs at column 4
Column 4 max = 59 , we need to colour this cell red
Row 3 →
Maximum : 59
Occurs at column 5
Column 5 max = 59 , we need to colour this cell red
Row 4 →
Maximum : 40
Occurs at columns 4,6,7
Column 4 max = 59 , we need not colour this cell
Column 6 max = 40 , we need to colour this cell red
Column 7 max = 55 , we need not colour this cell
Row 5 →
Maximum : 55
Occurs at columns 1,3
Column 1 max = 55 , we need to colour this cell red
Column 3 max = 55 , we need to colour this cell red
Row 6 →
Maximum : 54
Occurs at column 7
Column 7 max = 55 , we need not colour this cell
Row 7 →
Maximum : 40
Occurs at columns 1,6
Column 1 max = 55 , we need not colour this cell
Column 6 max = 40 , we need to colour this cell red
Row 8 →
Maximum : 59
Occurs at column 4
Column 4 max = 59 , we need to colour this cell red
Now we are done with seeing all the maximum cells. Totally we coloured 9 cells and the minimum among them is 40
Our grid looks like this after colouring :
Answer : 9,40
Subtask B , C : Bonus 
Hope you understood
