135 - No Rectangles
Moderator: Board moderators
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
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:
<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>
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 18:14 ]</font>
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
This part marks the top part and left part of the grid with a simple,symmetric pattern
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.....
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;
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;
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.....
-
- 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"]?
hello there guys, any hint on how to solve 135 ["No Rectangles"] would help.
thanx
thanx
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.
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.
Two solutions
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:
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)):
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.
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.![:)](./images/smilies/icon_smile.gif)
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
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
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
SOLUTION 2)
Build the adjacency matrix of the projective plane over the field with p elements. Definitions available upon request.
![:)](./images/smilies/icon_smile.gif)
-
- New poster
- Posts: 45
- Joined: Mon Jul 14, 2003 9:42 pm
- Location: Zoetermeer, The Netherlands
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?
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
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.
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.
Can anyone explain the problem with at least one example...
Thanks..
Thanks..
Ami ekhono shopno dekhi...
HomePage
HomePage
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:
Hope it helps. ![:)](./images/smilies/icon_smile.gif)
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
![:)](./images/smilies/icon_smile.gif)
Ami ekhono shopno dekhi...
HomePage
HomePage
135 - No Rectangles
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.
http://online-judge.uva.es/board/viewtopic.php?t=177
If you're still confused, I could try to explain it in more detail.
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.