Page 1 of 3
11228 - Transportation system.
Posted: Tue Jun 12, 2007 9:36 am
by asif_rahman0
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
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
Posted: Tue Jun 12, 2007 10:22 am
by little joey
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
Posted: Tue Jun 12, 2007 12:01 pm
by asif_rahman0
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
Posted: Wed Jun 13, 2007 11:28 am
by ayeshapakhi
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..
Posted: Wed Jun 13, 2007 1:01 pm
by stubbscroll
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..
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.
Posted: Wed Jun 13, 2007 4:02 pm
by little joey
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.
Posted: Thu Jun 14, 2007 8:52 am
by boyjava
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...
Posted: Thu Jun 14, 2007 9:25 am
by ayeshapakhi
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.
Posted: Thu Jun 14, 2007 11:57 am
by little joey
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.
Posted: Thu Jun 14, 2007 12:44 pm
by Darko
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.
Posted: Sun Jun 17, 2007 12:18 pm
by Adrian Kuegel
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.
Posted: Mon Jun 18, 2007 9:48 am
by ayeshapakhi
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
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..
very little
Thanks to all..
Posted: Mon Jun 18, 2007 10:05 am
by rio
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
Posted: Thu Jul 05, 2007 5:25 pm
by Kallol
how the Prims algo can be implemented in O(n) ??
Do you use Fibonacci Heap ?? Please let me know the trick ..
Thank you
Posted: Sat Jul 07, 2007 7:16 am
by rio
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