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

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

hints.

Post by Gaolious » Thu Jun 16, 2005 4:19 pm


Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Thu Jun 16, 2005 6:04 pm

If you want to know about basic floyd warshall, these liknks may help you.

1. http://www.cs.toronto.edu/~heap/270F02/node42.html
2. http://www.comp.nus.edu.sg/~stevenha/pr ... raph6.html
You should never take more than you give in the circle of life.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

104...I give up

Post by mido » Wed Jun 29, 2005 4:39 pm

What's wrong with this code?:

Code: Select all

#include <iostream>

using namespace std;

#define EPS 1e-8

void output(int s,int t,int w,int p[30][30][30])
{
	if (w==0) cout<<s+1;
	else output(s,p[s][t][w],w-1,p),cout<<" ",cout<<t+1;
}

void main()
{
	double arr[30][30][30];
	int n,p[30][30][30];
	
	while (cin>>ws>>n)
	{
		int i,j,k,w;
		
		for (i=0;i<n;i++)
		{
			for (j=0;j<n;j++)
			{
				for (k=0;k<n;k++) arr[i][j][k] = 0.0,p[i][j][k]=0;
				p[i][j][1] = i;
				if (i!=j) cin>>arr[i][j][1];
			}
			arr[i][i][1] = 1.0;
		}
		
		
		for (w=2;w <= n;w++)
		{
			for (k=0;k < n;k++)
			{
				for (i=0;i<n;i++)
				{
					for (j=0;j<n;j++)
					{
						double tmp = arr[i][k][w-1]*arr[k][j][1];
						if (tmp > arr[i][j][w] + EPS) arr[i][j][w]=tmp, p[i][j][w]=k;
					}
				}
			}
		}
		
		int min_len = 50,index=-1;
		for (w = n;w >= 2;w--)
		{
			double best = 1.0;
			for (i=0;i<n;i++)
			{				
				if (arr[i][i][w]>1.01+EPS && arr[i][i][w]>best+EPS) 
				{
					index=i,min_len=w,best = arr[i][i][w];
				}
			}
		}
		
		if (index==-1) cout<<"no arbitrage sequence exists"<<endl;
		else output(index,index,min_len,p),cout<<endl;
		
	}
	
}
Thanks for the time.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Mon Jul 04, 2005 8:59 pm

Never mind...got AC...:)

xiliu.tang
New poster
Posts: 1
Joined: Wed Sep 07, 2005 4:52 pm

104 WA, please help

Post by xiliu.tang » Wed Sep 07, 2005 4:57 pm

I run pass with all the test cases I can find in the forum, but get WA after submiting, please help, thanks.
#include <iostream>
#include <list>
using namespace std;
#ifndef ONLINE_JUDGE
#include <fstream>
ifstream _xin("a.txt");
#define cin _xin
#endif
#define MAX_DEC 30

void print_path(list<int> &l)
{
list<int>::iterator mi;
list<int>::iterator i;
int mini = MAX_DEC;
int j = 0;
for (i=l.begin(); i != l.end(); i++, j++)
if (*i<mini) {
mi = i;
mini = *i;
}
cout << *mi + 1;
for (j-=2, mi++; j>0; j--, mi++) {
if (mi == l.end()) {
mi = l.begin();
}
cout << ' ' << *mi + 1;
}
cout << ' ' << mini + 1;
cout << endl;
return;
}

void join(list<int> &dest, list<int> &l1, list<int> &l2)
{
list<int> xl;
list<int>::iterator i;
for(i=l1.begin(); i!=l1.end(); i++)
xl.push_back(*i);
i = l2.begin();
for(i++; i!=l2.end(); i++)
xl.push_back(*i);
dest.clear();
for (i=xl.begin(); i!=xl.end(); i++)
dest.push_back(*i);
return;
}
void profit(double a[MAX_DEC][MAX_DEC],
list<int> path[MAX_DEC][MAX_DEC],
int n)
{
int i, j, k;
for (k=0; k<n; k++) {
double prof = 1.0;
for (i=0; i < n; i++)
for(j=0; j < n; j++) {
if (a[k]*a[k][j] > a[j]) {
double tmp = a[j];
a[j] = a[k]*a[k][j];
#ifdef _DEBUG
printf("path[%d][%d]\n", i+1, k+1);
print_path(path[k]);
printf("path[%d][%d]\n", k+1, j+1);
print_path(path[k][j]);
#endif
join(path[j], path[k], path[k][j]);
#ifdef _DEBUG
printf ("a[%d][%d](%f) = a[%d][%d](%f)*a[%d][%d](%f):(%f), path[%d][%d] = %d\n",
i+1, j+1, tmp, i+1, k+1, a[k], k+1, j+1, a[k][j], a[j], i+1, j+1, k+1);
printf("path[%d][%d]\n", i+1, j+1);
print_path(path[i][j]);
#endif
}
if (i == j && a[i][j] > 1.01) {
print_path(path[i][j]);
#ifdef _DEBUG
cout << "profit is:"<< a[i][j] << endl;
cout << "k is:" << k << endl;
#endif
return;
}
}
}
cout << "no arbitrage sequence exists" << endl;
return;
}

