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

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

Post by ImLazy » Sat Feb 25, 2006 9:49 am

I've read it and I understand it now. Thank you.
I stay home. Don't call me out.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

hi

Post by sds1100 » Fri Mar 03, 2006 8:29 am

um.. i don't know your program.
ㅋㅋ 짱개면상

renkinjutsushi
New poster
Posts: 2
Joined: Tue Apr 25, 2006 2:44 pm
Location: Bogot

135 WA

Post by renkinjutsushi » Wed Jun 07, 2006 3:29 pm

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.
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 all-singing, all-dancing crap of the world.

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Jun 13, 2006 6:40 am

Yes, the first 100s are okay.
Check for overflows in your code. Or may be any other error, depends on which method you use.
Istiaque Ahmed [the LA-Z-BOy]

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Tue Jun 13, 2006 6:42 am

By the way, the problem number is 136, not 135.
Istiaque Ahmed [the LA-Z-BOy]

williamban
New poster
Posts: 3
Joined: Thu Jul 20, 2006 11:40 am

Post by williamban » Thu Jul 20, 2006 12:31 pm

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: -

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

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. :D
Life is a sine wave where there are many ups and downs.

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

Post by Jan » Thu Jul 20, 2006 7:48 pm

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

black_eagle
New poster
Posts: 1
Joined: Thu Jul 22, 2010 1:24 pm

Re: 135 (with solution inside the post...)

Post by black_eagle » Sat Aug 14, 2010 6:43 pm

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

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 135 - No Rectangles

Post by red_apricot » Tue May 05, 2015 3:33 am

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 (k-2) by a cyclic permutation x -> (x+t)%(k-1), 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
Secondly, consider a group of order (k-1) 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 (k-1)-by-(k-1) 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 k-th mark to the row/column?
3) finally, it's not obvious why there should be no rectangles produced.

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re: 135 - No Rectangles

Post by rafastv » Sun Jul 09, 2017 5:09 am

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.

Post Reply

Return to “Volume 1 (100-199)”