10160 - Servicing Stations
Moderator: Board moderators
10160 - Servicing Stations
I got WA for this question, can anyone give me the output for these case or give me some other input/ouput:
12 51
12 10
7 12
2 8
1 12
9 12
11 3
11 7
4 12
3 4
2 3
5 3
2 5
10 1
7 2
1 6
6 5
6 8
4 11
8 7
3 7
11 2
11 9
3 10
9 5
8 9
8 10
4 10
7 6
5 8
1 5
4 7
4 6
4 5
2 10
2 4
6 11
11 12
12 8
8 3
11 10
10 5
7 9
9 6
2 6
7 5
1 2
4 8
3 9
10 7
6 3
1 8
25 251
24 25
22 17
19 20
9 23
25 10
9 17
5 15
1 12
20 16
4 15
12 11
11 23
15 10
21 24
15 20
10 13
23 22
4 3
25 21
18 14
22 5
11 14
15 18
11 15
4 8
15 23
13 1
4 13
7 16
18 24
25 6
6 12
17 4
19 22
2 20
16 21
7 1
9 19
10 1
16 17
24 5
12 22
24 17
20 13
15 7
6 21
23 24
19 21
16 19
21 14
25 23
3 20
23 13
8 15
7 6
2 19
11 19
3 25
21 23
9 12
7 13
6 11
12 8
14 9
20 7
3 17
24 6
12 3
5 7
5 21
25 9
13 16
18 25
15 12
2 5
2 17
4 20
4 7
7 17
13 24
21 2
17 10
8 7
10 18
17 12
14 7
25 4
7 25
2 24
9 21
10 6
21 11
11 9
18 12
19 3
9 20
15 2
25 11
22 21
14 19
8 10
8 17
20 10
2 1
6 8
18 17
6 3
22 3
6 5
18 3
18 9
24 19
23 12
19 17
20 18
10 24
22 24
3 7
17 23
18 23
2 3
17 11
22 6
24 11
22 16
6 15
5 9
6 23
5 16
4 1
19 15
21 10
11 7
6 13
9 15
11 5
4 24
16 6
11 1
14 20
5 13
17 15
19 6
4 9
10 14
1 17
5 12
8 21
16 15
18 4
16 25
15 21
19 18
11 3
2 11
19 12
23 19
5 19
6 17
20 1
18 22
14 25
1 25
9 24
17 14
12 24
10 22
8 22
10 9
25 12
22 13
20 6
23 20
13 8
3 16
22 1
14 5
15 14
2 22
18 2
4 2
13 18
2 16
3 15
11 8
2 10
17 25
8 5
4 22
23 4
20 21
16 8
23 10
22 25
12 14
25 15
22 11
1 19
13 3
11 10
1 6
8 14
5 23
10 12
24 8
6 14
18 21
13 12
22 20
15 22
2 6
3 8
16 18
14 13
2 8
11 16
13 11
3 21
16 10
23 3
7 24
3 24
16 12
23 16
25 19
13 19
1 18
2 23
20 24
7 12
13 15
24 1
25 13
15 24
14 24
14 1
2 14
19 4
4 10
21 7
7 2
21 4
8 18
11 18
25 20
17 20
18 7
4 11
8 19
13 2
16 24
18 55
9 14
17 7
14 6
12 7
3 7
11 3
7 15
4 15
14 2
5 6
13 9
14 4
12 2
16 4
3 6
13 8
5 10
7 5
16 13
4 11
10 17
9 11
9 6
10 11
1 5
11 6
6 18
10 3
6 12
18 15
4 17
9 7
4 3
7 14
16 17
5 3
13 6
1 10
2 3
6 4
12 4
12 9
14 10
13 17
11 14
1 12
16 3
16 6
2 9
18 13
13 2
6 17
16 9
15 12
17 5
27 308
5 22
9 24
16 19
25 24
23 2
10 16
5 15
22 19
27 21
9 19
6 15
16 11
3 15
15 19
27 14
9 23
13 12
19 25
5 23
14 6
2 13
21 20
10 13
1 4
23 27
10 15
15 1
6 25
17 23
25 10
8 18
26 22
20 7
11 19
26 7
25 3
23 13
26 18
27 25
18 10
5 4
19 4
14 19
24 16
25 23
5 21
12 10
15 27
12 5
4 10
4 20
17 16
18 15
15 25
24 3
13 15
26 6
17 12
25 8
4 8
6 8
5 11
23 3
21 4
20 1
16 7
8 3
20 19
8 15
26 14
12 11
13 18
24 11
14 5
17 27
14 3
26 16
8 19
20 3
4 18
7 18
7 4
16 13
21 16
22 16
5 16
4 3
24 5
1 16
24 18
6 1
1 2
15 20
19 7
15 2
5 25
27 8
27 12
9 21
26 10
26 17
16 23
21 7
17 14
26 5
23 10
13 19
10 5
1 18
22 20
2 11
6 17
13 11
4 15
7 17
14 2
1 12
20 24
1 9
23 1
23 19
1 10
23 11
24 22
17 18
18 19
20 18
22 13
25 1
27 18
18 2
4 9
18 21
12 24
17 21
25 9
24 4
14 23
7 8
4 25
19 27
24 6
16 27
11 6
7 22
12 25
21 12
16 14
22 14
22 6
14 21
5 20
20 6
18 5
12 20
2 10
11 8
16 6
26 27
16 25
19 2
22 8
16 18
3 13
2 7
5 1
1 19
11 3
3 10
12 9
24 17
9 11
11 14
26 15
26 13
8 5
17 9
3 21
13 7
26 21
17 1
13 14
1 3
7 9
3 16
14 25
13 4
19 3
9 14
7 23
5 3
27 5
21 10
12 16
20 14
26 23
11 7
4 23
21 8
11 25
13 21
17 2
15 23
2 20
17 20
18 3
15 9
22 25
19 26
19 17
12 18
12 2
3 22
10 19
22 21
21 25
5 7
19 12
19 6
11 21
2 3
25 26
24 14
2 26
10 11
13 20
10 17
13 25
8 17
15 12
7 25
25 18
4 14
14 7
6 9
1 7
6 10
27 11
8 23
6 2
24 2
2 22
27 9
3 26
15 16
3 12
9 5
16 9
24 1
26 12
9 3
1 11
12 22
20 11
10 27
22 18
13 6
15 22
13 17
7 24
27 7
26 24
7 15
24 8
12 6
6 21
19 21
19 5
23 12
25 20
9 13
15 21
6 5
4 26
5 2
10 9
27 6
8 10
25 2
9 2
9 18
7 6
4 6
10 20
24 15
2 8
22 9
19 24
16 8
13 1
11 17
1 21
18 11
17 25
23 6
16 20
11 26
5 13
27 2
11 22
27 20
16 2
22 27
24 23
10 22
26 20
14 10
12 8
4 5
2 4
1 4
3 2
3 1
4 3
23 100
7 12
18 12
1 2
22 3
9 19
21 8
16 6
5 19
10 3
14 4
9 7
11 12
3 21
23 16
8 12
2 6
2 16
6 11
2 22
15 22
3 4
1 16
21 2
14 18
5 9
11 2
19 3
3 23
8 14
23 19
4 17
13 14
23 9
4 9
4 15
12 14
20 10
5 13
22 6
8 17
19 12
4 11
20 9
1 11
15 17
22 7
17 2
23 18
14 5
10 21
4 6
15 21
7 10
11 19
19 7
12 15
2 10
13 23
11 5
17 6
13 3
20 16
17 19
22 17
8 6
5 12
18 5
2 20
19 8
9 8
23 2
14 3
16 5
13 7
5 20
13 18
4 20
22 18
9 1
18 16
8 23
13 19
17 23
7 18
18 17
16 7
19 16
16 9
4 8
18 2
10 8
18 11
14 15
7 1
6 13
14 10
10 19
8 22
17 11
4 22
28 260
18 14
13 11
9 5
5 19
15 6
8 9
14 2
14 13
5 23
28 25
17 14
18 27
11 2
16 20
25 16
23 2
28 22
13 2
27 13
8 27
20 12
18 24
22 5
22 25
3 13
12 26
7 26
7 19
10 26
27 25
22 13
4 3
22 6
17 7
13 23
8 14
12 13
10 15
15 18
26 16
21 16
3 18
15 8
8 11
7 21
21 26
22 3
16 15
18 6
24 20
19 15
26 27
22 4
25 10
12 24
7 2
19 16
3 7
24 7
7 28
6 8
2 24
3 12
16 8
23 10
18 25
3 2
5 25
12 6
6 24
28 10
14 24
24 13
12 10
9 23
17 8
27 7
15 3
13 7
26 18
21 25
22 7
3 14
15 22
12 19
8 18
4 16
7 6
19 4
7 15
25 8
22 26
17 27
22 1
21 28
20 22
12 17
10 17
15 12
4 21
6 5
18 20
19 3
9 2
21 2
6 13
20 11
4 9
20 1
14 27
9 10
18 9
4 23
8 1
22 12
2 27
5 1
13 19
10 27
22 8
25 6
28 27
11 19
8 13
3 27
16 12
9 12
6 14
9 22
5 21
13 4
8 7
27 9
26 4
14 15
25 1
3 8
11 17
7 25
1 2
23 6
14 10
23 14
28 23
24 22
24 26
11 24
5 11
17 15
28 6
28 16
10 2
22 11
20 5
4 8
2 18
1 13
23 12
25 12
17 5
13 21
23 22
3 5
4 27
25 2
27 23
27 12
1 4
17 20
19 23
1 19
14 22
25 23
15 28
4 28
11 21
2 6
5 15
11 26
14 9
16 5
21 17
21 10
13 10
24 5
16 17
16 11
13 15
14 19
10 18
19 8
21 27
7 14
24 21
10 19
20 23
28 20
18 5
22 17
11 23
19 27
16 9
9 25
6 9
24 16
11 6
10 5
22 27
15 9
20 14
2 22
26 8
4 7
23 18
10 24
24 28
10 22
24 25
18 17
4 25
16 14
18 19
2 28
20 21
9 26
24 17
19 26
3 16
10 16
3 6
14 21
11 7
9 21
18 21
4 12
11 12
17 25
14 26
14 28
20 7
25 3
18 13
19 21
8 5
9 7
6 16
26 2
8 12
11 15
26 28
1 6
11 10
2 19
14 1
8 28
27 16
12 28
19 20
18 12
19 24
23 33
23 13
14 13
6 22
21 17
8 18
17 8
13 22
7 2
21 10
9 23
15 8
18 11
3 17
2 6
13 17
15 20
20 18
6 9
16 12
21 15
3 10
6 10
7 19
15 5
7 10
17 9
22 7
20 14
17 16
1 13
6 19
13 11
16 13
14 74
5 3
2 5
9 6
11 10
10 6
13 7
13 5
12 13
8 3
6 7
12 5
10 4
7 2
2 8
4 11
2 10
9 11
3 4
14 1
8 9
2 4
9 13
10 13
3 11
6 3
7 10
6 13
14 10
14 5
5 7
11 13
8 13
2 1
14 7
13 14
2 9
3 12
8 10
10 12
10 3
12 4
6 1
9 14
11 14
12 7
1 5
14 2
1 8
11 8
11 7
2 13
9 3
2 6
4 6
10 5
11 2
8 12
6 5
3 13
10 1
5 4
1 13
5 9
8 14
11 1
4 13
6 11
4 1
7 3
1 9
9 10
11 12
12 2
12 6
23 207
11 10
19 12
13 12
23 15
18 7
7 19
22 23
6 10
17 23
16 10
18 17
15 17
3 9
9 11
20 6
4 17
14 22
18 2
20 18
5 13
5 17
20 15
22 16
5 7
13 22
8 14
4 11
6 12
5 15
4 23
18 6
13 20
15 3
18 21
11 12
22 17
2 4
20 11
12 22
4 6
20 23
21 12
6 5
12 1
11 22
5 11
7 10
20 22
7 13
1 14
12 7
13 3
8 22
3 21
21 16
5 2
4 22
14 19
19 18
3 10
12 10
19 4
7 4
6 19
16 2
9 10
20 17
15 2
5 23
23 10
5 12
17 16
19 13
22 10
15 4
3 11
12 3
7 21
7 8
18 10
2 10
5 8
3 8
12 15
7 15
23 21
11 2
9 19
17 14
4 13
5 16
23 13
17 11
1 3
10 15
20 16
16 7
3 17
16 12
12 23
15 19
3 6
21 20
20 2
23 14
21 8
2 21
11 21
13 6
23 1
7 22
7 14
15 9
21 22
19 11
8 10
7 6
19 22
9 6
10 13
19 10
20 3
20 8
21 19
6 21
2 23
16 13
9 8
13 21
17 13
6 23
1 18
22 2
23 8
8 16
20 10
5 4
5 14
2 17
18 14
15 8
7 3
3 18
13 14
18 8
17 6
4 12
16 23
8 1
2 9
20 14
23 3
15 13
9 22
1 6
2 14
3 19
18 15
14 16
20 9
11 18
7 2
7 9
18 13
15 21
16 3
16 18
11 8
1 11
6 16
17 19
7 20
2 1
10 4
12 14
8 2
20 19
11 7
6 8
4 18
18 12
10 5
18 5
1 16
3 4
8 19
17 7
15 22
19 2
4 8
1 19
9 18
10 21
14 3
1 10
5 21
5 9
8 13
12 8
3 2
2 6
2 12
12 20
9 14
20 4
2 13
17 8
17 33
14 15
4 8
11 6
16 4
6 10
17 13
10 13
15 5
7 6
13 8
1 12
7 17
11 13
16 5
16 11
5 12
12 13
8 5
8 6
13 3
7 14
4 2
14 10
17 14
1 4
11 12
10 17
13 5
17 12
11 8
15 13
4 11
13 16
32 132
18 27
20 25
19 9
1 13
8 30
16 24
22 8
3 27
30 25
17 18
17 20
8 26
9 12
6 31
5 10
6 28
3 22
2 21
2 25
27 10
31 21
29 10
23 30
22 19
29 7
2 30
28 25
15 23
9 4
1 23
7 24
14 28
20 10
20 23
28 21
12 2
4 14
29 3
30 21
12 26
28 7
28 29
15 32
21 17
2 29
16 15
19 15
14 27
29 20
6 26
24 6
1 8
7 15
29 19
18 15
9 24
8 29
12 10
23 4
11 4
11 1
4 2
18 9
5 8
25 29
30 27
10 19
16 19
9 15
16 28
20 31
30 29
30 24
5 13
23 7
19 25
27 31
31 29
27 16
18 21
10 16
7 2
14 30
9 8
18 31
17 22
17 13
30 32
14 22
25 18
7 9
17 10
4 17
31 32
6 1
13 20
27 25
26 10
22 6
11 18
21 13
6 19
12 8
10 18
20 8
2 6
27 6
28 9
17 24
16 25
30 15
22 26
3 31
30 3
21 26
23 3
4 12
22 25
23 22
23 14
17 7
7 11
19 24
20 14
29 4
24 12
28 27
19 18
17 3
2 18
22 28
15 10
27 91
6 25
9 3
9 15
9 5
8 24
27 24
12 20
11 17
15 10
3 22
10 26
11 24
2 10
27 7
5 15
26 19
22 5
2 24
19 4
24 4
6 15
21 13
13 27
5 10
19 20
2 21
9 2
19 3
26 15
18 3
14 3
6 14
18 17
15 13
5 14
14 9
10 27
5 2
25 4
9 1
4 17
20 25
26 3
18 10
19 11
6 13
23 19
26 20
10 11
16 7
18 22
17 13
21 15
26 13
9 21
9 4
22 4
8 13
2 6
4 15
3 10
12 11
13 10
22 20
9 25
4 7
7 26
3 23
27 23
26 5
16 5
26 11
25 27
17 24
6 18
9 19
2 1
13 23
13 22
20 3
27 16
26 27
2 8
11 18
1 22
20 10
17 19
2 16
4 16
27 3
14 17
19 28
10 7
6 11
19 9
12 14
13 2
3 14
7 2
15 4
16 14
7 14
6 15
7 9
3 18
12 19
6 16
10 17
6 13
3 2
8 15
9 14
13 17
11 5
10 3
8 12
7 4
5 14
16 18
19 2
25 35
25 2
16 5
23 13
13 9
3 15
12 24
2 16
8 21
5 22
19 22
18 1
5 8
3 13
15 7
22 11
19 18
4 14
24 5
24 6
17 2
22 12
14 25
13 17
13 6
21 17
19 3
16 21
12 14
19 10
6 17
5 20
9 16
17 8
15 12
8 10
18 32
7 13
4 18
16 9
17 2
6 2
2 13
14 3
9 8
1 17
18 10
6 17
4 7
14 18
15 14
9 5
1 15
15 11
3 9
15 17
4 15
18 3
3 5
16 5
16 4
3 2
5 7
10 14
12 2
12 6
13 4
9 17
5 1
3 2
2 3
1 2
0 0
32 59
6 9
29 25
24 31
32 3
5 22
14 11
30 26
22 31
12 21
30 4
27 14
17 8
8 19
27 11
8 3
30 2
20 17
20 16
16 9
5 4
24 15
31 28
19 30
4 16
10 21
31 6
14 30
20 24
9 24
26 18
25 14
24 28
16 2
27 3
12 5
15 22
32 22
2 17
31 3
23 9
24 23
13 7
27 29
23 19
27 10
5 3
23 1
31 21
9 27
26 14
28 25
30 16
17 28
30 31
5 6
15 21
28 26
18 30
21 30
21 99
19 20
13 17
9 19
17 3
6 9
13 10
12 2
21 20
11 18
18 2
21 10
18 14
4 6
3 6
20 13
13 11
17 21
9 3
20 1
16 14
1 13
7 14
1 2
16 10
2 9
14 11
19 6
6 7
19 15
9 7
9 5
13 7
14 15
4 9
19 3
15 5
12 3
17 5
15 10
9 15
2 15
16 15
8 19
19 12
10 14
12 15
13 18
20 7
13 9
5 14
5 3
20 3
2 7
1 9
13 12
11 5
6 14
17 12
10 9
10 2
16 4
18 6
10 5
19 18
4 3
18 20
14 17
19 10
2 20
18 3
4 12
9 14
11 21
11 15
21 13
8 20
14 20
21 8
15 20
19 14
16 6
12 5
8 11
12 9
17 7
13 6
2 13
18 16
5 6
2 8
8 17
8 1
6 12
17 4
7 12
10 8
2 5
18 15
19 21
0 0
12 51
12 10
7 12
2 8
1 12
9 12
11 3
11 7
4 12
3 4
2 3
5 3
2 5
10 1
7 2
1 6
6 5
6 8
4 11
8 7
3 7
11 2
11 9
3 10
9 5
8 9
8 10
4 10
7 6
5 8
1 5
4 7
4 6
4 5
2 10
2 4
6 11
11 12
12 8
8 3
11 10
10 5
7 9
9 6
2 6
7 5
1 2
4 8
3 9
10 7
6 3
1 8
25 251
24 25
22 17
19 20
9 23
25 10
9 17
5 15
1 12
20 16
4 15
12 11
11 23
15 10
21 24
15 20
10 13
23 22
4 3
25 21
18 14
22 5
11 14
15 18
11 15
4 8
15 23
13 1
4 13
7 16
18 24
25 6
6 12
17 4
19 22
2 20
16 21
7 1
9 19
10 1
16 17
24 5
12 22
24 17
20 13
15 7
6 21
23 24
19 21
16 19
21 14
25 23
3 20
23 13
8 15
7 6
2 19
11 19
3 25
21 23
9 12
7 13
6 11
12 8
14 9
20 7
3 17
24 6
12 3
5 7
5 21
25 9
13 16
18 25
15 12
2 5
2 17
4 20
4 7
7 17
13 24
21 2
17 10
8 7
10 18
17 12
14 7
25 4
7 25
2 24
9 21
10 6
21 11
11 9
18 12
19 3
9 20
15 2
25 11
22 21
14 19
8 10
8 17
20 10
2 1
6 8
18 17
6 3
22 3
6 5
18 3
18 9
24 19
23 12
19 17
20 18
10 24
22 24
3 7
17 23
18 23
2 3
17 11
22 6
24 11
22 16
6 15
5 9
6 23
5 16
4 1
19 15
21 10
11 7
6 13
9 15
11 5
4 24
16 6
11 1
14 20
5 13
17 15
19 6
4 9
10 14
1 17
5 12
8 21
16 15
18 4
16 25
15 21
19 18
11 3
2 11
19 12
23 19
5 19
6 17
20 1
18 22
14 25
1 25
9 24
17 14
12 24
10 22
8 22
10 9
25 12
22 13
20 6
23 20
13 8
3 16
22 1
14 5
15 14
2 22
18 2
4 2
13 18
2 16
3 15
11 8
2 10
17 25
8 5
4 22
23 4
20 21
16 8
23 10
22 25
12 14
25 15
22 11
1 19
13 3
11 10
1 6
8 14
5 23
10 12
24 8
6 14
18 21
13 12
22 20
15 22
2 6
3 8
16 18
14 13
2 8
11 16
13 11
3 21
16 10
23 3
7 24
3 24
16 12
23 16
25 19
13 19
1 18
2 23
20 24
7 12
13 15
24 1
25 13
15 24
14 24
14 1
2 14
19 4
4 10
21 7
7 2
21 4
8 18
11 18
25 20
17 20
18 7
4 11
8 19
13 2
16 24
18 55
9 14
17 7
14 6
12 7
3 7
11 3
7 15
4 15
14 2
5 6
13 9
14 4
12 2
16 4
3 6
13 8
5 10
7 5
16 13
4 11
10 17
9 11
9 6
10 11
1 5
11 6
6 18
10 3
6 12
18 15
4 17
9 7
4 3
7 14
16 17
5 3
13 6
1 10
2 3
6 4
12 4
12 9
14 10
13 17
11 14
1 12
16 3
16 6
2 9
18 13
13 2
6 17
16 9
15 12
17 5
27 308
5 22
9 24
16 19
25 24
23 2
10 16
5 15
22 19
27 21
9 19
6 15
16 11
3 15
15 19
27 14
9 23
13 12
19 25
5 23
14 6
2 13
21 20
10 13
1 4
23 27
10 15
15 1
6 25
17 23
25 10
8 18
26 22
20 7
11 19
26 7
25 3
23 13
26 18
27 25
18 10
5 4
19 4
14 19
24 16
25 23
5 21
12 10
15 27
12 5
4 10
4 20
17 16
18 15
15 25
24 3
13 15
26 6
17 12
25 8
4 8
6 8
5 11
23 3
21 4
20 1
16 7
8 3
20 19
8 15
26 14
12 11
13 18
24 11
14 5
17 27
14 3
26 16
8 19
20 3
4 18
7 18
7 4
16 13
21 16
22 16
5 16
4 3
24 5
1 16
24 18
6 1
1 2
15 20
19 7
15 2
5 25
27 8
27 12
9 21
26 10
26 17
16 23
21 7
17 14
26 5
23 10
13 19
10 5
1 18
22 20
2 11
6 17
13 11
4 15
7 17
14 2
1 12
20 24
1 9
23 1
23 19
1 10
23 11
24 22
17 18
18 19
20 18
22 13
25 1
27 18
18 2
4 9
18 21
12 24
17 21
25 9
24 4
14 23
7 8
4 25
19 27
24 6
16 27
11 6
7 22
12 25
21 12
16 14
22 14
22 6
14 21
5 20
20 6
18 5
12 20
2 10
11 8
16 6
26 27
16 25
19 2
22 8
16 18
3 13
2 7
5 1
1 19
11 3
3 10
12 9
24 17
9 11
11 14
26 15
26 13
8 5
17 9
3 21
13 7
26 21
17 1
13 14
1 3
7 9
3 16
14 25
13 4
19 3
9 14
7 23
5 3
27 5
21 10
12 16
20 14
26 23
11 7
4 23
21 8
11 25
13 21
17 2
15 23
2 20
17 20
18 3
15 9
22 25
19 26
19 17
12 18
12 2
3 22
10 19
22 21
21 25
5 7
19 12
19 6
11 21
2 3
25 26
24 14
2 26
10 11
13 20
10 17
13 25
8 17
15 12
7 25
25 18
4 14
14 7
6 9
1 7
6 10
27 11
8 23
6 2
24 2
2 22
27 9
3 26
15 16
3 12
9 5
16 9
24 1
26 12
9 3
1 11
12 22
20 11
10 27
22 18
13 6
15 22
13 17
7 24
27 7
26 24
7 15
24 8
12 6
6 21
19 21
19 5
23 12
25 20
9 13
15 21
6 5
4 26
5 2
10 9
27 6
8 10
25 2
9 2
9 18
7 6
4 6
10 20
24 15
2 8
22 9
19 24
16 8
13 1
11 17
1 21
18 11
17 25
23 6
16 20
11 26
5 13
27 2
11 22
27 20
16 2
22 27
24 23
10 22
26 20
14 10
12 8
4 5
2 4
1 4
3 2
3 1
4 3
23 100
7 12
18 12
1 2
22 3
9 19
21 8
16 6
5 19
10 3
14 4
9 7
11 12
3 21
23 16
8 12
2 6
2 16
6 11
2 22
15 22
3 4
1 16
21 2
14 18
5 9
11 2
19 3
3 23
8 14
23 19
4 17
13 14
23 9
4 9
4 15
12 14
20 10
5 13
22 6
8 17
19 12
4 11
20 9
1 11
15 17
22 7
17 2
23 18
14 5
10 21
4 6
15 21
7 10
11 19
19 7
12 15
2 10
13 23
11 5
17 6
13 3
20 16
17 19
22 17
8 6
5 12
18 5
2 20
19 8
9 8
23 2
14 3
16 5
13 7
5 20
13 18
4 20
22 18
9 1
18 16
8 23
13 19
17 23
7 18
18 17
16 7
19 16
16 9
4 8
18 2
10 8
18 11
14 15
7 1
6 13
14 10
10 19
8 22
17 11
4 22
28 260
18 14
13 11
9 5
5 19
15 6
8 9
14 2
14 13
5 23
28 25
17 14
18 27
11 2
16 20
25 16
23 2
28 22
13 2
27 13
8 27
20 12
18 24
22 5
22 25
3 13
12 26
7 26
7 19
10 26
27 25
22 13
4 3
22 6
17 7
13 23
8 14
12 13
10 15
15 18
26 16
21 16
3 18
15 8
8 11
7 21
21 26
22 3
16 15
18 6
24 20
19 15
26 27
22 4
25 10
12 24
7 2
19 16
3 7
24 7
7 28
6 8
2 24
3 12
16 8
23 10
18 25
3 2
5 25
12 6
6 24
28 10
14 24
24 13
12 10
9 23
17 8
27 7
15 3
13 7
26 18
21 25
22 7
3 14
15 22
12 19
8 18
4 16
7 6
19 4
7 15
25 8
22 26
17 27
22 1
21 28
20 22
12 17
10 17
15 12
4 21
6 5
18 20
19 3
9 2
21 2
6 13
20 11
4 9
20 1
14 27
9 10
18 9
4 23
8 1
22 12
2 27
5 1
13 19
10 27
22 8
25 6
28 27
11 19
8 13
3 27
16 12
9 12
6 14
9 22
5 21
13 4
8 7
27 9
26 4
14 15
25 1
3 8
11 17
7 25
1 2
23 6
14 10
23 14
28 23
24 22
24 26
11 24
5 11
17 15
28 6
28 16
10 2
22 11
20 5
4 8
2 18
1 13
23 12
25 12
17 5
13 21
23 22
3 5
4 27
25 2
27 23
27 12
1 4
17 20
19 23
1 19
14 22
25 23
15 28
4 28
11 21
2 6
5 15
11 26
14 9
16 5
21 17
21 10
13 10
24 5
16 17
16 11
13 15
14 19
10 18
19 8
21 27
7 14
24 21
10 19
20 23
28 20
18 5
22 17
11 23
19 27
16 9
9 25
6 9
24 16
11 6
10 5
22 27
15 9
20 14
2 22
26 8
4 7
23 18
10 24
24 28
10 22
24 25
18 17
4 25
16 14
18 19
2 28
20 21
9 26
24 17
19 26
3 16
10 16
3 6
14 21
11 7
9 21
18 21
4 12
11 12
17 25
14 26
14 28
20 7
25 3
18 13
19 21
8 5
9 7
6 16
26 2
8 12
11 15
26 28
1 6
11 10
2 19
14 1
8 28
27 16
12 28
19 20
18 12
19 24
23 33
23 13
14 13
6 22
21 17
8 18
17 8
13 22
7 2
21 10
9 23
15 8
18 11
3 17
2 6
13 17
15 20
20 18
6 9
16 12
21 15
3 10
6 10
7 19
15 5
7 10
17 9
22 7
20 14
17 16
1 13
6 19
13 11
16 13
14 74
5 3
2 5
9 6
11 10
10 6
13 7
13 5
12 13
8 3
6 7
12 5
10 4
7 2
2 8
4 11
2 10
9 11
3 4
14 1
8 9
2 4
9 13
10 13
3 11
6 3
7 10
6 13
14 10
14 5
5 7
11 13
8 13
2 1
14 7
13 14
2 9
3 12
8 10
10 12
10 3
12 4
6 1
9 14
11 14
12 7
1 5
14 2
1 8
11 8
11 7
2 13
9 3
2 6
4 6
10 5
11 2
8 12
6 5
3 13
10 1
5 4
1 13
5 9
8 14
11 1
4 13
6 11
4 1
7 3
1 9
9 10
11 12
12 2
12 6
23 207
11 10
19 12
13 12
23 15
18 7
7 19
22 23
6 10
17 23
16 10
18 17
15 17
3 9
9 11
20 6
4 17
14 22
18 2
20 18
5 13
5 17
20 15
22 16
5 7
13 22
8 14
4 11
6 12
5 15
4 23
18 6
13 20
15 3
18 21
11 12
22 17
2 4
20 11
12 22
4 6
20 23
21 12
6 5
12 1
11 22
5 11
7 10
20 22
7 13
1 14
12 7
13 3
8 22
3 21
21 16
5 2
4 22
14 19
19 18
3 10
12 10
19 4
7 4
6 19
16 2
9 10
20 17
15 2
5 23
23 10
5 12
17 16
19 13
22 10
15 4
3 11
12 3
7 21
7 8
18 10
2 10
5 8
3 8
12 15
7 15
23 21
11 2
9 19
17 14
4 13
5 16
23 13
17 11
1 3
10 15
20 16
16 7
3 17
16 12
12 23
15 19
3 6
21 20
20 2
23 14
21 8
2 21
11 21
13 6
23 1
7 22
7 14
15 9
21 22
19 11
8 10
7 6
19 22
9 6
10 13
19 10
20 3
20 8
21 19
6 21
2 23
16 13
9 8
13 21
17 13
6 23
1 18
22 2
23 8
8 16
20 10
5 4
5 14
2 17
18 14
15 8
7 3
3 18
13 14
18 8
17 6
4 12
16 23
8 1
2 9
20 14
23 3
15 13
9 22
1 6
2 14
3 19
18 15
14 16
20 9
11 18
7 2
7 9
18 13
15 21
16 3
16 18
11 8
1 11
6 16
17 19
7 20
2 1
10 4
12 14
8 2
20 19
11 7
6 8
4 18
18 12
10 5
18 5
1 16
3 4
8 19
17 7
15 22
19 2
4 8
1 19
9 18
10 21
14 3
1 10
5 21
5 9
8 13
12 8
3 2
2 6
2 12
12 20
9 14
20 4
2 13
17 8
17 33
14 15
4 8
11 6
16 4
6 10
17 13
10 13
15 5
7 6
13 8
1 12
7 17
11 13
16 5
16 11
5 12
12 13
8 5
8 6
13 3
7 14
4 2
14 10
17 14
1 4
11 12
10 17
13 5
17 12
11 8
15 13
4 11
13 16
32 132
18 27
20 25
19 9
1 13
8 30
16 24
22 8
3 27
30 25
17 18
17 20
8 26
9 12
6 31
5 10
6 28
3 22
2 21
2 25
27 10
31 21
29 10
23 30
22 19
29 7
2 30
28 25
15 23
9 4
1 23
7 24
14 28
20 10
20 23
28 21
12 2
4 14
29 3
30 21
12 26
28 7
28 29
15 32
21 17
2 29
16 15
19 15
14 27
29 20
6 26
24 6
1 8
7 15
29 19
18 15
9 24
8 29
12 10
23 4
11 4
11 1
4 2
18 9
5 8
25 29
30 27
10 19
16 19
9 15
16 28
20 31
30 29
30 24
5 13
23 7
19 25
27 31
31 29
27 16
18 21
10 16
7 2
14 30
9 8
18 31
17 22
17 13
30 32
14 22
25 18
7 9
17 10
4 17
31 32
6 1
13 20
27 25
26 10
22 6
11 18
21 13
6 19
12 8
10 18
20 8
2 6
27 6
28 9
17 24
16 25
30 15
22 26
3 31
30 3
21 26
23 3
4 12
22 25
23 22
23 14
17 7
7 11
19 24
20 14
29 4
24 12
28 27
19 18
17 3
2 18
22 28
15 10
27 91
6 25
9 3
9 15
9 5
8 24
27 24
12 20
11 17
15 10
3 22
10 26
11 24
2 10
27 7
5 15
26 19
22 5
2 24
19 4
24 4
6 15
21 13
13 27
5 10
19 20
2 21
9 2
19 3
26 15
18 3
14 3
6 14
18 17
15 13
5 14
14 9
10 27
5 2
25 4
9 1
4 17
20 25
26 3
18 10
19 11
6 13
23 19
26 20
10 11
16 7
18 22
17 13
21 15
26 13
9 21
9 4
22 4
8 13
2 6
4 15
3 10
12 11
13 10
22 20
9 25
4 7
7 26
3 23
27 23
26 5
16 5
26 11
25 27
17 24
6 18
9 19
2 1
13 23
13 22
20 3
27 16
26 27
2 8
11 18
1 22
20 10
17 19
2 16
4 16
27 3
14 17
19 28
10 7
6 11
19 9
12 14
13 2
3 14
7 2
15 4
16 14
7 14
6 15
7 9
3 18
12 19
6 16
10 17
6 13
3 2
8 15
9 14
13 17
11 5
10 3
8 12
7 4
5 14
16 18
19 2
25 35
25 2
16 5
23 13
13 9
3 15
12 24
2 16
8 21
5 22
19 22
18 1
5 8
3 13
15 7
22 11
19 18
4 14
24 5
24 6
17 2
22 12
14 25
13 17
13 6
21 17
19 3
16 21
12 14
19 10
6 17
5 20
9 16
17 8
15 12
8 10
18 32
7 13
4 18
16 9
17 2
6 2
2 13
14 3
9 8
1 17
18 10
6 17
4 7
14 18
15 14
9 5
1 15
15 11
3 9
15 17
4 15
18 3
3 5
16 5
16 4
3 2
5 7
10 14
12 2
12 6
13 4
9 17
5 1
3 2
2 3
1 2
0 0
32 59
6 9
29 25
24 31
32 3
5 22
14 11
30 26
22 31
12 21
30 4
27 14
17 8
8 19
27 11
8 3
30 2
20 17
20 16
16 9
5 4
24 15
31 28
19 30
4 16
10 21
31 6
14 30
20 24
9 24
26 18
25 14
24 28
16 2
27 3
12 5
15 22
32 22
2 17
31 3
23 9
24 23
13 7
27 29
23 19
27 10
5 3
23 1
31 21
9 27
26 14
28 25
30 16
17 28
30 31
5 6
15 21
28 26
18 30
21 30
21 99
19 20
13 17
9 19
17 3
6 9
13 10
12 2
21 20
11 18
18 2
21 10
18 14
4 6
3 6
20 13
13 11
17 21
9 3
20 1
16 14
1 13
7 14
1 2
16 10
2 9
14 11
19 6
6 7
19 15
9 7
9 5
13 7
14 15
4 9
19 3
15 5
12 3
17 5
15 10
9 15
2 15
16 15
8 19
19 12
10 14
12 15
13 18
20 7
13 9
5 14
5 3
20 3
2 7
1 9
13 12
11 5
6 14
17 12
10 9
10 2
16 4
18 6
10 5
19 18
4 3
18 20
14 17
19 10
2 20
18 3
4 12
9 14
11 21
11 15
21 13
8 20
14 20
21 8
15 20
19 14
16 6
12 5
8 11
12 9
17 7
13 6
2 13
18 16
5 6
2 8
8 17
8 1
6 12
17 4
7 12
10 8
2 5
18 15
19 21
0 0
-
- New poster
- Posts: 27
- Joined: Thu Feb 14, 2002 2:00 am
Is this NP? How to solve efficiently?
Hi people,
I'm trying to solve this problem and it appears to be NP (dominating seT). I've implemented a recursive solution using backtracking, but it is giving time limit.
Anyone could help?
Regards!
I'm trying to solve this problem and it appears to be NP (dominating seT). I've implemented a recursive solution using backtracking, but it is giving time limit.
Anyone could help?
Regards!
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 am
I tried a number of pruning strategies with backtracking. I tried using some general integer programming and zero-one programming code that I have. I also tried a simple greedy algorithm to quickly get a hopefully good bound before doing any of the above. But they all take too long. What else should I try? I know this is NP-hard.
I get accepted on this problem with a small trick.
My program runs a greedy algorithm first to find a dominating set of size X,
then it will use exhaustive search up to size X-1. If no dominating set smaller than size X, just output the greedy one.
Also, using adjacency list (instead of adjacency matrix) is critical, I get accepted with list in 2s which matrix will need 9s.
My program runs a greedy algorithm first to find a dominating set of size X,
then it will use exhaustive search up to size X-1. If no dominating set smaller than size X, just output the greedy one.
Also, using adjacency list (instead of adjacency matrix) is critical, I get accepted with list in 2s which matrix will need 9s.
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 am
I am doing this already...my greedy algorithm chooses the vertex which dominates the most number of uncovered vertices at each step, and then I used the size of this dominating set to be a bound for pruning.
I am not using an adjacency list...there is nothing in the description that implies a sparse graph? Anyway, since I am taking more than 30 seconds, there must be something else that I am missing?
I am not using an adjacency list...there is nothing in the description that implies a sparse graph? Anyway, since I am taking more than 30 seconds, there must be something else that I am missing?
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 am
-
- Learning poster
- Posts: 71
- Joined: Thu Aug 21, 2003 1:56 am
I di d backtracking:
- choose an undominated vertex v
- pick v or one of its neighbours
- if I decide not to choose a vertex at this stage, remember it so I don't try it again when I recurse
- recurse
To make it go faster, I always choose an undominated vertex of least degree. I also do the obvious pruning when we have chosen more vertices than the current best set.
- choose an undominated vertex v
- pick v or one of its neighbours
- if I decide not to choose a vertex at this stage, remember it so I don't try it again when I recurse
- recurse
To make it go faster, I always choose an undominated vertex of least degree. I also do the obvious pruning when we have chosen more vertices than the current best set.
Hi,
Thank you for your reply. I appreciate it![:)](./images/smilies/icon_smile.gif)
I still can't crack this problem. I've tried many different things so far. Basically my solution does what you described. In an attempt to make my code run faster, my latest "optimization" was to make it so that before I recurse, I sort the remaining uncovered nodes by how many nodes they would cover if chosen. I then recurse using this list.
I've posted my code below. Thank you so much in advance.
[cpp]#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct town {
int id;
int links;
};
bool operator<(const town& a, const town& b) {
return a.links > b.links;
}
vector<int> list[35]; // adjacency list
int matrix[35][35]; // adjacency matrix
town *orderedTowns;
int n, minimum;
bool member(vector<int> vect, int n) {
for (int i = 0; i < vect.size(); i++)
if (vect == n) return true;
return false;
}
bool isSolution(vector<int> covered) {
for (int i = 0; i < n; i++) if (!covered) return false;
return true;
}
vector<town> constructSearchSpace(vector<int> tried, vector<int> towns, vector<int> covered) {
vector<town> orderedTowns;
for (int i = 0; i < n; i++) {
bool sem = false;
for (int k = 0; k < tried.size(); k++) if (tried[k] == i) sem = true;
if (sem) continue;
town x;
x.id = i;
x.links = 0;
for (int k = 0; k < list.size(); k++) {
if (!covered[list[k]]) x.links++;
}
orderedTowns.push_back(x);
}
sort(orderedTowns.begin(), orderedTowns.end());
return orderedTowns;
}
vector<int> calcCovered(vector<int> covered, int town) {
for (int i = 0; i < list[town].size(); i++)
if (!covered[(list[town])]) covered[(list[town])] = 1;
return covered;
}
void findSolution(vector<int> towns, vector<int> tried, vector<int> covered, int add) {
towns.push_back(add);
covered = calcCovered(covered, add);
if (towns.size() >= minimum) {
return;
}
if (isSolution(covered)) {
if (towns.size() < minimum) minimum = towns.size();
return;
}
vector<town> searchSpace = constructSearchSpace(tried, towns, covered);
for (int i = 0; i < searchSpace.size(); i++) {
if (towns.size() >= minimum - 1)
return;
tried.push_back(searchSpace.id);
findSolution(towns, tried, covered, searchSpace.id);
}
}
int main () {
int m;
while (true) {
cin >> n;
cin >> m;
minimum = 35;
for (int i = 0; i < n; i++){
list.clear();
list.push_back(i);
for (int k = 0; k < n; k++) {
if (k == i) {
matrix[i][k] = 1;
matrix[k][i] = 1;
}
else {
matrix[i][k] = 0;
matrix[k][i] = 0;
}
}
}
if (n == 0 && m == 0) break;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a;
cin >> b;
a--;
b--;
if (!member(list[a], b)) list[a].push_back(b);
if (!member(list, a)) list.push_back(a);
matrix[a] = 1;
matrix[a] = 1;
}
orderedTowns = new town[n];
for (int i = 0; i < n; i++) {
town x;
x.id = i;
x.links = list[i].size();
orderedTowns[i] = x;
}
sort(orderedTowns, orderedTowns + n);
vector<int> tried;
for (int i = 0; i < n; i++) {
vector<int> towns;
vector<int> covered;
for (int i = 0; i < n; i++) covered.push_back(0);
covered = calcCovered(covered, orderedTowns[i].id);
tried.push_back(orderedTowns[i].id);
findSolution(towns, tried, covered, orderedTowns[i].id);
}
delete orderedTowns;
cout << minimum << endl;
}
}[/cpp]
~Andrew
Thank you for your reply. I appreciate it
![:)](./images/smilies/icon_smile.gif)
I still can't crack this problem. I've tried many different things so far. Basically my solution does what you described. In an attempt to make my code run faster, my latest "optimization" was to make it so that before I recurse, I sort the remaining uncovered nodes by how many nodes they would cover if chosen. I then recurse using this list.
I've posted my code below. Thank you so much in advance.
[cpp]#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct town {
int id;
int links;
};
bool operator<(const town& a, const town& b) {
return a.links > b.links;
}
vector<int> list[35]; // adjacency list
int matrix[35][35]; // adjacency matrix
town *orderedTowns;
int n, minimum;
bool member(vector<int> vect, int n) {
for (int i = 0; i < vect.size(); i++)
if (vect == n) return true;
return false;
}
bool isSolution(vector<int> covered) {
for (int i = 0; i < n; i++) if (!covered) return false;
return true;
}
vector<town> constructSearchSpace(vector<int> tried, vector<int> towns, vector<int> covered) {
vector<town> orderedTowns;
for (int i = 0; i < n; i++) {
bool sem = false;
for (int k = 0; k < tried.size(); k++) if (tried[k] == i) sem = true;
if (sem) continue;
town x;
x.id = i;
x.links = 0;
for (int k = 0; k < list.size(); k++) {
if (!covered[list[k]]) x.links++;
}
orderedTowns.push_back(x);
}
sort(orderedTowns.begin(), orderedTowns.end());
return orderedTowns;
}
vector<int> calcCovered(vector<int> covered, int town) {
for (int i = 0; i < list[town].size(); i++)
if (!covered[(list[town])]) covered[(list[town])] = 1;
return covered;
}
void findSolution(vector<int> towns, vector<int> tried, vector<int> covered, int add) {
towns.push_back(add);
covered = calcCovered(covered, add);
if (towns.size() >= minimum) {
return;
}
if (isSolution(covered)) {
if (towns.size() < minimum) minimum = towns.size();
return;
}
vector<town> searchSpace = constructSearchSpace(tried, towns, covered);
for (int i = 0; i < searchSpace.size(); i++) {
if (towns.size() >= minimum - 1)
return;
tried.push_back(searchSpace.id);
findSolution(towns, tried, covered, searchSpace.id);
}
}
int main () {
int m;
while (true) {
cin >> n;
cin >> m;
minimum = 35;
for (int i = 0; i < n; i++){
list.clear();
list.push_back(i);
for (int k = 0; k < n; k++) {
if (k == i) {
matrix[i][k] = 1;
matrix[k][i] = 1;
}
else {
matrix[i][k] = 0;
matrix[k][i] = 0;
}
}
}
if (n == 0 && m == 0) break;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a;
cin >> b;
a--;
b--;
if (!member(list[a], b)) list[a].push_back(b);
if (!member(list, a)) list.push_back(a);
matrix[a] = 1;
matrix[a] = 1;
}
orderedTowns = new town[n];
for (int i = 0; i < n; i++) {
town x;
x.id = i;
x.links = list[i].size();
orderedTowns[i] = x;
}
sort(orderedTowns, orderedTowns + n);
vector<int> tried;
for (int i = 0; i < n; i++) {
vector<int> towns;
vector<int> covered;
for (int i = 0; i < n; i++) covered.push_back(0);
covered = calcCovered(covered, orderedTowns[i].id);
tried.push_back(orderedTowns[i].id);
findSolution(towns, tried, covered, orderedTowns[i].id);
}
delete orderedTowns;
cout << minimum << endl;
}
}[/cpp]
~Andrew
-
- Experienced poster
- Posts: 169
- Joined: Wed Oct 31, 2001 2:00 am
- Location: Singapore
This problem is quite difficult... it requires a lot of pruning... but it is possible... ![:D](./images/smilies/icon_biggrin.gif)
Try these suggestions:
- Find all "dominating nodes", and eliminate the rest. Let A and B be the set of nodes adjacent to node a and b respectively. Let a node be connected to itself. If A is a subset of B, then node a can be ignored totally.
- Search the nodes in decreasing degree. An obvious but powerful heuristic.
- When you backtrack on the stations, make sure you don't repeat. I.e, let's say you put on node 5, then recurse to node 2, don't repeat the process again with node 2 then 5, since it'll end up being the same thing done twice.
- The graphs in the input file are not all connected. Break each graph into its components before backtracking on each of them. This reduces runtime from 4-5 seconds to 1-2 seconds, so it is one of the most useful thing to do.
These are the few heuristics I can think of so far... too lazy to read and try to understand my code. They won't give you the best timings, but you should be able to get pass the time limit if you implement all of them.
Good luck.![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
Try these suggestions:
- Find all "dominating nodes", and eliminate the rest. Let A and B be the set of nodes adjacent to node a and b respectively. Let a node be connected to itself. If A is a subset of B, then node a can be ignored totally.
- Search the nodes in decreasing degree. An obvious but powerful heuristic.
- When you backtrack on the stations, make sure you don't repeat. I.e, let's say you put on node 5, then recurse to node 2, don't repeat the process again with node 2 then 5, since it'll end up being the same thing done twice.
- The graphs in the input file are not all connected. Break each graph into its components before backtracking on each of them. This reduces runtime from 4-5 seconds to 1-2 seconds, so it is one of the most useful thing to do.
These are the few heuristics I can think of so far... too lazy to read and try to understand my code. They won't give you the best timings, but you should be able to get pass the time limit if you implement all of them.
Good luck.
![:D](./images/smilies/icon_biggrin.gif)