Posted:

**Sat Feb 25, 2006 9:49 am**I've read it and I understand it now. Thank you.

Page **2** of **2**

Posted: **Sat Feb 25, 2006 9:49 am**

I've read it and I understand it now. Thank you.

Posted: **Fri Mar 03, 2006 8:29 am**

um.. i don't know your program.

ㅋㅋ 짱개면상

ㅋㅋ 짱개면상

Posted: **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.

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.

Posted: **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.

Check for overflows in your code. Or may be any other error, depends on which method you use.

Posted: **Tue Jun 13, 2006 6:42 am**

By the way, the problem number is 136, not 135.

Posted: **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: -
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.

Posted: **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.

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.

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

@

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

Posted: **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
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.

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

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.

Posted: **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.

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.