135 - No Rectangles

[Andre060]

I need some help with this problem please..
specifically, an efficient way of determining how to place the points in the grid.
I tried a linear scan method, putting a point if it doesn't viloate the problem rules, and then rolling back and going to the next point when a line can't be filled with enough points to satisfy the problem. Theoretically this would work, and it works in practice for k<=5, but after that there are just too many possibilities to check brute-force like that.

There has to be a "smart" way of figuring out where to put the points.. any one have any ideas?

Thanks,
Andre

[..]

Hi,

I am trying to solve 135.
I have tried to use backtrack, but it will case Time Limit Exceed........
I searched a solution from Internet. The solution used a smart way that marks the correct points directly, but I don't understand, can anyone tell me the trick in this solution?

In the solution, the program is trying to mark the 2d array by the following code:

Code: Select all

mark(1, 1);
	for s := 1 to k do
	for t := (s - 1) * (k - 1) + 2 to s * (k - 1) + 1 do begin
    		mark(s, t); mark(t, s) 
	end;

	for u := 1 to k - 1 do
  	for v := 1 to k - 1 do begin
    		s := u * (k - 1) + 2;
    		t := v * (k - 1) + 2;
    		for w := 0 to k - 2 do
      		mark(s + (w + (u - 1) * (v - 1)) mod (k - 1), t + w);
  	end;

<font size=-1>[ This Message was edited by: .. on 2002-02-03 08:52 ]</font>

<font size=-1>[ This Message was edited by: .. on 2002-02-03 18:14 ]</font>

[wyvmak]

i'm not sure if i'm correct. but i guess
1. if all numbers in a row +1, +2, ... won't duplicate.
2. if all numbers between columns increment by different number, won't duplicate. reason:
i think one keyword in the problem is 'prime'. which means numbers won't duplicate.

[..]

By printing out the grid marked by these codes, I found the pattern that the code wants to generate.
BUT, I still don't know what the pattern means in number theory. I think this question can be related to number theory. This is the part I am deeply interested in

Code: Select all

mark(1, 1); 
for s := 1 to k do 
for t := (s - 1) * (k - 1) + 2 to s * (k - 1) + 1 do begin 
mark(s, t); mark(t, s) 
end;

This part marks the top part and left part of the grid with a simple,symmetric pattern

Code: Select all

for u := 1 to k - 1 do 
for v := 1 to k - 1 do begin 
s := u * (k - 1) + 2; 
t := v * (k - 1) + 2; 
for w := 0 to k - 2 do 
mark(s + (w + (u - 1) * (v - 1)) mod (k - 1), t + w); 
end;

From the last part of code, a square(at bottom right corner of gird) of length (k-1)^2 is remain un-marked. This part of code will mark it by dividing the square into (k-1)^2 small squares of length (k-1)
The pattern of a small square is got by left-shifting its left neighbour. And the distance of shift is related to the "depth" of that small square in the whole grid.....

[MegaS]

Just try to get the formula of positions in the (n-1)^2 * (n-1)^2 square(right and down)
see the result for n=4:
1 2 3 4
1 5 6 7
1 8 9 10
1 11 12 13
2 5 8 11
2 6 9 12
2 7 10 13
3 5 9 13
3 6 10 11
3 7 8 12
4 5 10 12
4 6 8 13
4 7 9 11

[Adil]

hello there guys, any hint on how to solve 135 ["No Rectangles"] would help.

thanx

[wyvmak]

i forget exactly how i solve it. but think about prime number sequences.

eg. for n=5
start from 1, 1+(i*j) , j=0,1,2,3,4
for i=0, then { 1,1,1,1,1 }
for i=1, { 1,2,3,4,5 }
for i=2, { 1,3,5,2,4 }
for i=3, { 1,4,2,5,3 }
for i=4, { 1,5,4,3,2 }

you see that there's no rectangle. hope that helps. and wish what i'm saying is correct.

[Alvaro]

I'll illustrate the solutions with 4 ones per row and column. They work with any (p+1), with p being a prime number. Here, p=3, in problem 135, p=11.

SOLUTION 1)
Start building this part of the matrix:

Code: Select all

1111000000000
1000111000000
1000000111000
1000000000111
0100
0100
0100
0010
0010
0010
0001
0001
0001

Now we build 3x3 blocks of size 3x3 each (pxp blocks of size pxp each). We do it by building a table similar to the one wyvmak proposed (using i*j instead of 1+(i*j)):

Code: Select all

0 0 0
0 1 2
0 2 1 <- It's 1 and not 4 because we are computing everything modulo p

Substitute each number by the identity matrix of size pxp "rotated" as many places to the right as indicated by the number in the table.

Code: Select all

1 0 0 1 0 0 1 0 0
0 1 0 0 1 0 0 1 0
0 0 1 0 0 1 0 0 1
1 0 0 0 1 0 0 0 1
0 1 0 0 0 1 1 0 0
0 0 1 1 0 0 0 1 0
1 0 0 0 0 1 0 1 0
0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 1 0 0

Now complete the matrix using this piece.


SOLUTION 2)
Build the adjacency matrix of the projective plane over the field with p elements. Definitions available upon request.

[El-idioto]

Hi all,

I'm stuck on this problem.
From 6 dots per line onwards my algorithm fails. E.g., for k=6 I seem to be missing 12 rows.
Can someone tell me their output for k=5, k=6, and k=7?

Code: Select all

k=1
 1

k=2
 1  2
 1  3
 2  3

k=3
 1  2  3
 1  4  5
 1  6  7
 2  4  6
 2  5  7
 3  4  7
 3  5  6

