10702 - Travelling Salesman

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

Moderator: Board moderators

zhou junyu
New poster
Posts: 2
Joined: Mon Sep 15, 2003 5:58 pm

10702 - Travelling Salesman

Post by zhou junyu » Mon Aug 30, 2004 4:40 pm

I use DP to solve this problem. The complexity of my algo is lg(T)*C^3

my program take about 2 second to run all the test case.

How to make the time less than 1 second?
any better algo?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Aug 30, 2004 5:01 pm

My Pascal solution, having complexity of T*C^2, runs in 0.6 sec. :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

zhou junyu
New poster
Posts: 2
Joined: Mon Sep 15, 2003 5:58 pm

Post by zhou junyu » Mon Aug 30, 2004 5:44 pm

yup, I got it, thanks.


Observer wrote:My Pascal solution, having complexity of T*C^2, runs in 0.6 sec. :wink:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Sep 15, 2004 9:37 pm

Would you please describe your procedure plz (just the algorithm)? Seeming my algo. is totally wrong.
"Everything should be made simple, but not always simpler"

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Sep 16, 2004 5:52 am

A "state" can be given by : [current location, number of inter-city travels he has done].

Try to think of a way to fill the table.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

uzurpatorul
New poster
Posts: 5
Joined: Fri Oct 22, 2004 10:21 am

Post by uzurpatorul » Fri Oct 22, 2004 8:01 pm

use dynamic programming and store the max value per step, the algo to find the max is:

int findMax(int c, int s, int e, int t, int step) {

if (step == t) {
for (i = 0; i < e; i++)
Max(cost[s][endcity - 1])

}
else
for (j = 0; j < c; j++) {
Max(cost[s][j]+ findMax(c, j, e, t, step + 1));

}
return max;
}

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

10702 - Travelling Salesman

Post by Nazmul Quader Zinnuree » Mon Apr 03, 2006 5:42 pm

Hello,
I've found no posts on this problem. Is it so easy or soo hard one?
Plz, somebody give me some hints on how to solve this problem. How to form the DP table? In details.....

Thanks?

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

10702 PE

Post by Zuza » Thu Apr 26, 2007 12:43 pm

I'm printing the output with

Code: Select all

printf( "%d\n", best );
just as the problem suggests it and I don't know how to get rid of the presentation error.
I tried leaving blank after each set and leaving a blank line between each set.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Apr 26, 2007 6:23 pm

For each input set produce one line of output, the total profit he can earn in the corresponding tour.
Why are you concerned about printing additional blank lines?
There shouldn't be any blank lines at all.

.. and don't create a new thread for a problem that already exists. :)

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

Post by Zuza » Thu Apr 26, 2007 7:25 pm

My original method ( printf( "%d\n", best ); ) prints a line per set.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Apr 26, 2007 7:37 pm

Can you PM me your code?

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

whatz wrong .......... ???????????????????????????

Post by Ron » Tue Feb 19, 2008 11:08 am

i am getting TLE in DP solution and getting WA in brute force solution....plz tell me problems ....

EDIT : ACed by T * C^2 complexity
Last edited by Ron on Sun Oct 25, 2009 8:59 am, edited 1 time in total.

golden eye
New poster
Posts: 2
Joined: Sat Jan 03, 2009 9:24 am

Re: 10702 - Travelling Salesman

Post by golden eye » Wed Jan 26, 2011 10:02 am

how the output is 7 for the sample test case ??

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10702 - Travelling Salesman

Post by Shafaet_du » Wed Jun 08, 2011 9:44 am

1-3,3-2
5+2=7

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 10702 - Travelling Salesman

Post by @li_kuet » Mon Jun 18, 2012 12:34 am

Why i am getting Wrong Answer ????
here is my code >>

Code: Select all

Removed After AC :)
Silly mistake at the time of function calling .............

Post Reply

Return to “Volume 107 (10700-10799)”