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

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

Post by junjieliang » Sun Apr 18, 2004 2:30 pm

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

Good luck!

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

faster Solution

Post by Moha » Thu Feb 17, 2005 5:56 pm

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

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

?????????

Post by I LIKE GN » Wed Aug 10, 2005 5:59 pm

hello all...
what is repeated states????
how can i handle them????
thx.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 10160 - Servicing Stations

Post by crip121 » Sat Oct 03, 2009 9:39 pm

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
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 10160 - Servicing Stations

Post by Bruno » Thu Aug 30, 2012 3:45 am

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
New poster
Posts: 2
Joined: Wed Jun 25, 2014 10:56 pm

Re: 10160 - Servicing Stations

Post by googol » Sat Jan 10, 2015 6:19 pm

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.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest