I've got an O(n^3) algo that seems to run all of the test input I can come up with very quickly. I'm just wondering if anyone has any input that might cause my TLE or any advice on how much I need to optimize this thing.
Thanks!
Peter
786 - Working with Relations
Moderator: Board moderators
-
brianfry713
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 786 - Working with Relations
inputAC output:
Code: Select all
89419 = E
F >= C
B > 71187
39382 >= J
F >= 93008
D < 87640
I <= 97345
31064 >= 12018
I = I
71332 <= 69771
-
A <= 14700
D < 89969
F >= C
J = F
93282 < 52964
63777 >= 36887
12275 <= 96140
67508 <= F
91401 > I
77610 < J
-
42783 < 19156
B <= C
65112 > J
73489 <= 59338
99030 = 40679
D <= C
23890 >= 19641
62232 > 62348
45152 >= E
J <= H
-
J >= 51131
B >= C
B < 10354
19567 < 47977
55161 < 66067
E <= 11476
43326 <= 25543
C < 58865
32435 = H
D < H
-
70027 > 38160
C < 74490
E > H
33259 <= 1088
15161 = 77135
A = E
39605 < 35508
75668 >= 33258
56004 > 46719
5079 < 93344
-
85530 >= 41258
F >= A
G > 95967
G >= I
A > 90101
43937 > C
60969 < 19850
D > 17326
7557 > 14357
J > I
-
H > E
17098 = 48299
E >= E
38481 = E
D >= 73549
67292 >= A
54462 >= 11575
G <= 71373
17932 < 64604
52473 <= D
-
A = H
F > E
25949 > C
631 >= 20878
89649 = 70984
20340 >= 46698
23709 >= 91359
36686 > 88305
G > 74840
7055 <= H
-
C < 4594
E >= 97305
D <= E
52469 >= B
F > I
90912 >= A
A >= 95734
93750 = 81000
G < 39984
E > G
-
A > 5713
26404 > 53369
55771 >= J
75184 > G
J >= C
H >= 79589
79174 >= 68391
11007 > B
H > 59370
C <= B
-
9113 = 83223
J < 39313
75272 = H
F = 21689
I >= 96855
26687 <= I
13008 <= 17527
E > D
8369 < 21893
43748 > 74662
-
I > 3181
27234 > F
98025 <= G
50897 = C
B = H
B <= 51206
59061 = 62906
55624 >= 9923
39295 = 2684
73072 < I
-
41350 >= 38970
46027 = J
6960 > 50403
42782 <= 66804
6624 >= 9387
85060 > H
14932 = 76415
57038 < H
C < 80002
74708 <= 94915
-
H <= F
H > H
C > 60145
A = C
40753 <= 97883
D > A
D >= A
22226 < D
27853 > I
4357 <= 9296
-
E < J
46182 > I
C > C
D >= 84241
73212 <= 10848
E >= J
9786 = C
B > 4967
85626 <= F
G > D
-
80225 < 78291
I = C
C > 83206
52982 > H
89486 > 18271
G <= D
J >= 65841
E >= 52925
A > 87998
E = D
-
681 >= 22436
65433 > 55014
39287 = A
H >= 62270
J <= 84200
J = 36766
76075 <= 64913
C = 21539
48140 = 75244
91302 > C
-
J >= 85082
F <= J
B >= E
68325 > 89745
51707 <= 17196
8227 > 3256
G = 58326
87759 <= 17627
16836 >= H
53235 <= A
-
B <= D
A >= H
A > D
J < 93672
C = 93763
25052 >= 13427
18450 < H
75009 <= 58188
B >= I
16493 < G
-
I < 22952
65832 < 85373
G <= 14446
9374 > 76158
C = J
96513 <= 53422
83285 < A
B >= G
I < 25439
58117 < 72894
-
46872 >= 66441
H < 68219
29574 > H
F > 13381
D = H
I < 15536
I = E
21309 >= 70531
B = 84204
G > 78063
-
A > G
91970 > 96060
D > B
60036 = D
56541 <= 41659
D > G
69426 <= A
81386 = 10361
A <= B
D > 57309
-
J >= C
56820 >= 17700
6934 < G
87168 > 97432
83491 <= 33527
71273 >= 24511
13352 > G
17599 < C
61349 = B
A >= G
-
54008 <= 67922
D < A
17121 = 69026
F <= F
B <= D
I = 69975
D = C
B < C
D = E
D >= I
-
B = 16183
85495 = A
B >= 47123
84432 <= 63810
76277 > 71207
79736 >= F
62249 = A
D < 1019
F <= C
92281 >= G
-
26209 <= C
85064 = J
16727 < C
42655 >= J
7842 >= 16100
H >= 24194
38501 >= B
B < 42344
C <= G
E < 71314
-
C >= J
B > E
50857 < B
32787 = 97292
43038 > 79887
C = 19462
A >= 77318
90680 < 93105
F > 50956
I = 42293
-
40063 < 44592
6953 >= D
30535 < 5967
A = 74768
G >= 53143
D = J
H > C
86939 <= 66040
55371 = C
D < 50697
-
C > J
A <= 87024
78224 < J
G >= 20154
32047 <= 63033
36836 >= 39457
F > 89258
G >= 31467
45831 <= 87999
A >= 38212
-
47039 <= F
G >= B
64698 = 1081
D = 81298
92219 >= 55064
48922 < 68528
8585 <= 80948
E > 2289
3549 < D
F >= E
-
J < 11226
F >= A
F <= 26636
66575 = H
19014 = 56472
56892 <= 46279
24897 = B
59058 <= G
7589 < F
1816 > 63973
-
F = 63418
14793 < A
B < 16363
H = C
D = B
75205 = 22934
B = 39162
D >= H
C < 38645
48338 > 66885
-
J <= C
F < 11037
16409 <= J
2109 < 66177
25356 <= G
G > H
A <= 5290
H > 22893
16342 <= 56633
18648 <= A
-
42427 < E
13441 = 47786
16769 > H
F < E
13837 < D
80992 = I
81854 >= C
G < 10206
B > 1557
632 = 4030
-
28475 > H
54747 > 38857
28646 <= 23391
7782 < 26920
H >= 97362
60823 > C
5519 = J
E >= 58027
78220 = 41997
13484 >= F
-
E >= 93640
D = 85375
2209 = 70321
33048 < E
I > C
30673 <= C
G <= 43690
86905 > A
96391 = F
I < C
-
J > 94169
H = 21884
D = 49655
I > A
F < 79700
G < J
H < A
H >= 37147
E >= G
A <= 93075
-
79072 < G
I <= 89694
33997 >= 71209
32242 >= E
66066 > A
B < 27678
B = C
C >= E
D < 21428
A < 7549
-
86426 = J
60505 <= A
C > 41444
E = D
E >= A
84580 < B
E <= F
74729 > I
H < 22504
79337 = C
-
A <= A
D > 14443
I >= J
87786 > 63754
A <= 68808
A = A
C < 82366
82139 > 60070
C < 90645
23486 < A
-
A <= I
E <= 19008
H >= H
A > 22778
99341 >= H
B = D
61415 = B
72413 <= H
F = H
G < 35050
-
41941 < A
G < C
H = 47429
21943 > I
51565 > C
F > 12822
9175 > C
I >= 88427
D > H
C > F
-
68735 >= 8810
75929 >= 92893
71636 > H
54526 > 12379
4918 >= 30270
E = 7292
C >= B
E < 96891
15215 <= 9275
39861 >= 61928
-
I >= 63233
63253 = 59925
E >= 5138
28599 > 54544
91051 = E
86456 < C
67530 < 11064
52195 <= 14686
31047 <= D
E = G
-
2291 >= H
F <= G
25019 > I
61392 > 5589
F <= G
80971 = C
J = 67727
H = 72082
6288 > E
61655 <= 94704
-
82582 >= E
33801 = 27340
81176 < 66171
66415 <= G
E <= C
44589 < F
50433 = 90758
A >= D
C = 11818
35300 = H
-
73690 < F
56034 > I
J >= 32222
33622 <= F
J >= 62507
J = 41475
I < I
21668 = 14716
G = 66484
62769 < B
-
C >= 9727
D >= G
F = G
B < 98384
E <= 70303
H = H
74339 < B
59595 = F
C <= 59545
77156 < D
-
78437 >= E
83788 > J
D < 25092
I >= H
G >= G
2922 < 88326
J >= B
93297 = 99563
98995 <= 56576
E = B
-
54009 = 62224
15571 >= J
76366 > G
21684 = C
77417 <= 9059
76790 >= C
A < D
1999 < 52127
A >= 66498
D = 20352
-
B > 59149
55285 <= A
I >= 27509
1757 <= 65007
A >= 24542
45398 = 13209
42164 < 74218
C < B
55503 > B
I > 53693
-
22751 > 34138
148 < 95368
64795 <= B
32611 >= I
E < B
89904 <= 57200
I >= 24687
G < G
F = E
B <= 2901
-
92276 < 45873
I >= J
15855 > 79653
J <= 94736
93056 <= A
C <= 93926
63312 < A
G >= 28258
31686 = 20251
79185 < 5009
-
76541 < E
G < 8226
52409 = 42514
89684 < I
G >= B
C > 25228
17411 >= 1102
49133 >= B
I <= F
F < C
-
84238 >= 48982
95385 >= 42141
G = 13285
G >= 78273
D > C
41451 >= 33396
99252 >= 43660
26044 <= D
H >= 31463
412 >= G
-
J <= E
H = D
58790 <= C
F < B
D >= F
F >= 5344
13712 < 70259
50379 > A
92030 = B
32201 >= 35302
-
27202 > 95246
I <= E
17775 < B
A <= 56283
F = I
D < 32274
I <= J
C <= 34503
A = 61860
27510 <= F
-
D >= D
J >= D
H < 76697
G <= 73508
1582 = 73047
F < 57700
2638 <= A
D = 43040
10600 < I
72606 = D
-
97997 < J
E < 79788
11437 <= J
E <= E
33254 <= 53405
87370 <= A
F <= A
55732 > 71859
26707 >= H
27611 > J
-
J < 80356
D <= B
51559 > 99205
C < B
I = A
A < 2690
47016 > 67860
52831 > B
F >= 35678
C = H
-
34599 > 95440
G > D
B > 56733
12446 = J
21236 < C
89693 >= C
73138 > D
20248 > J
93753 <= C
64880 = 52996
-
J > 53785
I < 11610
H <= I
28556 < A
D <= 27815
41774 <= B
F < 53207
E >= 51316
1311 = I
J >= 90865
-
C >= F
24929 > D
G > I
92517 = 29101
9928 < C
I > F
A = J
D = D
F > A
46954 <= I
-
71427 > 9147
I = E
74389 <= 39662
I >= H
J = 67867
19756 >= C
A >= C
A = 69241
C < H
15082 > 9333
-
J = 77009
D <= 7205
45857 >= 1878
J <= 71162
H >= 40403
81727 <= 26552
A >= 8844
F <= B
74765 <= 31525
81831 > 6014
-
I >= 8917
49437 < D
F >= 18055
D < 54882
B < 22726
63047 > 29236
A <= 96425
45816 >= 71006
32601 > H
E <= C
-
24072 >= 928
B < 74420
39338 < H
85247 >= B
G <= 19787
83477 >= H
C = 6527
39450 > 58749
D < 39269
B <= 34062
-
I = 21493
A = 84010
C < F
D = H
F > C
I = 85385
C < G
D <= J
14135 > E
I > D
-
14835 <= G
H < H
71873 = C
35379 <= H
48195 > C
H = J
G <= F
J >= 87933
34329 < 48214
G > 88233
-
26469 < F
13113 < 47916
7123 >= 8139
G < C
B >= 80861
21706 = 19543
19602 >= J
F = G
B >= 51722
G >= H
-
B = A
E <= D
15340 >= B
D <= G
8632 < 29189
I > 22359
A = F
64364 >= 37588
B = H
D <= F
-
C > 72401
F < 86483
23243 < 68247
98117 < 36621
61073 > A
80199 = G
I = J
E = 35379
B = 63804
G < J
-
D = 66201
29877 = A
F = J
A = 54295
38170 > D
27346 < A
20493 < 60934
92658 = 36989
87522 = G
50771 < 88926
-
85971 >= 39758
E >= 29333
C >= 8231
74008 <= 95272
60784 > 90584
35861 < 89532
50912 > C
11323 <= I
47407 < D
F > 94371
-
E <= 14835
43432 <= 83103
98835 < I
D >= J
56468 < F
G <= C
89458 < 86582
14785 > B
A < D
B > 59850
-
87748 >= D
G > 32551
42645 <= J
14115 >= 8653
J > E
53304 <= D
43092 <= 42727
59485 >= A
25213 < 62716
J >= A
-
9035 > 33060
81511 = B
18529 >= H
2213 <= E
E < 53194
33232 <= D
25259 < 75083
E >= E
C < C
34696 < G
-
19154 = 68564
D = D
61701 <= B
70462 >= 40501
E >= A
914 < C
22089 > J
88840 > 64178
25175 > 35407
41806 < 2189
-
H > 70717
52257 >= 47225
71173 > D
85516 = 19071
I >= H
D <= 9516
29852 = B
89458 >= J
C <= A
A = 47316
-
39524 >= F
74560 = B
A > 68521
E < F
49611 = 96522
77631 = I
99516 < A
87976 > 4693
I > A
E = 64475
-
D >= 292
H > 57234
A >= 18262
H = 31676
J <= 52480
G >= 17361
G = 45936
17527 >= H
69542 = J
77045 >= E
-
13117 <= C
E > 40191
G < 92050
99227 > C
A < D
24128 > 61937
C <= C
C >= 71393
26525 = C
B < 84814
-
G = D
A = 32966
2988 < B
D > 11802
E <= 49910
48706 <= 55052
H < J
F < 20674
79049 < 48637
13540 = 99224
-
J < A
A > D
91083 > G
49112 > H
H <= G
H < H
H <= B
D >= 37583
23542 < D
E >= 69635
-
A <= 71379
C < B
G > C
69719 < E
B > 96512
G >= F
C >= 2113
F > F
C = 89786
73348 < J
-
E = 57084
C = 93439
B <= 48200
I <= 67829
65301 < I
92639 > H
67009 = 84240
10232 > 95016
J >= E
H >= 16428
-
53487 >= C
I <= I
B < 47302
H > H
90504 > 16934
E <= D
B <= I
H = E
15183 <= G
C = 27094
-
18186 > D
68195 <= H
30000 <= 41768
B < B
A < D
I > B
31489 > 36969
H = D
91007 >= 1714
B <= 26740
-
F <= A
57285 <= 88930
I >= B
68820 < B
58046 > D
25458 <= B
6000 >= J
F < 34431
46947 < E
G > F
-
H > A
70945 = 3055
29225 >= 56114
G = H
A > 88547
J >= 78417
F < H
J = D
37830 > D
C > 75430
-
D = H
9957 <= 54232
68062 = I
B <= 44264
45758 >= F
A >= J
C >= H
73596 > H
C = 22863
B < D
-
27169 < E
G < B
D > 58853
50327 < B
C < 66507
58511 = 46801
C > 57770
G > H
89301 < 58476
F <= D
-
F <= 52751
F >= 49088
B = A
C < 75199
G > A
A <= I
E >= 74068
H >= 55443
8298 > 88611
C > 45043
-
G <= I
H > B
D > 63605
65009 = 88859
68031 < 67583
J >= 28063
293 >= H
H <= 87254
70140 < 91730
85812 = 48699
-
A >= 13510
6646 > D
I > 57277
A > 14805
26248 >= 7775
B > F
15227 < 24558
H > 5564
58114 < 79149
5902 < 92069
-
C > 5830
C <= 61788
F >= G
G >= I
B = 27611
E = D
C >= D
G >= 88947
H < 14962
96958 <= F
-
24041 > 19596
76723 > 15881
A = A
82745 >= 13293
F >= C
47520 > 96209
93135 > 5252
E <= 2271
8071 = D
56122 <= F
-
89854 < 78381
51502 >= E
B >= J
E = B
I <= 54853
64483 = J
B < I
B >= 29324
47804 >= A
71770 <= E
-
F <= I
84764 >= E
B <= 98958
66953 <= D
A <= F
92257 > B
75936 > 22830
A > 80423
A <= I
2752 = 58181
-
I > 74982
F <= 31398
60189 > D
C > C
81305 < D
B >= H
73736 < 84398
B = 44977
4781 <= C
E <= B
-Code: Select all
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
OK
A 60505 99999
B 84581 99999
C 79337 79337
D 60505 99999
E 60505 99999
F 60505 99999
H 1 22503
I 1 74728
J 86426 86426
OK
A 23487 68808
C 1 82365
D 14444 99999
I 1 99999
J 1 99999
OK
A 22779 99999
B 61415 61415
D 61415 61415
E 1 19008
F 72413 99341
G 1 35049
H 72413 99341
I 22779 99999
No solution
No solution
No solution
No solution
No solution
No solution
OK
B 74340 98383
C 9727 59545
D 77157 99999
E 1 70303
F 59595 59595
G 59595 59595
H 1 99999
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
OK
A 28557 99999
B 41774 99999
D 1 27815
E 51316 99999
F 1 53206
H 1 1311
I 1311 1311
J 90865 99999
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
OK
A 1 15340
B 1 15340
D 1 15340
E 1 15340
F 1 15340
G 1 99999
H 1 15340
I 22360 99999
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
No solution
OK
A 1 99999
B 68821 99999
D 1 58045
E 46948 99999
F 1 34430
G 2 99999
I 68821 99999
J 1 6000
No solution
OK
A 1 99999
B 1 22862
C 22863 22863
D 2 22863
F 1 45758
H 2 22863
I 68062 68062
J 1 99999
No solution
No solution
No solution
OK
A 14806 99999
B 2 99999
D 1 6645
F 1 99998
H 5565 99999
I 57278 99999
OK
B 27611 27611
C 5831 61788
D 1 61788
E 1 61788
F 96958 99999
G 88947 99999
H 1 14961
I 1 99999
No solution
No solution
No solution
No solutionCheck input and AC output for thousands of problems on uDebug!