bayram's blog

Young tableaus
By bayram, 11 years ago, In English

An MxN Young tableau is an MxN matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be infinity, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold r <= mn finite numbers.

How to find an O(M+N) — time algorithm to determine whether a given number is stored in a given MxN Young tableau?
(source : Introduction to Algorithms)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Hint: Can you find a way to eliminate an entire row or column of the tableau based on the value of the top-right element?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are nonexistent infinity elements placed to the right/bottom edge of the tableau (since rows and columns are sorted); or they could appear anywhere in the matrix?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    4x3 young tableau matrix
    1 inf inf
    2 inf inf
    3 inf inf
    4 inf inf

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you have an opencup account (or friend who has XD) you can check your solution there. problem link (C): http://opencup.ru/files/oce/gp2/problems-e.pdf

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it 
bool search (int a[N][M], int x) {
	int i=0, j=M-1;
	while (i<N && j>=0) {
		if (a[i][j] == x)
			return true;
		if (a[i][j] < x)
			i++;
		else
			j--;
	}
	for (; i<N; i++)
		if (a[i][j] == x)
			return true;
	for (; j>=0; j--)
		if (a[i][j] == x)
			return true;
	return false;
}
→ Reply