135  No Rectangles
Moderator: Board moderators

 New poster
 Posts: 2
 Joined: Tue Apr 25, 2006 2:44 pm
 Location: Bogot
135 WA
According to my program the first 100 ugly numbers are:
1
2
3
4
5
6
8
9
10
12
15
16
18
20
24
25
27
30
32
36
40
45
48
50
54
60
64
72
75
80
81
90
96
100
108
120
125
128
135
144
150
160
162
180
192
200
216
225
240
243
250
256
270
288
300
320
324
360
375
384
400
405
432
450
480
486
500
512
540
576
600
625
640
648
675
720
729
750
768
800
810
864
900
960
972
1000
1024
1080
1125
1152
1200
1215
1250
1280
1296
1350
1440
1458
1500
1536
Can someone confirm this? Whatever I do I get WA with the 1500th.
Thanks.
1
2
3
4
5
6
8
9
10
12
15
16
18
20
24
25
27
30
32
36
40
45
48
50
54
60
64
72
75
80
81
90
96
100
108
120
125
128
135
144
150
160
162
180
192
200
216
225
240
243
250
256
270
288
300
320
324
360
375
384
400
405
432
450
480
486
500
512
540
576
600
625
640
648
675
720
729
750
768
800
810
864
900
960
972
1000
1024
1080
1125
1152
1200
1215
1250
1280
1296
1350
1440
1458
1500
1536
Can someone confirm this? Whatever I do I get WA with the 1500th.
Thanks.
You're not your job. You're not how much money you have in the bank. You're not the car you drive. You're not the contents of your wallet. You're not your fucking khakis. You're the allsinging, alldancing crap of the world.

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:

 New poster
 Posts: 3
 Joined: Thu Jul 20, 2006 11:40 am
Hi..
I thought I have solved this problem (135) but it returned with a Wrong Answers. I'm not sure what's wrong with it, so I hope someone here can give me a helping hand.
The following is some of the output: 
The only difference I see is the order of the solutions, but I thought that' not the main issue of requirement for this problem. If this is the one that causes the error, please tell me..
Thanks in advance.
I thought I have solved this problem (135) but it returned with a Wrong Answers. I'm not sure what's wrong with it, so I hope someone here can give me a helping hand.
The following is some of the output: 
Code: Select all
1
1
2
1 2
1 3
2 3
3
1 2 3
1 4 5
1 6 7
2 4 7
2 5 6
3 4 6
3 5 7
4
1 2 3 4
1 5 6 7
1 8 9 10
1 11 12 13
2 5 9 13
2 6 10 11
2 7 8 12
3 5 10 12
3 7 9 11
3 6 8 13
4 5 8 11
4 7 10 13
4 6 9 12
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 13 19 25 31
2 8 14 20 26 27
2 9 15 21 22 28
2 10 16 17 23 29
2 11 12 18 24 30
3 7 14 21 23 30
3 11 13 20 22 29
3 10 12 19 26 28
3 9 16 18 25 27
3 8 15 17 24 31
4 7 16 20 24 28
4 10 14 18 22 31
4 8 12 21 25 29
4 11 15 19 23 27
4 9 13 17 26 30
5 7 12 17 22 27
5 10 15 20 25 30
5 8 13 18 23 28
5 11 16 21 26 31
5 9 14 19 24 29
6 7 8 9 10 11
6 22 23 24 25 26
6 12 13 14 15 16
6 27 28 29 30 31
6 17 18 19 20 21
Thanks in advance.
Life is a sine wave where there are many ups and downs.
To williamban,
You can write a manual judging code. After that run that code for several inputs and verify the outputs with the judging code.
I think you will find your error. And the order of the values is not important here. Any yellow marked problem has multiple output and all correct outputs should be accepted by the judge.
Hope it helps.
You can write a manual judging code. After that run that code for several inputs and verify the outputs with the judging code.
I think you will find your error. And the order of the values is not important here. Any yellow marked problem has multiple output and all correct outputs should be accepted by the judge.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 1
 Joined: Thu Jul 22, 2010 1:24 pm
Re: 135 (with solution inside the post...)
hi:
@ Ryan Pai
can please you explain your soln by example?
i mean for k=2 ,n=3
grid will be like that :
110
101
011
how can i apply your theory to get this solution
thanks in advance
@ Ryan Pai
can please you explain your soln by example?
i mean for k=2 ,n=3
grid will be like that :
110
101
011
how can i apply your theory to get this solution
thanks in advance

 New poster
 Posts: 48
 Joined: Sun Jun 22, 2014 6:14 am
Re: 135  No Rectangles
I'm trying to take in the "finite field & cyclic permutation" approach to this problem.
OK, so let's identify each number t from 0 to (k2) by a cyclic permutation x > (x+t)%(k1), or, rather, with its matrix representation. For example, the cycle (0 1 2) has representaion
Secondly, consider a group of order (k1) and its multiplication table. Obviously, no two entries in a given row (column) are equal, other wise we would have a*b = a*c => b = c. Now replace each number in this (k1)by(k1) table by its matrix representation.
This is what Ryan Pai says.
What I can't figue out is:
1) why he talks of finite fields rather than groups?
2) how does one add the last kth mark to the row/column?
3) finally, it's not obvious why there should be no rectangles produced.
OK, so let's identify each number t from 0 to (k2) by a cyclic permutation x > (x+t)%(k1), or, rather, with its matrix representation. For example, the cycle (0 1 2) has representaion
Code: Select all
0 1 0
0 0 1
1 0 0
This is what Ryan Pai says.
What I can't figue out is:
1) why he talks of finite fields rather than groups?
2) how does one add the last kth mark to the row/column?
3) finally, it's not obvious why there should be no rectangles produced.
Re: 135  No Rectangles
If you are stuck in this problem some tips for you:
1) DO NOT TRY BRUTE FORCE testing for rectangles or creating all of them, O(nˆ4) and O(nˆ3) is too much for this algorithm.
2) Look into projective spaces (study about them a little if you need, lot of videos in YouTube). The FANO plane is a projective space of order 2 that is exactly the solution for K=3 (See: http://www.donnadietz.com/PG/ThirdFano.html).
For some of you who have trouble understanding why this works, in a projective space there are no parallel lines, therefore there cannot be a rectangle by default which means:
3) Every 2 lines meet in a single point.
4) Every space has K vanishing points.
5) Take a really long look at the formula for N, the major tip of the problem is there (staring at you).
Btw it is really fun doing the projective spaces by hand once you figure it out.
1) DO NOT TRY BRUTE FORCE testing for rectangles or creating all of them, O(nˆ4) and O(nˆ3) is too much for this algorithm.
2) Look into projective spaces (study about them a little if you need, lot of videos in YouTube). The FANO plane is a projective space of order 2 that is exactly the solution for K=3 (See: http://www.donnadietz.com/PG/ThirdFano.html).
For some of you who have trouble understanding why this works, in a projective space there are no parallel lines, therefore there cannot be a rectangle by default which means:
3) Every 2 lines meet in a single point.
4) Every space has K vanishing points.
5) Take a really long look at the formula for N, the major tip of the problem is there (staring at you).
Btw it is really fun doing the projective spaces by hand once you figure it out.