10160 - Servicing Stations

[junjieliang]

Hmm... if you implemented all the heuristics listed you should get a better runtime. Try checking through your code and see if you have anything that would take a long time to run. An example of useless redundancy could be like:

Code: Select all

for (i = 0; i < 1000000; i++) a = i;

when you could just have a = 999999;

Though I think your problem is something more subtle than this...

Good luck!

[Moha]

i got accepted just in .094s.
and this is simple, use memoize to avoid repeated state!

[I LIKE GN]

hello all...
what is repeated states????
how can i handle them????
thx.

[crip121]

what is the output for following data set,

Code: Select all

35 90
10 22
5 19
9 29
9 6
13 33
19 19
14 9
7 28
3 31
30 29
22 30
22 1
35 21
22 35
29 14
19 30
25 35
13 10
11 11
29 14
13 4
19 20
1 29
4 19
22 1
22 29
9 25
33 10
33 33
8 24
30 19
13 26
32 14
34 6
32 12
10 33
1 18
2 29
22 8
14 11
18 15
17 10
9 7
32 33
30 12
22 23
30 33
3 1
26 11
25 4
24 12
25 32
9 31
16 33
31 33
32 34
28 23
28 33
20 5
5 32
5 27
28 24
21 6
30 5
28 22
1 11
9 19
34 5
27 5
35 28
8 10
35 22
26 19
12 8
6 7
8 24
10 31
12 20
22 27
14 12
31 9
34 1
29 3
16 13
2 9
29 7
18 22
15 27
28 27
27 25
0 0

my ac code returns 6 whereas http://uvatoolkit.com returns 8. im surprised. can any ACed coder help me plz.

[Bruno]

Test cases are weak, got acc with an internet code, it fails on this test (it handles multiple edges and/or self loops if there is any, I didnt checked the input, just generated a random one..):

Code: Select all

29 91
20 25
28 19
13 10
23 1
2 25
2 19
26 8
1 2
17 16
9 13
3 12
14 1
4 16
28 6
26 9
4 3
22 8
17 23
15 26
13 10
21 16
24 7
8 9
25 16
21 25
7 4
25 23
1 12
17 28
7 29
23 5
4 3
25 7
24 13
14 11
18 29
6 26
6 12
20 13
8 1
25 11
4 6
17 20
11 26
17 26
22 17
11 10
9 18
1 28
9 24
23 6
3 18
22 28
4 8
29 12
22 3
9 24
14 17
13 25
13 24
4 29
2 6
23 6
4 2
17 15
20 4
22 11
1 14
13 14
17 4
7 12
27 9
17 15
2 12
27 22
13 15
12 22
28 14
7 26
11 23
27 24
26 22
28 19
24 26
22 11
15 11
11 28
5 12
15 27
11 27
4 13
0 0

Answer is 5, the code that was acc outputs 6..

@crip121, yes for that case the answer should be 8!

[googol]

One more testcase that could generate TLE in some solutions. It's just a "ring" of 35 cities.

Code: Select all

35 35
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 1
0 0

Output should be 12.