135 - No Rectangles

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Andre060
New poster
Posts: 1
Joined: Thu Nov 01, 2001 2:00 am

Post by Andre060 » Thu Nov 01, 2001 10:28 pm

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Feb 03, 2002 9:51 am

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sun Feb 03, 2002 3:56 pm

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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Feb 03, 2002 7:20 pm

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
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am

Post by MegaS » Tue Feb 05, 2002 12:17 pm

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
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Any hint on 135["No Rectangles"]?

Post by Adil » Sun Sep 29, 2002 12:21 pm

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

thanx

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sun Sep 29, 2002 2:32 pm

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
New poster
Posts: 2
Joined: Fri Oct 11, 2002 9:11 pm

Two solutions

Post by Alvaro » Fri Oct 11, 2002 9:24 pm

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
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto » Tue Jan 27, 2004 1:29 am

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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Tue Apr 26, 2005 8:05 pm

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.
I'm always willing to help, if you do the same.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Jul 23, 2005 6:24 am

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

Thanks..
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Aug 26, 2005 10:52 pm

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. :)
Ami ekhono shopno dekhi...
HomePage

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

135 - No Rectangles

Post by ImLazy » Fri Feb 17, 2006 10:11 am

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?
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Feb 20, 2006 5:25 am

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.
I stay home. Don't call me out.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Tue Feb 21, 2006 3:17 am

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

Post Reply

Return to “Volume 1 (100-199)”