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

The answer should be $5$. 

1. We first need to shift $2$ in place of $1$ keeping $5$ AND $14$ intact as it isn't mentioned in the question that the entire row elements move.
2. $4$ is shifted up,next to $2$ (keeping $12$ and infinity intact in column $2$).
3. Now in second row $6$ is shifted left.
4. $18$ shifts up to the second row
5. And finally $25$ is shifted left to the third column.

So, this takes $5$ moves and still maintains the tableau property. Also infinity is placed to the right of $25$ and below $23$ (unfilled entries to be filled with $\infty$ ). The final table would look as follows.
$$\begin{array}{|l|l|l|l|}\hline \text{2}  &  \text{4}&  \text{5} &  \text{14}  \\\hline  \text{3} & \text{6} &  \text{18} &  \text{23}  \\\hline  \text{10} & \text{12}  &  \text{25} &  \infty  \\\hline  \text{31} & \text{$\infty$} &  \text{$\infty$} &  \text{$\infty$}  \\\hline \end{array}$$

Comments

Are diagonal shifts allowed here? Please someone mention which types of moves allowed and which types aren’t allowed.

---

These are the qs that give immense dopamine shot when we get the correct answer :)

---

@Anupreet13 as this is array so how diagonal shift is allowed? if this is possible then ans should be 4

Answer 2

Answer is 5. 

And shifts are, 

Shift 1 -  2- left 

Shift 2-  4-up

Shift 3- 6 - left 

Shift 4-  18-up

Shift 5-  25 left 

Comments

Wondering what concept of computer science , they are wishing to test through this question

---

only your answer is solved according to the question specifications with exact approach in a detailed manner.

---

Thanks @sal

---

@dev will explained.

---

solve using GREEDY method

shift unfilled entry (∞) with min of (right entry , below entry )

---

same thing occurred to me when i first attempted this question
after some thinking i noticed some similarities to concept of heap ,
here 1 is like the root of heap and elts. on row a[i][j+1] >  a[i][j]  and also along col a[i+1][j]>a[i][j]
suggesting them to be looked upon as the left and right child of heap ,then every elt has heap property
the difference from heap would be that elts of left and right sub-tree can be shared also which is not the case with heap ,Also the shifting procedure sounds very similar to how we fix heap after removing elt
So if you model this structure as similar to heap and try to  move elts. keeping fix heap in back of your mind and use ideas from it like comparing left and right children and moving smaller one above
So i think in that sense it is a great question as they wanted to check if (i) we can identify the similarity with heap and (ii) apply heap algorithms in this new setting
Unfortunately a kind of ad-hoc approach also works somewhat on the lines of hit and trail which most people did and got two marks and the beauty of this question could never be realized.

---

not in all cases i think

Answer 3

A Young Tableau is a matrix, such that each row, as well as each column is sorted in ascending order,

 

The most optimal solution to rearrangement in this grid-like structure is to move in a zig-zag manner,as shown.

5 is the answer.

Answer 4

Actually, the element deleted is replaced by by infinity in that cell of the Young Tableau. And, then we perform an operation called Youngify(Y, i, j) where Y is the 2D-Young matrix, i and j are the coordinates of the element deleted.

This function sets the blank/infinity created by the deletion of the element in its proper position by rearranging the Young Tableau much like the heapify procedure.

Please refer this PDF which contains the details - https://lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf

The blank/infinity is compared with the immediate right and immediate bottom element each time and the smallest is exchanged with it out of the 2. This procedure ultimately arranges all the elements in their correct position.

Eg :-  Youngify on position Y[1, 1] :- The position Y[1, 1] = INF, is compared with position Y[1, 2] = 2 and position Y[2, 1] = 3, the smaller one is Y[1, 2] is exchanged with Y[1, 1] and now Y[1, 2] becomes INF. Now same procedure is repeated for Y[1, 2] and so on.. 

 2   4    5 14

 3   6  18 23

10 12  25 oo

31 oo oo oo 

Comments

@ravi , so final answer is 5 right ??

---

This will give the result but do we hav to maintain property at each step that nothing is to the right and below 00

---

Got answer