## 10944 - Nuts for nuts..

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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:
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:
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
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)

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
My program gives the same output.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm
Try the input like this:

2 2
L.
..

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

Wojciech

DongJoo Kim
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea
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
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
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
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:
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
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
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:
Cache the bitmask and where you're at.

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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 :)

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