int main(int argc, char **argv)
{
int n;
while (cin>>n) {
double a[MAX_DEC][MAX_DEC] = { {0} };
list<int> path[MAX_DEC][MAX_DEC];
int i, j;

for(i=0; i < n; i++)
for(j=0; j < n; j++)
if (i == j) {
a[i][j] = 1.0;
} else {
cin >> a[i][j];
path[i][j].push_back(i);
path[i][j].push_back(j);
}

profit(a, path, n);
}


}

BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm

104 WA - Precision?

Post by BJM » Wed Oct 05, 2005 11:57 pm

I've tried the test cases on the board and all come up OK, but I still get a WA. Any thoughts? If it's another precision thing then I'm giving up! :evil:

Can someone who got AC blast the following cases through and let me know if they get the same output. I know that the last few are correct if you use EXACT arithmetic - i.e. no rounding AT ALL - for example the last one gives a result which is:

1.01000000000006434388668492285546792130944671547196447929482389637107356374191802709539861369205977896583603678185280560336534840538792961024

this, is >1.01, when the transactions are done EXACTLY although it has got 140 digits after the decimal point.

Thanks a million

//Problem 104
/* Additional Test Cases
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
20
1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032454
1.00049764032454 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00049764032455
1.00049764032455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00099552829497
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.00099552829498
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Output
10 16 10 16 10
1 2 1
1 2 4 1
no arbitrage sequence exists
5 6 5
no arbitrage sequence exists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1
no arbitrage sequence exists
1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1 20 1

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Nov 05, 2005 1:37 am

Your algorithm, as written, is wrong: it doesn't return the shortest arbitrage sequence but the one with minimum starting point (albeit breaking ties by sequence length).
The outermost loop should be the one indexed by the variable "j".

StepLg
New poster
Posts: 6
Joined: Wed Dec 28, 2005 10:09 am
Contact:

[104] Help to understand

Post by StepLg » Wed Jan 04, 2006 7:18 pm

The example #1:

Giving anwer is 1-2-1, the profit is 1.2*0.88=1.056-1.0$

But why the sequence 1-2-3-1 is wrong? The profit in this case is 1.2*5.1*1.1=6.732-1.0$

Where I am wrong?

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Wed Jan 04, 2006 8:29 pm

This is the reason to your question:
If there is more than one sequence that results in a profit of more than 1 percent you must print a sequence of minimal length, i.e., one of the sequences that uses the fewest exchanges of currencies to yield a profit.
Good luck!

StepLg
New poster
Posts: 6
Joined: Wed Dec 28, 2005 10:09 am
Contact:

Post by StepLg » Wed Jan 04, 2006 8:51 pm

oh! thnk you. i'm so inattentive... :'(

bjorn
New poster
Posts: 2
Joined: Fri Jan 06, 2006 3:35 am

104 - Arbitrage, is my reasoning incorrect?

Post by bjorn » Fri Jan 06, 2006 3:53 am

--------------------------------------------------------------------------------------------
MAIN PLEDGE FOR PEOPLE NOT WANTING TO READ WHOLE POST:
Please give me more sample input this problem is killing me.
--------------------------------------------------------------------------------------------

I have read all posts about people doing this problem with floyd-warshall,
using a 3D array, where the best exchange sequence from every currency to every other currency is stored for every number of steps.

I have however done it the following (not blazingly fast) way:

Code: Select all

for each starting currency
  for #steps in 1..20
    for each currency J do
      for each currency K do
        "for each currency K, calculate the largest amount we can possibly get of that 
          currency by trying an exchange from the best result for each currency J 
           received in less than #steps" 
      end
    end
   "check if there was a sequence giving arbitrage by doing an exchange back 
    to starting currency. If so, and that sequence is also shorter than any found
    before, store it, and continue with next 'starting currency'"
  end
end
"output shortest sequence found"
So I dont store a value for each step, but rather store the best possible amount of each currency in #steps or less in each iteration.

I have tried all sample inputs available on the forum and they give a correct result.
Should I be worrying about something else? I use (> 1.01) in my code. Or is there something fundamental that I am missing with my solution method here?

Dmitry R
New poster
Posts: 7
Joined: Sat Sep 17, 2005 10:42 am
Contact:

Post by Dmitry R » Fri Jan 06, 2006 6:21 pm

Do you count an exchange to starting currency as an exchange operation? If no, it can become a 21st exchange and your program will still output that there is a sequence of not more than 20 exchanges...

bjorn
New poster
Posts: 2
Joined: Fri Jan 06, 2006 3:35 am

thanks!!

Post by bjorn » Sat Jan 07, 2006 12:50 am

Thank you,

I got it right now in like 1 minute after your hint. So easy to look past some detail, in this case I had mistaken the limit to be 20 sequences, when it was actually n depending on the dimension of the input table. and counted one step too many as you hinted about.

msimonet
New poster
Posts: 1
Joined: Sat Jan 14, 2006 9:19 pm

104 arbitrage

Post by msimonet » Sat Jan 14, 2006 9:21 pm

I have a problem of WA with this C++ algorithm..
can you help me :)

#include <iostream>
#include <stack>
#include <stdio.h>

using namespace std;

int nbprec[25][25];
int prec[25][25];
float d[25][25];
float w[25][25];
bool avue[25][25][25];
int longueur;
int start;
stack<int> pile;
float maxi;

void relacher(int u,int v,int s,int n)
{


if(d[s]!=0 && nbprec[s]<n)
{
if(d[s][v]==0)
{
d[s][v]=d[s] * w[v];
prec[s][v]=u;
nbprec[s][v]=nbprec[s]+1;
}
else
{
if(d[s][v] < d[s] * w[v] && !avue[s][v])
{
d[s][v]=d[s] * w[v];
prec[s][v]=u;
nbprec[s][v]=nbprec[s][u]+1;
for(int k=1;k<=n;k++)
{
avue[s][k][v] = avue[s][k][u];
}
avue[s][v][v] = true;

}
}

}

}

void Bellman_Ford(int n,int s)
{
for(int i=1;i<=n;i++)
{
d[s] = 0;
prec[s] = 0;
nbprec[s] = 0;
}
d[s][s] = 1;

for(int k=1;k<n;k++)
{

for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
relacher(i,j,s,n);
}

if(d[s][s]>1.01)
{
i=n+1;
//j=n+1;
}

}
}

}

int main()
{
int n;
bool first = true;
while(!cin.eof())
{
cin >> n;
if(!cin.eof())
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
avue[j][k]=false;
}
avue[j][j]=true;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
cin >> w[j];
}
else
{
w = 1;
}

}
}

longueur = n+1;
maxi = 0;
start = 0;

for(int i=1;i<=n;i++)
{
Bellman_Ford(n,i);
if(d > 1.01)
{
if(nbprec[i][i] < longueur)
{
longueur = nbprec[i][i];
start = i;
maxi = d[i][i];
}
}
}

if(!first)
{
cout << endl;
}
first = false;
if(start == 0)
{
cout << "no arbitrage sequence exists";
}
else
{
int curr = start;
for(int i=1;i<=longueur;i++)
{
pile.push(curr);
curr = prec[start][curr];
}

cout << start;
while(!pile.empty())
{
cout << " " << pile.top();
pile.pop();
}
}


}


}
}

Apprentice
New poster
Posts: 1
Joined: Sat Feb 04, 2006 2:46 pm
Location: Mianyang Sichuan
Contact:

Re: 104 - Arbitrage, is my reasoning incorrect?

Post by Apprentice » Sat Feb 04, 2006 2:59 pm

I had one similar algorithm as yours at first,and I got WA.And then
I copied exactly your one.But still I got WA.
Can you help me find out what my problem is please.Here's my code:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
int shortest,n,etimes;
double ctable[21][21];
double finestr[21][21][21];

int finestpr[21][21][21];

int shortests[23];


int readdata(void)
{int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
{for(j=1;j<i;j++)
scanf("%lf",&ctable[j]);
for(j=i+1;j<=n;j++)
scanf("%lf",&ctable[j]);
ctable=double(1);
scanf("\n");
}
/* printf("%d\n",n);
for(i=1;i<=n;i++)
{for(j=1;j<=n;j++)
printf("%.2lf ",ctable[j]);
printf("\n");
}*/
return 0;
}

