Doubt in ZIO 2012 Question 3

help
1

I have a doubt in the given example for the question. I’m pasting the question text below:
(copied from the pdf available at: https://www.iarcs.org.in/inoi/2012/zio2012/zio2012-qpaper.pdf)

You are given a grid of cells. Each cell has a positive integer written on it. You can
move from a cell x to a cell y if x and y are in the same row or same column, and the
number in y is strictly smaller than the number in x. You 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.

If there are multiple valid solutions, give any one solution

For example, suppose the grid is as follows:
2 2 3
2 1 2
3 2 2
It is sufficient to color the two cells labelled 3, and one cannot do better than this.
In this case, the number of red cells is 2 and the smallest number appearing amongst
all red cells is 3.

(followed by three grids, for which the student has to provide the answer)

What I’m understanding is that a cell (x,y) is reachable ONLY if at least one of its adjacent cells contain a number STRICTLY GREATER than the number in cell (x,y), or it is adjacent to a red cell. So, in the example given, if we color the cells containing ‘3’, at (1,3) and (3,1), all cells will be reachable except the cells containing ‘2’ at (1,1) and (3,3). These two cells, i.e. (1,1) and (3,3) don’t have any adjacent cell which is colored or has a number strictly greater than itself.
I would also color the cells at (1,1) and (3,3). Hence my answer for the example is:

  1. No. of colored cells : 4
  2. Least number among the colored cells : 2

My interpretation renders the example incorrect. And so I believe I’m missing out some important fact in the question. Don’t give me the logic to solve the question; just tell me how the given example in question is correct.
Thank You!

1 Like
2

Hello @anon22682649 !!,

Even I was solving this problem a some days ago and even I had the same doubt
Then I understood that I was assuming something …

In the problem it has stated that you can go from (x,y) to any cell in the yth column or xth row
You are assuming that you can go to the cell (x,y) only from the adjacent cells

So after i read the problem 3-4 times even I understood my mistake

Hope you understood what I told .

Sudheera Y S
:smile: :slightly_smiling_face:

3 Likes
3

Pls reply if you understood or ask me what you didn’t understand

2 Likes
4

Thanks a lot @sudheerays123 ! I understand the question now. :slight_smile: The only grid questions I’ve ever done are those where one can move to adjacent cells only. And so out of habit I took that to be implicit in this question, although nowhere mentioned.

1 Like
5

Hey there,

The problem lies in the fact that from a position (x, y), we can move anywhere in the same column or row, and not only to the adjacent cells.

For example: we can move to the position (x + 4, y) if it is within the bounds and the number in (x, y) is strictly greater than the number in (x + 4, y).

This is what you were missing out on.

Hope this helps. :slight_smile:

2 Likes
6

Yes I understood. @sudheerays123 also clarified this fact. Thanks for helping me out! :smiley:

1 Like