104 - Arbitrage

[ytz]

BTW, I think on this problem BFS is much better than DFS. Using DFS you need to search all solution spaces because you never know there's a shorter solution ahead. By BFS you can stop at the first solution you met.

[ytz]

actually i havent solved this problem yet. but i heard something from my friend, if there are several shortest possible answers, choose one with biggest profit. hope it can help.

I guess this is not true. For example in the second test case the sequence yield the biggest profit is 2 4 3 2, which is about 89.** better than the 1 2 4 1 sequence given as standard but with the same length.

[Larry]

Try taking the log of the numbers, and then look up shortest paths again...

[ytz]

My BFS solution result in "out of memory" so I change it to use BFS, however I have the same problem as RAV now, it gives out "WA" on about 5.5 seconds after showing running(5) for a while. BTW, anyone know what this "5" means?

[ytz]

My BFS solution result in "out of memory" so I change it to use BFS, however I have the same problem as RAV now, it gives out "WA" on about 5.5 seconds after showing running(5) for a while. BTW, anyone know what this "5" means?

Sorry,I mean from BFS to DFS.

[ehaque]

Is there any helpful guy who can post some test cases , cause my program works fine with test cases and I used DP . Please helppppp!!!

[ezra]

here is some test case
20
0.38 0.88 0.33 0.85 0.76 0.62 0.15 0.69 0.42 0.96 0.19 0.62 0.54 0.90 0.95 0.08 0.99 0.78 0.42
0.51 0.86 0.43 0.20 0.21 0.27 0.24 0.21 0.20 0.37 0.11 0.74 0.50 0.44 0.52 0.71 0.62 0.49 1.03
0.51 0.06 0.83 0.68 0.60 0.48 0.37 0.11 0.15 0.68 0.47 0.54 0.63 0.80 0.49 0.23 0.87 1.03 0.57
0.37 0.62 0.55 0.94 0.58 0.61 0.09 0.85 0.69 0.78 0.92 0.89 0.76 0.46 0.25 0.83 0.21 0.49 0.12
0.01 0.40 0.31 0.09 0.38 0.42 1.03 0.81 1.00 0.04 0.91 0.46 0.21 0.41 0.05 0.65 0.69 0.84 0.70
0.88 1.04 0.69 0.38 0.61 0.57 0.36 0.24 0.72 0.12 0.95 0.71 0.98 0.56 0.34 0.76 0.33 0.68 0.94
0.03 0.40 0.73 0.70 0.25 0.24 0.41 0.92 0.71 0.87 0.23 0.75 0.76 0.59 0.51 1.00 0.55 0.62 0.70
0.65 0.72 0.95 0.65 0.40 0.99 0.59 0.25 0.85 0.80 0.45 0.64 0.46 0.36 0.77 0.28 0.92 0.24 0.92
0.78 0.49 0.05 0.01 0.73 0.06 0.98 0.67 0.29 0.27 0.48 0.43 0.46 0.61 0.71 0.76 0.56 0.28 0.33
0.81 0.73 0.92 0.16 0.97 0.77 1.03 0.86 0.38 0.62 0.89 0.48 0.45 0.08 1.04 0.76 0.11 0.20 0.18
0.63 0.70 0.49 0.64 0.73 0.51 0.41 0.51 0.35 0.31 0.33 0.75 0.10 0.84 0.94 0.90 1.02 0.33 0.80
0.67 0.57 0.94 0.86 0.02 0.67 0.14 0.49 0.75 0.82 0.41 0.28 0.45 0.31 0.31 0.32 0.21 0.03 0.78
0.26 0.88 0.17 0.01 0.56 0.04 0.93 1.04 0.79 0.39 0.36 0.69 0.65 0.80 0.99 0.30 0.42 1.00 0.99
0.42 0.10 0.00 0.35 0.38 0.56 0.64 1.01 0.67 0.55 0.56 0.41 0.05 0.16 0.42 0.74 0.40 0.26 0.83
0.58 1.03 0.66 0.16 0.84 0.06 0.69 1.04 0.62 0.77 0.98 0.67 0.50 0.05 0.74 0.60 0.89 0.91 1.03
0.57 0.68 0.95 0.99 0.27 0.14 1.02 0.34 0.23 0.97 0.22 0.66 0.70 0.09 0.64 0.20 0.39 0.14 1.04
0.37 0.14 0.50 0.64 0.30 0.17 1.00 1.01 0.98 0.34 1.03 0.72 0.94 0.67 0.74 0.82 0.75 0.57 0.69
0.84 0.29 0.53 0.01 0.77 0.09 0.93 0.94 0.11 0.32 0.36 0.11 1.00 0.38 0.30 0.74 0.80 0.77 0.94
0.04 0.48 0.97 0.54 0.81 0.33 0.67 0.10 0.83 0.94 0.22 0.52 0.90 0.62 0.79 0.90 0.40 0.26 0.23
0.55 0.48 0.75 0.96 0.65 0.21 0.98 0.71 0.91 0.63 0.94 0.62 0.56 0.90 0.89 0.00 0.43 0.43 0.08
3
1.2 .89
.88 5.1
1.1 0.15
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111
2
2.0
0.45
6
0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.1 0.0 0.0
0.0 0.0 1.0 0.0 0.0
0.0 5.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 9.0
0.0 0.0 0.0 0.0 1.0

