GATE CSE 2015 Set 2 | Question: 31

Question

A Young tableau is a $2D$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$, and hence there cannot be any entry to the right of, or below a $\infty$. The following Young tableau consists of unique entries.
$$\begin{array}{|l|l|l|l|}\hline \textbf{1}  &  \text{2}&  \text{5} &  \text{14}  \\\hline  \text{3} & \text{4} &  \text{6} &  \text{23}  \\\hline  \text{10} & \text{12} &  \text{18} &  \text{25}  \\\hline  \text{31} & \text{$\infty$} &  \text{$\infty$} &  \text{$\infty$}  \\\hline \end{array}$$
When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled with a $\infty$). The minimum number of entries (other than $1$) to be shifted, to remove $1$ from the given Young tableau is _____.

Comments

The algorithmic solution to this was asked as a question in GATE 1996

https://gateoverflow.in/2766/gate1996-14

---

Once an entry a[i][j] is moved then min(a[i+1][j], a[i][j+1]) will take that position, and this goes on.
1 is removed, min (2,3) = 2.   2 takes 1's position

Now 2 is removed, min (4,5) will take its position.
We do this till we reach to the end.

Source: comments below.

---

smsubham

$best$ $solution$

---

@Sachin Mittal 1 sir to which topic of Algorithm can I relate this question to ?

Answer 1

sir may i think this Young tableau as  min heap.. delete 1 and it should filled by 31.. then just apply modified heapify procedure to get desired Young tableau..
removal of 1 and replacement of 1s position with 31 is single atomic operations so shift should not be counted..

later only swaps (modified heapify) required..
31 with 2,
31 with 4,
31 with 6,
31 with 18,
31 with 25..

is it not right way ???

Comments

I think ,In question movements are allowed not the jumps .So we cannot  put 31 directly in place of 1.

Answer 2

Ans is 5, shift 2,5,14 to left and 23,25 up.

 

Edit: these shift moves will violate the Young Table property, So we have to shift 2,4,6,18 and 25 in zig-zag fashion.

Comments

@Pragy Agarwal Shouldn't algorithm stop shifting once it has encountered an infinity. Because after that, all shifting will be of infinity elements only. Once it is clear that only infinty element can be shifted in empty cell, just fill that cell with infinity and stop. This method because it's been asked to minimize the shifting of elements.

---

@Arjun sir with m rows and n column.

time complexity to delete smallest  element is O(m+n) 

time complexity to delete largest  element is O(m+n) 

time complexity to delete element is O(m+n) ryt?

---

sir, i think here they are saying that unfilled entries at the end of shift will be marked as infinite.

Answer 3

Answer: 6

Shift $2,4,6,18,25, \infty$ in a zig-zag manner.

2	4	5	14
3	6	18	23
10	12	25	∞
31	∞	∞	∞

Comments

I don't think we need to count ∞ shift. we just have to fill the unfilled entries.

---

there cannot be any entry to the right of, or below a ∞..
entry 31   violate this condition..
der is  infinity after 25..
correct me ..

---

How is 31 below $\infty$? Are you talking about the $\infty$ on the extreme right?

 

Well, the question means that within a row, nothing must be to the right of an $\infty$, and in a column nothing must be below an $\infty$.

Since there is no $\infty$ before 31 in the first column, it's all fine.

Answer 4

After removing 1

 

NULL	2	5	14
3	4	6	23
10	12	18	25
31	Infinite	Infinite	Infinite

 

NULL moves right:

(Note: NULL cannot move down because it will contradict the given question conditions. Hence, we have to move right.)

 

2	NULL	5	14
3	4	6	23
10	12	18	25
31	Infinite	Infinite	Infinite

 

NULL moves down:

 

2	4	5	14
3	NULL	6	23
10	12	18	25
31	Infinite	Infinite	Infinite

 

NULL moves right:

 

2	4	5	14
3	6	NULL	23
10	12	18	25
31	Infinite	Infinite	Infinite

 

NULL moves down:

 

2	4	5	14
3	6	18	23
10	12	NULL	25
31	Infinite	Infinite	Infinite

 

NULL moves right:

 

2	4	5	14
3	6	18	23
10	12	25	NULL
31	Infinite	Infinite	Infinite

 

Now in question given that " Unfilled entries are filled with infinite

Therefore:

2	4	5	14
3	6	18	23
10	12	25	Infinite
31	Infinite	Infinite	Infinite

 

 

We will not bring NULL to the bottom right because question is asked to find the minimum.

Since total 5 movements of NULL is involved:

 

The answer will be 5