11228 - Transportation system.

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

11228 - Transportation system.

Post by asif_rahman0 » Tue Jun 12, 2007 9:36 am

Would someone check my I/O?
Input:

Code: Select all

20
41 131
38 72
69 80
68 65
22 96
67 49
61 51
87 63
24 66
83 80
60 71
52 64
60 90
31 49
99 23
11 94
24 25
15 51
39 13
97 67
76 19
33 12
18 99
35 92
0 74
71 95
33 39
32 39
45 37
71 57
5 95
24 71
8 86
54 51
24 74
70 75
63 33
99 29
94 58
13 52
99 35
57 46


71 189
3 17
48 94
18 77
11 83
25 83
62 59
78 2
7 86
65 94
32 80
84 39
65 60
61 72
84 58
72 8
19 12
49 47
59 49
52 71
22 34
20 21
33 92
39 80
9 74
97 28
93 100
25 29
66 4
81 79
21 98
62 91
4 82
100 59
1 34
80 51
69 92
39 77
97 38
34 51
19 35
1 22
9 67
31 90
11 82
84 51
70 78
42 74
88 100
80 53
62 57
51 32
63 48
46 92
61 4
98 31
52 69
20 88
41 68
79 48
98 97
44 56
3 73
100 63
87 87
79 41
83 64
1 63
72 21
9 24
51 75
53 25


77 123
30 52
93 96
89 32
89 70
71 55
40 79
64 10
30 80
62 19
98 67
8 42
57 32
22 27
38 1
52 89
43 74
2 8
82 65
67 20
43 22
95 22
48 16
6 25
86 75
3 96
43 85
93 69
61 4
81 53
84 43
15 20
22 34
26 35
33 28
19 67
19 79
8 45
51 13
86 0
18 68
82 47
16 3
0 80
39 18
5 22
65 26
21 70
66 92
14 65
46 6
21 46
80 32
86 35
67 6
42 29
14 71
55 77
1 3
38 14
82 71
65 41
5 12
3 77
22 67
40 59
48 81
63 63
45 25
78 32
26 83
18 96
45 99
31 56
45 30
80 47
7 1
18 81


1 187
71 15


22 39
18 44
60 31
93 16
17 13
97 44
51 98
42 46
47 22
97 72
52 24
59 55
100 25
5 28
76 14
41 32
61 97
20 32
2 0
41 8
77 52
22 35
78 98


92 32
82 29
28 33
5 16
21 9
26 13
59 39
10 69
4 42
80 13
42 34
44 100
70 32
32 15
83 8
23 10
8 73
7 53
10 21
14 52
28 82
33 24
59 94
17 4
53 73
31 85
74 100
12 74
38 72
14 34
53 22
30 0
3 95
79 52
36 41
25 81
67 24
95 48
7 44
77 96
48 90
45 92
93 78
38 95
4 71
79 83
89 64
76 0
34 81
1 66
58 13
40 4
24 5
6 17
13 65
76 13
20 3
36 8
60 12
42 37
87 53
65 10
25 42
41 47
71 33
94 69
12 24
11 92
3 71
91 82
20 90
44 95
60 76
95 34
40 49
4 89
27 45
34 9
59 82
20 2
22 68
10 29
23 1
47 19
76 16
49 47
94 90
18 10
69 55
26 14
77 59
8 73
72 21


1 83
51 76


94 43
98 24
77 71
9 59
49 12
72 38
55 22
61 35
48 16
21 41
74 67
4 92
85 7
92 34
96 39
26 42
1 1
64 4
96 33
23 62
76 67
47 26
73 32
30 82
61 14
92 21
4 40
38 2
64 76
14 8
49 3
31 71
86 38
17 98
98 15
55 32
46 69
3 61
67 44
44 50
0 76
23 45
11 25
99 82
39 11
40 50
52 21
60 17
90 44
6 44
38 16
41 3
56 43
24 26
9 0
36 90
13 50
88 42
66 87
28 32
94 73
11 52
47 35
87 9
57 37
56 15
95 38
43 6
30 23
39 84
69 88
34 5
93 81
2 86
10 77
30 28
68 97
12 14
1 88
35 100
30 73
43 2
41 11
82 58
84 6
16 71
67 18
100 41
78 92
7 57
69 35
76 56
93 13
26 26
21 38


