ZIO12003 - Editorial

Editorialist : Sudheera Y S

Problem Link : ZIO 2012 Problem 3

Prerequisites : Greedy , recursion

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.

Idea :

We have to color the minimum number of cells red. Therefore it is always better to choose the largest number which is not yet red , make it red so that , we can go to maximum number of cells from this red cell and need not color them red again

First choose the maximum cell number which is not red yet , color it red , and then see which all cells we can go to from the current cell in both row and column . Then , take the first cell to which cell we can go to , then check which all cells we can go from that cell

Till all cells are reachable β†’ take the maximum non-red color cell , see which all cells we can go from that cell

It will get clear as we do it

Subtask A :

Grid :

Here we see that the maximum element is 59 at (2,4) , so we will start from it β†’ firstly color it red and color blue all cells in the column 4 and row 2

Which all we colored blue in the 2nd row - { 33 , 32 , 26 , 41 , 40 , 55 }

Which all we colored blue in the fourth column - { 40 , 58 , 40 , 46 , 47 , 36 }

Now let us take one by one cell in 2nd row , and see all those cells which are reachable from that cell

Let us take 33 @ (2,1) and see which all are reachable in the first column ( Note : We need not see which all cells are reachable in the second row because those which are reachable from 33 in the row , are already coloured blue from 59 ! , so no need to check it )

Which all we colored blue in the first column β†’ { 31 , 9 , 10 , 21 }

Now let us take one by one cell in the first column ,

31 @ (3,1) : Again Note : No need to check in the first column , only the third row !

Which all we colored blue in the third row β†’ { 23, 14 }

Now one by one ,

23 @ 3,2 :

Which all we colored blue in the second column β†’ { 19 , 22 }

One by one ,

19 @ (4,2) :

Which all we colored blue in the fourth row β†’ { 9,4 }

9 @ (4,3) :

Which all we colored blue in the third column β†’ { 7 }

7 @ (6,3) :

Which all we colored blue in the sixth row β†’ { 5 }

5 @ (6,5) : from this cell we can’t color blue any other cell , therefore we return back , to {9,4} list , in that we have seen 9 but we have to see 4

4 @ (5,4) : Even this can’t color blue any other cell , therefore we go back to the list before {9,4} which is {19,22} , in this list we have finished 19 , but we have to do 22 β†’

22 @ (7,2) :

Which all we colored blue in the seventh row β†’ { 7 }

Again from the 7 we can’t color blue any cell , now we have finished {19,22} , now we go back this and see which is there which is {23,14} , we have finished 23 , but we have to do now 14

Which all we colored blue in the sixth column β†’ { 3 }

As we can see , we cannot color blue any cell from 3 , therefore we will not see that. Now that we have finished {23,14} we will see which we have to do by going back {23,14} and it is

{ 31 , 9 , 10 , 21 } in which we have completed 31 , now we have to do 9 . As we can see we cant color blue any other cell from 9 and as well as 10, therefore we skip both of them and directly go to 21

Which we colored blue β†’ { 14 }

As we can see that we cannot color blue from 14 , therefore we skip this and we have now finished { 31 , 9 , 10 , 40 , 21 } . We will see what was there before this and it is { 33 , 32 , 26 , 41 , 40 , 55 } out of which 33 is done :frowning: :frowning: Lets take the next one i.e 32

32 @ (2,2) :

Which we colored blue β†’ { 29 }

As we can see we cannot color any other cell blue from 29 therefore we skip this list and do from the next number from { 33 , 32 , 26 , 41 , 40 , 55 } which is 26 @2,3 and again we cannot blue any other cell , therefore we skip this and do the next number from { 33 , 32 , 26 , 41 , 40 , 55 } which is 41 @2,5 BUT AGAIN we cannot color any other cell blue , therefor we skip this and take the next number from { 33 , 32 , 26 , 41 , 40 , 55 } which is 40 @ (2,6)

40 @ (2,6 ) :

Which all we colored β†’ { 39 , 30 , 36 } But as we can see we can color no other cell from both of these therefore we skip both of these and take the next number which is 36 and as we can see we can coor 31 in the eighth row , therefore we will make it blue :

36 @ (8,6) :

