10160 - Servicing Stations

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

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10160 - Servicing Stations

Post by .. » Thu Oct 03, 2002 7:59 pm

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

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » Thu Oct 03, 2002 9:38 pm

Nice long message, eh?

The output should be

2
1
3
1
1
3
2
7
1
1
4
5
5
7
8
5
1

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Oct 04, 2002 6:30 am

oh~~
I got the same output as you~~
Can't find what's wrong :(

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

Is this NP? How to solve efficiently?

Post by uzioriluzan » Tue Mar 04, 2003 9:32 pm

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!

youquan
New poster
Posts: 2
Joined: Sun Apr 06, 2003 4:22 pm

Post by youquan » Sun Jun 22, 2003 5:08 pm

Try this:
Input:

8 10
1 2
1 3
1 4
1 5
6 2
6 3
6 4
6 5
1 7
7 8
0 0

The output should be 2

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sun Nov 09, 2003 9:33 am

I am getting time limit exceeded using exhaustive search ( recursive ). How to do it faster?

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Thu Mar 11, 2004 7:02 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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Mar 11, 2004 7:21 am

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

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Thu Mar 11, 2004 7:50 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?

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Thu Mar 11, 2004 8:30 am

I tried using a randomized algorithm to get a good dominating set, and of all the examples above I can always get within 1. The randomized part only takes 1 second to execute, but I seem to be having a lot of trouble getting the other part to work quickly enough.

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

Post by drewsome » Tue Apr 13, 2004 8:23 am

Yo, I'm also having trouble with this question (I keep getting Time Limit Exceeded). Have you managed to solve it by any chance? If so -- any hints? Thanks in advance.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Post by howardcheng » Tue Apr 13, 2004 4:29 pm

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.

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

Post by drewsome » Thu Apr 15, 2004 9:47 am

Hi,

Thank you for your reply. I appreciate it :)

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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Thu Apr 15, 2004 4:31 pm

This problem is quite difficult... it requires a lot of pruning... but it is possible... :D

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

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

Post by drewsome » Sun Apr 18, 2004 10:35 am

Thank-you so much!!

I implemented all of your suggestions, and I got my solution accepted (runtime was 28.586 seconds).

I'm curious as to how I could make my program go faster. Is there some obvious heurestic that I missed?

-Andrew

Post Reply

Return to “Volume 101 (10100-10199)”