96 57
2 88
17 60
95 54
2 26
21 0
11 87
36 96
88 83
24 31
62 24
88 14
39 84
17 22
96 84
78 1
53 91
35 9
87 75
33 100
42 80
20 7
65 50
92 81
45 14
34 96
20 6
51 86
19 4
91 70
0 13
70 42
15 43
14 47
72 96
91 41
72 11
92 7
16 12
13 51
40 86
43 50
26 55
1 7
18 70
99 71
55 49
78 94
59 40
96 20
6 34
85 28
70 42
63 62
34 32
80 97
47 49
73 50
63 85
29 20
19 0
84 91
55 58
4 33
55 68
38 12
9 49
99 13
35 4
5 26
29 42
20 98
77 95
63 36
42 41
81 45
53 40
5 60
9 55
34 13
52 6
35 28
29 33
67 21
61 57
41 21
54 95
19 50
75 81
73 67
47 77
83 40
28 16
13 3
87 15
22 30
49 39


42 31
100 83
67 7
30 27
47 62
4 76
13 19
78 25
4 55
48 21
59 42
47 59
47 26
67 92
2 49
67 27
44 76
23 44
83 69
64 100
95 44
46 63
77 17
16 81
80 77
10 78
42 26
5 19
62 58
59 42
77 85
87 4
70 89
3 38
10 35
87 8
67 42
2 37
55 58
56 2
94 6
46 71
35 45


35 182
73 76
15 15
0 7
14 73
91 51
58 5
27 52
32 78
98 68
39 13
85 71
40 40
17 36
80 28
76 79
90 53
73 26
71 7
25 61
46 3
71 97
76 64
22 21
97 25
7 27
92 70
2 99
75 42
66 56
61 71
86 10
52 79
81 46
5 5
98 76


81 38
66 55
15 91
92 62
13 69
91 79
98 15
96 88
33 86
89 34
89 22
10 36
10 68
39 56
84 100
76 55
15 26
0 76
79 0
31 35
91 64
74 88
34 8
19 28
93 70
19 4
40 41
7 42
51 66
76 55
70 16
56 3
95 64
93 64
97 52
72 21
47 82
2 57
7 57
54 96
8 66
72 67
53 90
73 43
95 53
49 77
41 87
15 86
17 55
50 72
68 54
72 13
63 2
53 41
82 0
4 98
30 0
3 29
20 64
37 98
22 82
11 83
60 28
44 22
74 61
6 78
51 62
14 35
38 92
18 18
91 96
14 14
98 39
2 82
63 79
91 80
71 16
40 82
75 12
67 94
98 38
20 50


65 101
61 55
40 26
96 15
68 22
36 26
44 15
31 61
4 70
0 23
49 3
94 48
6 54
36 96
63 42
76 28
25 15
58 28
84 52
69 13
19 20
63 30
25 66
14 31
35 77
32 5
78 1
43 97
58 2
73 11
78 56
91 99
0 40
4 10
18 100
85 14
76 20
56 66
57 62
79 35
61 43
60 32
37 41
63 32
76 13
76 98
41 88
45 16
55 29
50 32
31 96
92 58
71 43
55 4
22 3
54 7
2 91
84 100
32 18
64 73
78 45
86 22
46 58
19 28
60 6
15 80


65 48
86 65
94 73
85 4
67 90
17 95
49 44
27 16
15 58
83 97
41 78
7 91
20 13
85 18
55 56
87 87
77 31
63 47
18 55
35 81
14 0
46 5
94 34
11 7
74 97
34 37
65 7
62 45
83 69
85 38
96 39
89 100
86 44
26 28
18 24
78 23
10 45
24 4
95 69
66 43
32 52
93 79
11 68
74 63
32 11
40 33
5 68
14 81
82 34
78 96
84 23
55 65
20 85
35 16
86 16
90 66
18 1
92 83
95 36
67 34
17 94
88 84
11 54
38 82
98 35
70 89


54 68
0 11
31 66
69 21
56 79
89 5
28 0
11 95
61 40
5 8
34 40
67 96
66 60
15 39
74 59
55 41
51 69
4 56
21 91
2 93
8 21
12 21
61 64
80 38
9 54
32 95
88 57
65 66
21 25
13 64
56 90
45 37
57 64
51 64
62 55
30 54
2 27
1 73
97 0
24 29
55 87
59 14
2 49
69 60
15 49
95 9
12 35
45 70
31 73
93 59
4 1
92 83
38 43
24 66
18 6


52 45
28 50
79 36
82 63
15 36
85 81
87 2
32 63
60 13
42 76
6 11
92 51
76 3
48 62
29 78
78 72
49 40
69 49
9 43
5 98
57 91
25 44
45 15
96 18
11 4
64 57
51 17
70 97
72 82
47 67
34 89
30 1
2 52
35 92
51 21
64 37
77 41
58 83
50 34
20 64
55 79
36 91
9 7
10 56
86 47
6 35
22 92
66 25
26 24
10 20
12 70
21 21
78 100


