A Puzzle
It has been a while. Consider array A[1..n,1..n] such that any rectangle A[i...j,k...l] has at least one element that appears exactly once in the rectangle. What is the smallest number distinct elements A can have?
Labels: aggregator
posted by metoo at 10:16 AM
7 Comments:
Here's an upper bound.
In one dimension, you can use log n elements. Suppose by induction this is true for A[1..n], then we introduce one new element E not contained in A[1..n] and place E at A[n+1] and place a copy of A[1..n] at A[n+2..2n+1], which doubles the size of the array adding only one new element. Any subarray either contains the new element exactly once at position A[n+1], or is a subarray of the inductive case and so inductively satisfies the requirement.
In two dimensions, do the same trick using the 1D array from above instead of a single new element. Suppose inductively we can make an n x n square with the property. Then use log n new elements to make a 2n+1 x 2n+1 "cross", placing four copies of A[1..n,1..n] in each of the four corners of the cross. We doubled n while adding only log n new elements, so this shows log^2 n is an upper bound.
log n is a lower bound. One could start with the full square with k unique elements and know that there must be an element appearing exactly once, at position A[i,j]. Take the widest rectangle going from [i,j] to a corner, which must be at least half the full width and contains at most k-1 unique elements.
Not sure how to prove log^2 n is a lower bound or that log n is an upper bound.
Great.
You can do O(log n) for 2D.
-- Metoo
Dave, in 2D case, you can double n by just placing only two new elements, one at the center of the cross, and one at the four midpoints along the four arms of the cross. Rest of the cross can be filled with values of elements that are already present in the previous matrix. That would give a solution of 2 log(n) - 1
If there is a matrix A of size 2^k - 1 that satisfies this condition, the center will be 2k-1, and the center of the four mid point of the segments will be 2k-2. Rest of the matrix does not contain values 2k-1 or 2k-2.
So, place A along four corners, with the empty cross in between. Place 2(k+1)-1 at the center of the cross, and place 2(k+1)-2 at the four midpoints. Place the center of the previous level matrix (2k-1) at midpoints of the eight empty segments, and place 2k-2 at the mid points of the 16 segments, and so on. The cross has 4*(2^k-1) + 1 slots in total, which are filled by 2k+1 (once), 2k (x4), 2k-1 (x8), etc., up to k.
For any rectangle that includes a portion of the cross, the maximum in that portion of the cross will be unique and higher than rest of the elements in the rectangle -- needs proof by induction.
Btw, an interesting algorithmic question is the following:
There are many A's that satisfy the property above. Find some A such that the point query A[i,j] can be answered quickly.
-- Metoo
Something interesting I noticed...
def A(i,j):
res = 1
while not i%2: i = i/2; res = res + 1
while not j%2: j = j/2; res = res + 1
return res
For any two numbers between 1 and 2^(n+1) - 1 (i.e., n-bit numbers), the maximum number of right shifts is (n-1) each, so, the maximum value is 2*n - 1
There is something I don't understand about the wording of the problem :
Any subrectangle has at least one element that appears exactly once.
Hence, any A[i..i, k..k] subarray has one element that appears exactly once : all elements in the array are unique.
What am I missing ?
Any subrectangle has at least one element that appears exactly once... in that subrectangle (versus in the entire array), so as we keep expanding the rectangle, a new unique number may come up.
Check the simple example below to see that see that any subrectangle has a unique element. In this case, n = 2^3 -1, and we can fill it in with just 2*3 - 1 numbers
1 2 1 3 1 2 1
2 3 1 4 2 3 1
1 2 1 3 1 2 1
3 4 3 5 3 4 3
1 2 1 3 1 2 1
2 3 1 4 2 3 1
1 2 1 3 1 2 1
Post a Comment
<< Home