## 104 - Arbitrage

Moderator: Board moderators

ubernewb
New poster
Posts: 6
Joined: Mon May 01, 2006 8:26 pm

### 104 WA

Hey,
I'm trying to solve the arbitrage problem, but it's not behaving as expected. It's worked fine for all the sample data I found on this forum, but I'm still getting a WA on submit. Can someone help me? It's C++, by the way.

Code: Select all

``````// Arbitrage

#include <iostream>
#include <sstream>
#include <stack>
using namespace std;

#define MAX 20
#define EPS 0.000001

string intToString(int x)
{
ostringstream ss;
ss << x;
return ss.str();
}

// Floyd-Warshall Algorithm
string FW(double table[MAX][MAX], int numCountries)
{
string output;

// Initialize the tables
double best[MAX][MAX][MAX];
int path[MAX][MAX][MAX];
for (int i = 0; i < numCountries; i++)
for (int j = 0; j < numCountries; j++)
for (int k = 0; k < numCountries; k++)
{
best[i][j][k] = 0;
if (k == 1)
{
best[i][j][k] = table[i][j];
path[i][j][k] = i;
}
}

// Begin the search
for (int steps = 2; steps <= numCountries; steps++)
{
for (int k = 0; k < numCountries; k++)
{
for (int i = 0; i < numCountries; i++)
for (int j = 0; j < numCountries; j++)
{
double temp = best[i][k][steps-1] * best[k][j][1];
if (temp > best[i][j][steps])
{
best[i][j][steps] = temp;
path[i][j][steps] = k;
}
}
}
for (int i = 0; i < numCountries; i++)
{
if (best[i][i][steps] - 1.01 > EPS)
{
stack<int> s;
s.push(i);
int next = i;
for (int j = steps; j > 0; j--)
{
next = path[i][next][j];
s.push(next);
}
output = intToString(s.top() + 1);
s.pop();
while(!s.empty())
{
output += " ";
output += intToString(s.top() + 1);
s.pop();
}
output += "\n";
return output;
}
}
}
return "no arbitrage sequence exists\n";
}

string findSeq(double table[MAX][MAX], int numCountries)
{
double best[MAX][MAX];
return FW(table, numCountries);
}

int main()
{
string input, output;
int numCountries;
while (true)
{
getline(cin, input);
if (input == "")
{
break;
}
numCountries = atoi(input.c_str());
double table[MAX][MAX];
for (int row = 0; row < numCountries; row++)
{
getline(cin, input);
istringstream *ss = new istringstream;
ss->str(input);
for (int col = 0; col < numCountries; col++)
{
if (row == col)
{
table[row][col] = 1.0;
}
else
{
*ss >> table[row][col];
}
}
delete ss;
}
output += findSeq(table, numCountries);
}
cout << output;
}``````

snublefot
New poster
Posts: 6
Joined: Wed May 25, 2005 8:21 pm
It worked fine with my solution.

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia
Hi, here's my output for your input.

10 16 10 16 10
1 2 1
1 2 4 1
no arbitrage sequence exists
5 6 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1
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
no arbitrage sequence exists
Narek Saribekyan

Dai Ming
New poster
Posts: 5
Joined: Sun Apr 23, 2006 3:54 am
Location: China
10 16 10 16 10
1 2 1
1 2 3 1
no arbitrage sequence exists
5 6 5
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1
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
no arbitrage sequence exists

this is the output of my program ,is it right?
especially the third one 1 2 3 1
It can't got AC But I do not know the prblom.
Help~~~~~~~~~~~~~~~~

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
My AC code gave the following output for the test case in this thread:

10 16 10 16 10
1 2 1
1 4 3 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

This problem has a special corrector judge, which means there can be more than one arbitrage sequence for a given test case. The output from my program for the third case is different as well.

Dai Ming
New poster
Posts: 5
Joined: Sun Apr 23, 2006 3:54 am
Location: China
10 16 10 16 10
1 2 1
1 2 3 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

this is my new result of my program,Is there any problem with it.
I think it is all right,but It can't get AC.
I am so puzzled.

Code: Select all

``````#include <iostream>
#include <stdio.h>
#include <math.h>
#include <fstream>

using namespace std;

double r,rate[20][20];
bool flag,tf;
int s[21],sf[21];
int time,t,d;

void next()
{
int i,j,k;

for( i = time - 1; i >= 0; i --)
{
if(s[i] < d - (time - i))
{
s[i]++;
for(j = i + 1; j < time; j ++)
{
s[j] = s[j - 1] + 1;
}
s[time] = s[0];
return;
} else
{
if(i > 0)
{
continue;
} else
{
if(time < d)
{
time++;
if(time >= t)
{
tf = true;

return;
}

for(k = 0; k < time; k++)
{
s[k] = k;
}
s[time] = 0;
} else
{
flag = true;
return;
}
}
}
}
}

void fang()
{
int i,j,k;
i = log10(1.01)/log10(r);

i++;
if(i*time <=d)
{
for(j= 0; j < i; j++)
{
for(k = 0; k < time; k++)
sf[j*time + k] = s[k];
}
t = i*time;
sf[t] = s[0];
tf = true;
}
}