61 4
60 47
72 84
5 19
59 44
90 38
75 60
57 24
70 44
88 26
69 73
63 31
66 25
56 47
37 27
49 2
45 59
18 72
94 91
81 4
57 88
82 69
62 64
28 72
93 8
63 4
0 69
62 28
55 0
99 58
4 35
100 65
57 95
77 42
35 96
45 21
57 70
98 61
18 83
59 76
33 2
79 38
16 51
60 62
46 17
96 77
67 16
12 96
73 29
85 94
58 7
23 95
58 56
78 48
69 22
39 57
75 79
44 86
76 12
53 3
66 66
68 82


32 11
56 84
29 18
57 34
36 31
27 55
68 46
84 7
44 35
78 15
16 93
24 91
3 43
43 48
10 70
78 63
98 51
79 100
75 20
78 16
29 57
88 89
58 87
62 76
42 11
30 45
13 49
91 26
74 76
63 98
76 88
52 60
86 28


93 48
84 85
25 5
70 43
25 29
78 61
80 5
65 9
39 7
91 44
60 42
54 38
31 19
87 94
46 68
52 57
16 91
90 95
32 73
1 4
17 92
67 68
33 49
5 3
80 1
31 75
53 40
2 58
31 63
80 87
50 11
74 1
52 31
70 53
85 1
99 6
35 15
49 28
97 75
25 33
44 74
47 18
47 29
56 44
31 69
7 79
23 46
76 95
38 47
97 37
79 79
60 47
5 75
48 23
70 97
2 67
57 83
90 58
13 74
89 77
77 2
21 76
93 100
64 82
94 34
88 31
77 91
47 32
18 38
70 81
20 0
37 41
17 37
43 77
79 99
34 4
74 66
1 4
38 59
34 34
24 0
76 9
95 56
43 51
51 55
10 65
12 73
66 17
97 54
57 52
65 84
38 89
28 55
98 77


10 6
33 93
99 58
19 36
59 77
35 50
85 83
3 87
63 3
31 16
2 17
Output:

Code: Select all

Case #1: 1 413 0
Case #2: 1 534 0
Case #3: 1 576 0
Case #4: 1 0 0
Case #5: 1 331 0
Case #6: 1 599 0
Case #7: 1 0 0
Case #8: 1 622 0
Case #9: 1 658 0
Case #10: 1 411 0
Case #11: 1 426 0
Case #12: 1 612 0
Case #13: 1 567 0
Case #14: 1 482 0
Case #15: 1 503 0
Case #16: 1 516 0
Case #17: 48 46 488
Case #18: 21 73 306
Case #19: 1 594 0
Case #20: 10 0 253
regards
Rabbi

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jun 12, 2007 10:22 am

Nope.

Code: Select all

Case #1: 1 424 0
Case #2: 1 550 0
Case #3: 1 597 0
Case #4: 1 0 0
Case #5: 1 338 0
Case #6: 1 628 0
Case #7: 1 0 0
Case #8: 1 649 0
Case #9: 1 686 0
Case #10: 1 422 0
Case #11: 1 438 0
Case #12: 1 637 0
Case #13: 1 588 0
Case #14: 1 501 0
Case #15: 1 518 0
Case #16: 1 535 0
Case #17: 55 20 533
Case #18: 22 65 325
Case #19: 1 623 0
Case #20: 10 0 257
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Tue Jun 12, 2007 12:01 pm

Thanks little joey. :)
Got accepted!
Though my output is different from you.

Code: Select all

Case #1: 1 425 0
Case #2: 1 551 0
Case #3: 1 598 0
Case #4: 1 0 0
Case #5: 1 338 0
Case #6: 1 628 0
Case #7: 1 0 0
Case #8: 1 650 0
Case #9: 1 686 0
Case #10: 1 423 0
Case #11: 1 438 0
Case #12: 1 637 0
Case #13: 1 588 0
Case #14: 1 501 0
Case #15: 1 519 0
Case #16: 1 535 0
Case #17: 55 20 533
Case #18: 22 65 325
Case #19: 1 625 0
Case #20: 10 0 257

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Wed Jun 13, 2007 11:28 am

I'm having WA in this prob..
confused about a point.. why do Little Joey's and asif_rahman0's outputs differ??

please explain this.. :roll:

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Wed Jun 13, 2007 1:01 pm

ayeshapakhi wrote:I'm having WA in this prob..
confused about a point.. why do Little Joey's and asif_rahman0's outputs differ??

please explain this.. :roll:
Since both people get AC, it could mean that the judge input is weak. Ideally, two different solutions should not both get AC, although it seems to happen a lot. It's incredibly hard to create input that's good enough to catch every wrong solution. For the record, I get the same output as Little Joey.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Jun 13, 2007 4:02 pm

When reading the problem during the contest, it struck me (and slightly irritated me), that the phrase "the minimum extension (rounded to the nearest integer)" can have two meanings:
1. calculate the distances, sum them up and then round the total to the nearest integer;
2. calculate the distances, round them to the nearest integer and then sum them up.