k=4
 1  2  3  4
 1  5  6  7
 1  8  9 10
 1 11 12 13
 2  5  8 11
 2  6  9 12
 2  7 10 13
 3  5  9 13
 3  6 10 11
 3  7  8 12
 4  5 10 12
 4  6  8 13
 4  7  9 11

k=5
 1  2  3  4  5
 1  6  7  8  9
 1 10 11 12 13
 1 14 15 16 17
 1 18 19 20 21
 2  6 10 14 18
 2  7 11 15 19
 2  8 12 16 20
 2  9 13 17 21
 3  6 11 16 21
 3  7 10 17 20
 3  8 13 14 19
 3  9 12 15 18
 4  6 12 17 19
 4  7 13 16 18
 4  8 10 15 21
 4  9 11 14 20
 5  6 13 15 20
 5  7 12 14 21
 5  8 11 17 18
 5  9 10 16 19

k=6 (missing 12 rows)
 1  2  3  4  5  6
 1  7  8  9 10 11
 1 12 13 14 15 16
 1 17 18 19 20 21
 1 22 23 24 25 26
 1 27 28 29 30 31
 2  7 12 17 22 27
 2  8 13 18 23 28
 2  9 14 19 24 29
 2 10 15 20 25 30
 2 11 16 21 26 31
 3  7 13 19 25 31
 3  8 12 20 26 29
 3  9 15 21 22 28
 3 10 16 18 24 27
 3 11 14 17 23 30
 4  8 14 21 25 27
 5  8 15 17 24 31
 6  8 16 19 22 30

k=7 (missing 24 rows)
 1  2  3  4  5  6  7
 1  8  9 10 11 12 13
 1 14 15 16 17 18 19
 1 20 21 22 23 24 25
 1 26 27 28 29 30 31
 1 32 33 34 35 36 37
 1 38 39 40 41 42 43
 2  8 14 20 26 32 38
 2  9 15 21 27 33 39
 2 10 16 22 28 34 40
 2 11 17 23 29 35 41
 2 12 18 24 30 36 42
 2 13 19 25 31 37 43
 3  8 15 22 29 36 43
 3  9 14 23 28 37 42
 3 10 17 24 31 32 39
 3 11 16 25 30 33 38
 3 12 19 20 27 34 41
 3 13 18 21 26 35 40

[Ryan Pai]

Let A=k-1, and suppose you have an AxA grid and want to mark one point on each row, r, and one point on each column, c. If you write the pairs (r,c) then what you end up with is a permutation of the first A positive integers.
In particular look at the cyclic permutations:
I (the identity), (1,2,3...A), (2,3...A,1), (3...,A,1,2) etc. There will be exactly A of these. They have a cool property: If you apply the permutation,P (thinking of it as a function now), to an integer, a to get the element P(a), and you apply another permutation, Q, to a and get Q(a) then P=Q if and only if P(a)=Q(a). If you look at a few examples I'm sure you can see why this property holds.

Now if you look at the finite field of size A, and produce a copy of its multiplication table, then each row has A different elements in it, and each column has A different elements in it. Thus if you think of the grid as being the multiplication table, and each AxA subgrid as being an element in that where it is associated with one of the special permutations above, then each row in the larger grid will get A points, each column will get A points, and there will be no rectangles produced.

You have to add the first loop to get K points.

[Jan]

Can anyone explain the problem with at least one example...

Thanks..

[Jan]

I finally got Accepted. Thanks to Alvaro.

And El-idioto, the problem states that k-1 will be 0, 1 or prime. So, there is no input like k=5 or k=7.

Here are some outputs.

Output:

Code: Select all

k=1
1

k=2
1 2
1 3
2 3

k=3
1  2  3
1  4  5
1  6  7
2  4  6
2  5  7
3  4  7
3  5  6

k=4
1  2  3  4
1  5  6  7
1  8  9 10
1 11 12 13
2  5  8 11
2  6  9 12
2  7 10 13
3  5  9 13
3  6 10 11
3  7  8 12
4  5 10 12
4  6  8 13
4  7  9 11

k=6
1  2  3  4  5  6
1  7  8  9 10 11
1 12 13 14 15 16
1 17 18 19 20 21
1 22 23 24 25 26
1 27 28 29 30 31
2  7 12 17 22 27
2  8 13 18 23 28
2  9 14 19 24 29
2 10 15 20 25 30
2 11 16 21 26 31
3  7 13 19 25 31
3  8 14 20 26 27
3  9 15 21 22 28
3 10 16 17 23 29
3 11 12 18 24 30
4  7 14 21 23 30
4  8 15 17 24 31
4  9 16 18 25 27
4 10 12 19 26 28
4 11 13 20 22 29
5  7 15 18 26 29
5  8 16 19 22 30
5  9 12 20 23 31
5 10 13 21 24 27
5 11 14 17 25 28
6  7 16 20 24 28
6  8 12 21 25 29
6  9 13 17 26 30
6 10 14 18 22 31
6 11 15 19 23 27

Hope it helps.

[ImLazy]

I had tried to draw the points by myself in the case of k = 3 and n = 7. But I failed because it was too difficult. I have no idea about this problem. How do you solve it?

[ImLazy]

I've found the official solution of this problem. It is based on some lemma or formula, thus the code can be very simple. But I don't know how the formula comes. Maybe I needn't know it.

[Ryan Pai]

http://online-judge.uva.es/board/viewtopic.php?t=177
If you're still confused, I could try to explain it in more detail.