135 - No Rectangles

[ImLazy]

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

[sds1100]

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

[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.

[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.

[the LA-Z-BOy]

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

[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.

[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.

[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

[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.

[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.