104 - Arbitrage

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

Moderator: Board moderators

Post Reply
ytz
New poster
Posts: 5
Joined: Tue Jul 22, 2003 4:31 pm

DFS and BFS

Post by ytz » Thu Jul 24, 2003 6:32 pm

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
New poster
Posts: 5
Joined: Tue Jul 22, 2003 4:31 pm

not necessarily the biggest.

Post by ytz » Thu Jul 24, 2003 8:35 pm

titid_gede wrote: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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Jul 24, 2003 8:35 pm

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

ytz
New poster
Posts: 5
Joined: Tue Jul 22, 2003 4:31 pm

WA

Post by ytz » Fri Jul 25, 2003 12:10 am

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
New poster
Posts: 5
Joined: Tue Jul 22, 2003 4:31 pm

Re: WA

Post by ytz » Fri Jul 25, 2003 12:10 am

ytz wrote: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
New poster
Posts: 3
Joined: Tue Jul 29, 2003 12:40 am

Input !

Post by ehaque » Tue Jul 29, 2003 12:46 am

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!!! :(

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra » Tue Jul 29, 2003 2:30 am

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
New poster
Posts: 3
Joined: Tue Jul 29, 2003 12:40 am

Thanks a lotttt!

Post by ehaque » Tue Jul 29, 2003 3:41 am

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Mon Aug 04, 2003 8:35 pm

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Mon Aug 04, 2003 8:41 pm

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Mon Aug 04, 2003 8:53 pm

This can be done with a 2D matrix.

de
New poster
Posts: 11
Joined: Sat Mar 08, 2003 3:46 pm

104 Wrong Answer

Post by de » Wed Aug 27, 2003 12:18 pm

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Wed Aug 27, 2003 4:45 pm

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Tue Sep 02, 2003 5:30 am

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

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf » Sat Sep 13, 2003 8:34 am

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

Post Reply

Return to “Volume 1 (100-199)”