Although the first interpretation looks the most appropriate to me (and is the one I used), I think the problem setter should have made more clear what he exactly meant. I don't know it, but maybe ayeshapakhi used the second interpretation, which would explain the differences (which are sometimes more than 1!).
I think that purely based on the grammar of the English language only interpretation 1 is correct, but a perfect problem setter should appreciate the fact that his problems should be also solvable by people with a less then perfect conduct of the English language.

To explain why both solutions get accepted, we might imagine a problem setter who seeks to stay out of trouble by designing his cases such that all shortest connections between cities are orthogonal (either same x or same y), in which case both interpretations lead to the same answer.

Pure speculation, but it might be like that.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

boyjava
New poster
Posts: 6
Joined: Mon Oct 06, 2003 7:29 pm

Post by boyjava » Thu Jun 14, 2007 8:52 am

Sorry to disappoint, but I'm not the perfect problem setter. In fact, there are a number of great problem setters in this online judge, none of them is perfect, I think.

We actually tried to make the problem descriptions as easy to interpret as possible, specially given the fact that English is not our native language either.

You are correct, the first interpretation is the one I expected for this problem. And not to stay out of trouble but actually to avoid contestants irritated with precision errors, I made sure that if the second interpretation of the mentioned phrase was used, the difference would be small enough to not fail the program. And just to dismiss your suspicions, the shortest connections between cities are not all orthogonal.

As stubbscroll wisely said, "it's incredibly hard to create input that's good enough to catch every wrong solution". And if even someone with 2020 problems solved (out of 2040 - almost perfect) had to try more than 10 times to get the problem accepted, maybe the input cases are not that weak... :wink: :)

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Thu Jun 14, 2007 9:25 am

Thanks to all for the explanation....

I didn't missinterprete the rounding specification..
my problem is in finding the number of states. However, i'll fix it.

Edit: got it accepted... but it took huge time... i wonder how rio and other people got acc with such short time and using a little memory!!


Thanks again.
Last edited by ayeshapakhi on Sun Jun 17, 2007 7:54 am, edited 2 times in total.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Jun 14, 2007 11:57 am

Glad you caught the undertone when I used the term 'perfect problem setter'. I made my blunders in that department too. And believe me, the 'slight irritation' was the only negative feeling about the whole problem set, which was very good in my opinion. It's a good thing that you made sure that both interpretations would lead to an accepted solution, but I still believe that resolving the ambiguity in the problem statement is better than resolving it in the test data. In general.

Also glad you mentioned the fact that I spent more than 10 submissions to solve this problem and linked that to the fact that I solved so many problems from the UVA set. Sorry to say, but that had nothing to do with the strength of the test data, but was just a simple case of chasing the wrong bug in my code. Which again shows that solving many problems on UVA is more the result of slightly maniacal stubbornness, than of being perfect in any sense.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Jun 14, 2007 12:44 pm

I'd like to say that, overall, this was a nice set - well suited for the level of the competition (so I was able to solve some of the problems, too :)).

The only thing I didn't like was output inconsistency. I think the format should be the same for all the problems, but maybe that was a part of it, I don't know.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jun 17, 2007 12:18 pm

ayeshapakhi wrote: Edit: got it accepted... but it took huge time... i wonder how rio and other people got acc with such short time and using a little memory!!
You can use Prim's algorithm, which can be implemented in O(n^2) using O(n) memory for this problem.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Mon Jun 18, 2007 9:48 am

Adrian Kuegel wrote:

Code: Select all

You can use Prim's algorithm, which can be implemented in O(n^2) using O(n) memory for this problem.
hmm... i used kruskal's algo for this prob...
..but one thing.... i can't understand :oops:
if i use prim's algo... it needs a queue... of memory of size O(N*N)...
isn't it?? or it can be implemented more efficiently??

i'm sorry.. actually i know a little.. :oops:
very little :oops:

Thanks to all..

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Jun 18, 2007 10:05 am

if i use prim's algo... it needs a queue... of memory of size O(N*N)...
isn't it?? or it can be implemented more efficiently??
Yes. As Adrian wrote, it can be implemented with O(N) memory. And this memory is not for queue.
----
Rio

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Jul 05, 2007 5:25 pm

how the Prims algo can be implemented in O(n) ??
Do you use Fibonacci Heap ?? Please let me know the trick ..

Thank you :)
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Jul 07, 2007 7:16 am

Kallol wrote:how the Prims algo can be implemented in O(n) ??
Do you use Fibonacci Heap ?? Please let me know the trick ..
O(n) memory is not for Heap. Its for an array of coordinates and some other infos.
----
Rio

Post Reply

Return to “Volume 112 (11200-11299)”