one of the possible answer is
10 16 10 16 10
1 2 1
1 2 4 1
5 6 5

try to look the best profit if the path more than one.
good luck.

[ehaque]

hey ezra ...thanks a lot man .... my program was all ok ...but i used to print my solution incorrectly ... 10 16 10 16 10 was printed as 10 16 10 although my program calculated it as 10 16 10 16 10 .... simple silly mistake with my print function .... thanks again .. that really helped.

[xbeanx]

Try changing the while(scanf( ... ) == 1)

to

while(scanf(...) != 0)

see if that helps..


Or, check the scanf int bug. You may be processing an extra newline.

http://dec.bournemouth.ac.uk/support/co ... scanf.html

[xbeanx]

Try changing the while(scanf( ... ) == 1)

to

while(scanf(...) != 0)

see if that helps..


Or, check the scanf int bug. You may be processing an extra newline.

http://dec.bournemouth.ac.uk/support/co ... scanf.html

[xbeanx]

This can be done with a 2D matrix.

[de]

this problem is hard for me><
can someone help me?><
[cpp]#include <iostream.h>
#include <math.h>

int main()
{
int stack[30];
int p;
int n;
int k;
int i;
int tx;
int t,t2;
double data[30][30];
int path[30][30];
int step[30][30];
int find;
int min;

while (cin >> n)
{
for (t=1 ;t<=n ;t++)
{
for (t2=1 ;t2<=n ;t2++)
{
if (t==t2)
{
data[t][t2]=1;
continue;
}
else
cin >> data[t][t2];
}
}

for (t=1 ;t<=n ;t++)
{
for (t2=1 ;t2<=n ;t2++)
{
path[t][t2]=t;
step[t][t2]=1;
}
}

for (k=1 ;k<=n;k++)
{
for (t=1 ;t<=n;t++)
{
for (t2=1 ;t2<=n;t2++)
{
if (t==t2 && data[t][t2]>=1.01 && step[t][t2]<=n)
continue;

if (data[t][k]*data[k][t2]>data[t][t2])
{
data[t][t2]=data[t][k]*data[k][t2];
step[t][t2]=step[t][k]+step[k][t2];
path[t][t2]=path[k][t2];
}
}
}
}

min=step[1][1];
tx=1;

find=0;
for (t=n ;t>=1 ;t--)
{
if (data[t][t]>=1.01 && step[t][t]<=n)
{
find=1;
if (step[t][t]<min)
{
min=step[t][t];
tx=t;
}
}
}

if (!find)
{
cout << "no arbitrage sequence exists" << endl;
continue;
}

i=path[tx][tx];

stack[0]=tx;

for (p=1 ;p<=step[tx][tx] ;p++)
{
stack[p]=i;
i=path[tx];
}

for (p=p-1 ;p>=0 ;p--)
{
cout << stack[p];
if (p)
cout << " ";
else
cout << endl;
}
}

return 0;
}[/cpp]

[xbeanx]

You have the right idea.. This problem can be done with a Floyd Warshall, as you have tried, but it becomes a lot easier if you use a three dimensional array to record your path and distance.

I have seen it done with a 2D matrix, but it is hard to understand.

If you use a couple 3D matrices, you can keep track of the information you need easier.

You then just do a floyd warshall, looking for the best path at each previous level of the 3D matrix.

Code: Select all

if(dist[i][x][k-1]*rates[x][j] > dist[i][best][k-1]*rates[best][j])
	best = x;
dist[i][j][k] = dist[i][best][k-1]*rates[best][j];
path[i][j][k] = best;

In the above code, which lies at the center of the floyd warshall, you can just increase x until you find the largest value. When that happens, you update your distance and path matricies from the original matrix.

If you need any more help just ask.

[Almost Human]

if there are more than one solution, pick the solution that takes the shortest sequence

[b3yours3lf]

I still don't understand why the input #3 give output 1 2 4 1.
If we choose the best profit the output should be 2 4 3 2, right?
thanks