int main()
{
int i,j;
bool h;
int f = scanf("%d",&d);
while(1 == f)
{
flag = false;
tf = false;
t = 21;
for(i = 0; i < d; i ++)
{
for(j = 0; j < d; j ++)
{
if(i == j)
{
rate[i][j] = 1.0;
}else
{
scanf("%lf",&rate[i][j]);
}
}
}
///////////////////////////////////////
time = 2;
s[0] = 0;
s[1] = 1;
s[2] = 0;

h = true;
while(1)
{
r = 1.0;
h = true;
for( i = 0; i < time; i ++)
{
r *= rate[s[i]][s[i+1]];
}

if(tf) break;
if( r >= 1.01)
{
cout<<" r - 1.01"<<endl;
h = false;
break;
}
else if( r > 1.0 && time < 11 )
{
fang();
}
else if(flag)
{
break;
}
next();
}
if(tf)
{
for(i = 0; i < t; i++)
{
cout<<sf[i]+1<<" ";
}
cout<<sf[i]+1<<endl;
}
else if(h && flag)
{
cout<<"no arbitrage sequence exists"<<endl;
}
else
{
for(i = 0; i < time; i++)
{
cout<<s[i]+1<<" ";

}
cout<<s[time]+1<<endl;

}

f = scanf("%d",&d);
}
return 0;
}

``````

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Contact:
Here is my output for this data set:

10 16 10 16 10
1 2 1
no arbitrage sequence exists ** (ERROR)
no arbitrage sequence exists
5 6 5
no arbitrage sequence exists
no arbitrage sequence exists ** (ERROR)
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

And here is my code:

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <math.h>
using namespace std;

#define T(_I, _J) table[_I+(_J<<5)]
#define C(_I, _J) cost[_I+(_J<<5)]
#define N(_I, _J) next[_I+(_J<<5)]

double weight ( double v )
{
return 1.0-(log(v)/10000.0);
}

int main ( void )
{
int n;
double table[32<<5];
double cost[32<<5];
int next[32<<5];

while (cin >> n)
{
int i, j, k;

for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
N(i, j) = j;

if (j==i)
{
T(i, j) = 1.0;
C(i, j) = 100000;
}
else
{
double in;
cin >> in;
T(i, j) = in;
C(i, j) = weight(in);
}
}

for (k=0; k<n; k++)
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
double sum = C(i, k) + C(k, j);

if (sum < C(i, j))
{
C(i, j) = sum;
N(i, j) = N(i, k);
}
}

vector<int> paths[20];
int minsteps = n+1;
int mini = -1;

for (i=0; i<n; i++)
{
int w = i;
int l;
double a = 1.0;
int steps = 0;

while (true)
{
paths[i].push_back(w);
steps++;

if (steps > n)
break;

l = w;
w = N(l, i);
a *= T(l, w);

if (w == i)
{
if (a <= 1.0)
break;
else if (a > 1.01)
{
paths[i].push_back(w);

if (steps < minsteps)
{
minsteps = steps;
mini = i;
}

break;
}
}
}
}

if (mini == -1)
{
cout << "no arbitrage sequence exists" << endl;
}
else
{
for (i=0; i<(paths[mini].size()-1); i++)
cout << paths[mini][i]+1 << " ";
cout << paths[mini][paths[mini].size()-1]+1 << endl;
}

}

return 1;
}``````
I know my problem is with how I'm weighting each number, (and maybe that I am weighting each number), however, I tried two different methods of doing this, the method you see there, which produces those results, and a counting the digits which fixed (atleast #3) of the outputs, and broke (atleast #1) of the outputs, I tried combining the two methods, but with no success, any ideas?

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm

### Thanks

This hint is really helpful and gits fast gives the whole solution.
I write my solution after reading this hint, got AC, but it takes 1.340s which is much longer than most of others. So i think it should be solved in a o(n^3) algo. Someone has said it can be done with DP,but i can' t catch that.

mindboggler
New poster
Posts: 6
Joined: Fri Dec 30, 2005 10:29 am

### 104 - Please explain the test case?

4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111

We are require to find the lexicographically smallest sequence giving profit greater than 1.0 right?
Then Shouldnt the answer sequence be
1 2 3 1 ?
When we start with 1 unit of currency 1, by above sequence we end up with 2.1886 unit of currency 1. That is a profit of over 100%

But the answer is 1 2 4 1

Plz Explain. Thank you

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
We are require to find the lexicographically smallest sequence
No, any minimum-length sequence will do. (So, there can be multiple correct answers.)
giving profit greater than 1.0 right?
greater than 1%.

New poster
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am
Contact:

### hi and a few qns

f-w is already an application of DP...

btw tks abt the crash course abt f-w. but then isnt f-w only suitable for graphs with no negative weights? It is possible for a profiting sequence to exist (in some cases) if a non-simple path is taken (ie if a currency is tranverse twice). for example a->b->a->b->a (if a->b->a yields a net profit but it isnt sufficent). that would be the equivelant of a negative weight cycle if its modelled into a graph. bt f-w doesnt deal with paths which r not simple.

there's such a way of doing this using matrix multiplication, but its complexity is O(v^3lg(v)).

would appreciate if somebody can explain... maybe f-w can somehow be modified?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
You can use it to detect negative cycles.
This problem is explained in Sedgewick (scroll down to "Arbitrage"):
http://www.awprofessional.com/articles/ ... Num=8&rl=1

New poster
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am
Contact:

### tip for arbitrage-> dont use logs

ive noticed quite a number of pple used logrithms. although logs can convert multiplication into sums, thus can be used as weights of graphs, they can affect precision as one converts the weights into logs and back again. try to find ways to use multiplication to find the optimal shortest path.

abhishake
New poster
Posts: 2
Joined: Fri Sep 22, 2006 6:21 pm

### 104 - Arbitrage

Hi. I was solving 104 using brute force. I know it is not the popular method for the problem but since ive begun i want to get it done with. I seem to have a problem understanding the expected output

i/p:
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111

expected o/p:
1 2 4 1

my o/p:
1 2 3 1

The problem states that "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." .... now since 1 2 3 1 is also one of the minimal length sequences is it a valid o/p ?
I am further confused as 1 2 4 1 is not even the most profitable minimal length sequence (i found it to be 4 3 2 4).

Am i missing out on something or understood the q wrong ?
or will my output also be accepted ?