10944 - Nuts for nuts..

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

Moderator: Board moderators

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Fri Jun 23, 2006 2:33 pm

bfs is unnecessary, the dist between x1,y1 and x2,y2 is
max(x1~x2, y1~y2). use bitmask DP, that wont give tle, i used this with time complexity O(n^2*2^n) and memory O(n*2^n) as described earlier in this forum
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Aug 29, 2006 11:14 pm

The dp for TSP is one of the standard dp for subsets. It is good to learn it.
It is basically 3 nested for loops. At the end, we need to take care of the last segment back to the start vertex.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Wed Jan 17, 2007 10:57 pm

I have solved this problem by this way

but a single if condition has confused me...

Code: Select all

...................................
This problem takes only 1.76 seconds

but when i have changed a if conditions format then it takes 6.52 seconds
why can any body explain me ...

Code: Select all

.................................

Code: Select all

   if (u) {
		if (Graph[x][u] < sum) return ;
		else Graph[x][u] = sum;
	}
it takes 6.52 seconds

Code: Select all

   if (u) {
		if (Graph[x][u] > sum) Graph[x][u] = sum;
		else return ;
	}
it takes 1.76 seconds
Thanks
MAP

After discussion i will cut my code :D
Last edited by mohiul alam prince on Sun Jan 28, 2007 9:38 am, edited 1 time in total.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Jan 18, 2007 7:33 am

mohiul alam prince wrote:

Code: Select all

   if (u) {
		if (Graph[x][u] < sum) return ;
		else Graph[x][u] = sum;
	}
it takes 6.52 seconds

Code: Select all

   if (u) {
		if (Graph[x][u] > sum) Graph[x][u] = sum;
		else return ;
	}
it takes 1.76 seconds
Thanks
MAP

After discussion i will cut my code :D

Look at this part:

Code: Select all

   if (u) {
		if (Graph[x][u] > sum) Graph[x][u] = sum;
		else return ;
	}
which is equivalent to:

Code: Select all

   if (u) {
		if (Graph[x][u] <= sum) return ;
		else Graph[x][u] = sum;
	}
but your equivalent code was

Code: Select all

   if (u) {
		if (Graph[x][u] < sum) return ;
		else Graph[x][u] = sum;
	}
the function returns when Graph[x]<sum, but in first case function returns when Graph[x]<=sum.. so your code dont return when Graph[x]==sum. thats why it takes more time.

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sun Jan 28, 2007 9:40 am

Thankx EmotionalBlind :D
i have got it..

MAP

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Thanks

Post by nymo » Fri Apr 06, 2007 4:03 pm

I 've got ACC with topdown approach (recursion with memoization) ... at last.
Thanks everyone. I 've done pretty much what ayon said.
regards,
nymo

Post Reply

Return to “Volume 109 (10900-10999)”