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

[Yarin]

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

[..]

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

[uzioriluzan]

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]

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]

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

[howardcheng]

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.

[howardcheng]

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]

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]

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]

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]

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]

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

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.

[drewsome]

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