10944 - Nuts for nuts..

[Dominik Michniewski]

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

[mf]

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]

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

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

[Cho]

My program gives the same output.

[w k]

Try the input like this:

2 2
L.
..

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

Wojciech

[DongJoo Kim]

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]

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]

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

[DongJoo Kim]

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]

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]

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]

could someone explain how to implement the dynamic programming solution?

[Larry]

Cache the bitmask and where you're at.

[arsalan_mousavian]

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]

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