Which we colored β†’ { 31 } , therefore now we will see which are reachable from 31 and it is 28 in the seventh column ,

31 @(8,7 ) :

Which we colored β†’ { 28 } in the seventh column , and we cant reach anywhere from 28 therefore we skip this and we have completed { 39 , 30 , 36 } , therefore we go back it and see which is { 33 , 32 , 26 , 41 , 40 , 55 } and we have completed 40 and we will take the next number which is 55 :

55 @ (2,7) :

Which all we colored blue β†’ { 33 , 40 , 41 , 54 }

As we can see we cannot color any other cell blue from the first three numbers , therefore we can skip these three and directly take the last one i.e 54 and start doing from it

54 @ (6,7) :

Which all we colored blue β†’ { 41 } , but we cannot color blue any other cell from 41 therefore we again skip it.

BUT WAITTTTT !!

From that time we are only seeing those which were colored in the row by 59 and we have not even considered those which we have colored blue in the fourth column !

We colored blue in the column by the red cell β†’ { 40 , 58 , 40 , 46 , 47 , 36 } :frowning:

Now let us consider one by one and do them :frowning:

As we can see we cannot color any other cell blue from 40 , 40 , 46 , 47

Therefore we can skip them and do 58 and 36

36 @ (7,4) :

Which we colored blue β†’ {31} in the seventh row but as we can see we cannot color any cell blue from 31 therefore we skip this and go to the next one which is 58

58 @ ( 3,4) :

Which we colored blue β†’ { 41 }

Again we cannot color blue any other cell from 41 therefore we can skip it and our coloring all the cells from the first red cell is over now :frowning:

Now that we have done with the first red coloring and there are still cells which are not colored either red or blue therefore we have to color some cell red to make the rest blue or red

As we have decided earlier , we will color red the one which is maximum in the non-colored cell and we find this as 59 @ ( 3,5) :

From this Red cell we can reach {52,55} and from 52 we cant blue any other cell therefore we will skip this and take the next number which is 55 and from this we can reach 49

55 @ (1,5) :

Which we colored β†’ {49} but as we see we cant color blue any other cell therefore we leave this and take the the next number but there are no other cells , we are done with this red cell.

But there are still some cells non-coloured

Therefore ,

We should choose the maximum non-coloured cell , and that is 59

Coloring red 59 @ (8,4) :

59 @ (8,4) :

Which all we colored β†’ { 40 , 41 } but unfortunately ( fortunately ? ) from both of these we cant reach any other cell , therefore we have to skip both of these

There are still some non-colored cell , therefore ,

Now let’s take the next maximum number from a non-colored cell and there are many of them , let us choose one by one and the first one is 55 @ 1,1

Coloring red 55 @ (1,1) :

55 @ (1,1) :

Which all we colored blue β†’ { 40 } but again we cannot reach any other cell from this therefore we have to skip this ,

As there are some cells which are still non-colored , we will have to color one more red cell and it should be the maximum , therefore it would be 55 @ 1,7

We can’t reach any other cell from this red cell , therefore we should leave this

But should this cell be colored red ?

Yes , Because we should be able to reach all the cells from red cells in zero or more moves but if we don’t color this red , as we can see this cell becomes unreachable from all the cells therefore even if we can’t reach any other cell , we have to color this red !

As there are some cells which are still non-colored , we will have to color one more red cell and it should be the maximum , therefore it would be 55 @ 5,1

55 @ (5,1) :

Which all we colored blue β†’ { 54 } but as we cannot reach any other cell from 54 we need to skip and and we are done with this red cell

As there are some cells which are still non-colored , we will have to color one more red cell and it should be the maximum , therefore it would be 55 @ 5,3

But as we can see we cannot reach any other cell from 55 therefore we can continue coloring red as there are still two non-colored cells.

Both of these are equal ,therefore we cannot reach any of them by any of them , therefore we have to color both the cells red :

Now all the cells are colored !!

So now we can directly calculate our answer

Number of red cells β†’ 9

Minimum cell number in all red cells β†’ 40

Answer : 9,40

Subtask B , C : Bonus :slight_smile:

Thanks to @akashbhalotia sir for finding mistakes in this long post !

Hope you understood
:slight_smile:

3 Likes