Page 2 of 2

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

hi

Posted: Fri Mar 03, 2006 8:29 am
by sds1100
um.. i don't know your program.
ㅋㅋ 짱개면상

135 WA

Posted: Wed Jun 07, 2006 3:29 pm
by renkinjutsushi
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.

Posted: Tue Jun 13, 2006 6:40 am
by the LA-Z-BOy
Yes, the first 100s are okay.
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 LA-Z-BOy
By the way, the problem number is 136, not 135.

Posted: Thu Jul 20, 2006 12:31 pm
by williamban
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

Posted: Thu Jul 20, 2006 7:48 pm
by Jan
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.

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

Posted: Sat Aug 14, 2010 6:43 pm
by black_eagle
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

Re: 135 - No Rectangles

Posted: Tue May 05, 2015 3:33 am
by red_apricot
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.

Re: 135 - No Rectangles

Posted: Sun Jul 09, 2017 5:09 am
by rafastv
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.