int done(void)
{int i,j,k;
for(i=1;i<=n;i++)
if(fabs(finestr[etimes]-1)>0.000000000001&&(finestr[etimes]>1))
{j=i;
for(k=etimes;k>=1;k--)
{shortests[k+1]=j;
j=finestpr[k][j];
}
shortests[1]=j;
for(k=1;k<=etimes+1;k++)
printf("%d ",shortests[k]);
printf("\n");
return 1;
}
return 0;
}

int process(void)
{int s,i,j,k,pr;
double t;
etimes=1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{finestr[etimes][i][j]=ctable[i][j];
finestpr[etimes][i][j]=i;
}
while(etimes<n)
{etimes++;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{//////////////////
pr=1;
finestr[etimes][i][j]=finestr[etimes-1][i][pr]*ctable[pr][j];
finestpr[etimes][i][j]=pr;
for(pr=2;pr<=n;pr++)
{t=finestr[etimes-1][i][pr]*ctable[pr][j];
if(t>finestr[etimes][i][j])
{finestr[etimes][i][j]=t;
finestpr[etimes][i][j]=pr;
}
}

////////////////
}
if(done())
return 0;
}
printf("no arbitrage sequence exists\n");
return 0;
}

int main(void)
{while(!feof(stdin))
{readdata();
process();
}
return 0;
}

if you have any testcases to show me,it will be helpful too.I see none in the forum.
Any reply is welcomed!

Post Reply

Return to “Volume 1 (100-199)”