edited by
12,974 views
71 votes
71 votes
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 _____.
edited by

9 Answers

Best answer
87 votes
87 votes

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}$$

edited by
13 votes
13 votes

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 

12 votes
12 votes

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.

7 votes
7 votes

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 

Answer:

Related questions

44 votes
44 votes
3 answers
1
35 votes
35 votes
12 answers
2
go_editor asked Feb 12, 2015
30,005 views
A binary tree T has $20$ leaves. The number of nodes in T having two children is ______.
38 votes
38 votes
5 answers
3
36 votes
36 votes
6 answers
4
go_editor asked Feb 13, 2015
15,514 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.