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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Oct 27, 2005 9:22 am

Mf, how did you compute 19 in 2nd case ?

Code: Select all

7 11 
.....1..... 
........... 
........... 
........... 
2....3....4 
........... 
........... 
I modified sample to easiest reading text below.
Distance matrix is as folow

Code: Select all

 |1  2  3  4
-+----------
1|0  5  4  5
2|5  0  5 10
3|4  5  0  5
4|5 10  5  0
Best route is, I think, 1-2-3-4-1 or 1-4-3-2-1, both of length 20.
Could you show me route of length 19, starting and ending in 1 ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Oct 27, 2005 9:38 am

Actually, that CodeMaker's test was not correct. My program interpreted it as if it was the first test below.

For this input:

Code: Select all

11 7
.....L.
.......
.......
.......
.......
.......
..#....
#....#.
.......
.......
....... 

7 11
.....L.....
...........
...........
...........
#....#....#
...........
........... 
the output should be: 19, 20.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Oct 27, 2005 9:58 am

Thanks for reply :D
I thought, that there must be any easy explanation :D

And could you tell me right answer for cases:

Code: Select all

10 10
..........
..#....#..
..#....#..
..#....#..
..##L###..
..#....#..
..#....#..
..........
..........
..........
10 10
#..#..#..#
..........
..........
#..L..#..#
..........
..........
#..#..#..#
..........
..........
#..#..#..#
??
My program outputs:
22
48

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Thu Oct 27, 2005 11:39 am

My program gives the same output.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k » Sat Nov 05, 2005 12:32 am

Try the input like this:

2 2
L.
..

The correct output is 0. At least it was my problem. Have AC! :lol:

Wojciech

DongJoo Kim
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea

Post by DongJoo Kim » Mon Nov 14, 2005 4:31 am

There is another approach. What I did was SA(Simulated Annealing).

Just calculate the cost function.
Cost function would be the order of visiting each nuts.

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Mon Nov 14, 2005 6:45 am

DongJoo Kim wrote:There is another approach. What I did was SA(Simulated Annealing).

Just calculate the cost function.
Cost function would be the order of visiting each nuts.
How to prove this?

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Mon Nov 14, 2005 7:25 am

I got a lot of WA for this problem.
Can anyone post more test I/O?
Thanks.

DongJoo Kim
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea

Post by DongJoo Kim » Mon Nov 14, 2005 1:01 pm

yatsen wrote:
DongJoo Kim wrote:There is another approach. What I did was SA(Simulated Annealing).

Just calculate the cost function.
Cost function would be the order of visiting each nuts.
How to prove this?
For the answer, I surf the web and read the article about the prove of SA(Simulated Annealing). However, I can't understand. :-?

Only one thing I know is that the value will be converged to the proper answer as long as we have enough N(iteration) and T(temparture- uncertainty).

I do not want to recommend to use this algorithm first. However, if there is nothing you can do, SA can be the final choice.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Fri Nov 18, 2005 12:27 am

i read the pdf and found it nice but i dont know how to implement it without looking like backtracking.... anyone can give me a hint?

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Mon Nov 21, 2005 6:18 pm

Cho wrote:My solution tries all possible visiting orders of the nuts by a DFS with 2 hueristics to cut off. The first one is to cut off if the current cost plus the under-estimated future cost is not less than minimum cost. The second one is not to visit the k-th nut from the i-th nut if there is a j-th nut such that the j-th nut is not visited yet and cost(i->j)+cost(j->k)<=cost(i->k).
I use your method but I got WA. Can anyone help?
Here is my code:

Code: Select all

#include <stdio.h>
#include <string.h>
#define Max 21
#define Maxint 2147483647
typedef struct
{
	int x,y;
}Node;
Node nut[15];
int Row,Column,used[Max],seq[Max],D[16][16],check[16][16];
char map[Max][Max];
int n,Lx,Ly,min;

int distance(int x1,int y1,int x2,int y2)
{
	int x=abs(x1-x2), y=abs(y1-y2);
	return (x>y ? x:y);
}

int checkshort(int i,int j)
{
	int k,a,b,c;
	for(k=0; k<n; k++)
	{
		if(k==i || k==j ) continue;
		a=D[i][k];
		b=D[k][j];
		c=D[i][j];
		if(a+b<=c)
			return 0;
	}
	return 1;
}

void dfs(int i,int k,int v)
/* i: dfs from this node, k:the rank in seq[], v: path length so far */
{
	int j,v2,t;
	v2=D[seq[k-1]][n];
	if(v+v2>=min)
		return;
	if(k==n+1)
	{
		v+=v2;
		if(v<min) min=v;
		return;
	}
	for(j=0; j<n; j++)
	{
		if(used[j]) continue;
		if(!check[i][j])
		{
			for(t=0; t<n; t++)
			{
				if(t==i || t==j) continue;
				if(!used[t])
				{
					t=-1;
					break;
				}
			}
			if(t==-1) continue;
		}
		used[j]=1;
		seq[k]=j;
		v2=v+D[seq[k]][seq[k-1]];
		dfs(j,k+1,v2);
		used[j]=0;
	}
}

void main()
{
	int i,j;
	/*freopen("in.txt","r",stdin);*/
	while(scanf("%d %d",&Row,&Column)==2)
	{
		for(i=0; i<Row; i++) scanf("%s",map[i]);
		n=0;
		for(i=0; i<Row; i++)
			for(j=0; j<Column; j++)
			{
				if(map[i][j]=='L')
				{
					Lx=i;
					Ly=j;
				}
				else if(map[i][j]=='#')
				{
					nut[n].x=i;
					nut[n++].y=j;
				}
			}
		nut[n].x=nut[n+1].x=Lx; nut[n].y=nut[n+1].y=Ly;
		memset(used,0,sizeof(used));
		for(i=0; i<=n; i++)
			for(j=i+1; j<=n; j++)
				D[i][j]=D[j][i]=distance(nut[i].x,nut[i].y,nut[j].x,nut[j].y);
		for(i=0; i<=n; i++)
			for(j=i+1; j<=n; j++)
				check[i][j]=check[j][i]=checkshort(i,j);
		min=Maxint;
		seq[0]=n;
		dfs(n,1,0);
		printf("%d\n",min);
	}
}

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 » Sat Mar 04, 2006 7:51 pm

could someone explain how to implement the dynamic programming solution?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Mar 10, 2006 8:33 pm

Cache the bitmask and where you're at.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Tue Mar 14, 2006 12:12 pm

here is some input , i hope it helps

Code: Select all

20 20
#..................#
....................
....................
....................
....#...............
...............#....
....................
....................
#...........#.......
....................
.........L..........
....................
............#.......
....................
..####..............
....................
...#..........#.....
....................
....................
#..................#
2 2
.L
..
8 8
#......#
.#....#.
..#..#..
...##...
...L....
#..#..#.
.#...#..
..#.#...
and the output is :

Code: Select all

79
0
26

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

I need help :)

Post by nymo » Fri Jun 23, 2006 1:37 pm

Hi, I 've tried bfs to make the distance matrix. Then I try backtracking and get TLE. I get correct answer for all test cases of the threads but for some of them, my program takes a lot of time. Can you share your cut off strategy... please, thanks :)

Post Reply

Return to “Volume 109 (10900-10999)”