## 104 - Arbitrage

Moderator: Board moderators

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### 104 Arbitrage ??

(sorry, my english is poor... )

If there is a mutiple cycle in this problem ,how can I do it?
FOR EXAMPLE:
for N = 10
1 - 2 - 3 - 1 - 2 - 3 - 1 ,
or something similiar...

I tried to solve the problem by using DFS,but when there is a mutiple cycle
my program may not work.

Can you give me some tips?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
use another variable that tell u that you've visited that node (here i used visited variable), example like this (do_nothing function):
[c]
int do_nothing(int matrix[X][X], visited[X], int dim, int i) {
int ct;
for (ct = 0; ct < dim; ct++)
if ((matrix[ct] == 1) && (visited[ct] == 0)) {
visited[ct] = 1;
do_nothing( matrix, visited, dim, i);
visited[ct] = 0; //dont forget to return this variable to 0
}
return 0;
}
[/c]

R
New poster
Posts: 18
Joined: Wed Jan 15, 2003 4:35 pm
i'm also facing this problem right now. the trouble is, you may oversee some solutions if you don't allow cycles:

see this example:
2
1.1
0.915

1 2 1 gives 1.0065, thus less than 1%, but doing
1 2 1 2 1 gives you 1.01304225, which is more than 1% profit and a valid solution.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

### #104 - Arbitrage (Runtime Error: Invalid memory access)

[cpp]/* @JUDGE_ID: 18472KP 104 C++ "All Pairs Shortest Paths" */

#include <stdio.h>

int path;

void printpath(int src, int pos) {
if (src != pos)
printpath(src, path[src][pos]);
printf("%d ", pos + 1);
}

int main() {
bool arbitrage;
double conv;
int ncurr, i, j, k;

while (scanf("%d", &ncurr) == 1) {
for (i = 0; i < ncurr; i++)
for (j = 0; j < ncurr; j++) {
if (i == j)
conv[j] = 1.0;
else
scanf("%lf", &conv[j]);
}

for (i = 0; i < ncurr; i++)
for (j = 0; j < ncurr; j++)
path[j] = i;

for (k = 0; k < ncurr; k++)
for (i = 0; i < ncurr; i++)
for (j = 0; j < ncurr; j++)
if (conv[k] * conv[k][j] > conv[j]) {
conv[j] = conv[k] * conv[k][j];
path[j] = path[k][j];
}

arbitrage = false;
for (i = 0; i < ncurr; i++)
if (conv > 1.01) {
printpath(i, path[i][i]);
printf("%d\n", i + 1);
arbitrage = true;
break;
}

if (!arbitrage)
printf("no arbitrage sequence exists\n");
}

return 0;
}[/cpp]

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

### Help me

Hi.

i use Floyd Algorithm ( it's same you ), but i got WA ..

i did comparing my source and your source.

so, i found one point - scanf("%d", &n) , while( scanf("%d", &ncurr) == 1) ...

i didn't use the while loop.

i tried to use while loop, then i got Runtime Error . it's same you.

plz help me if you solve the problem or got hints.

this time is 5:34 AM , KOREA.

too sleep...

sorry at poor english.

thanks

Alansoft
New poster
Posts: 5
Joined: Mon Feb 03, 2003 11:31 pm
Location: Brazil
Contact:

### P104 - Can't understand the logic

Hello!

I have read the problem 104 but can't understand what's the table logics.

In this sample input:

Code: Select all

``````3
1.2  .89
.88  5.1
1.1  0.15
``````
Now with the diagonal:

Code: Select all

``````3
1.0   1.2   .89
.88   1.0   5.1
1.1   0.15  1.0
``````
The output must be: 1 2 1
But I can't understand where it comes from. What's the multiplication sequence!?

Thanks.
[]'s

Alan

cplusplus
New poster
Posts: 13
Joined: Fri Feb 07, 2003 10:20 pm
[quote="R

Alansoft
New poster
Posts: 5
Joined: Mon Feb 03, 2003 11:31 pm
Location: Brazil
Contact:

### Nobody!?

Hello.

As I see nobody understood the logic too! Or I didn't explained well... Please help me! []'s

Alan

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Well, I'll give it a try:
The sequence 1 2 1 means: start with currency, convert it to currency and convert it back to currency. For every conversion currency[a] to currency there is a certain rate, which can be found in the matrix at row a, column b. So in converting 1.00 unit of currency, you get 1.00 * rate[1,2] = 1.00*1.2 = 1.20 unit of currency. If you convert 1.20 unit of currency to currency, you get 1.20 * rate[2,1] = 1.20*0.88 = 1.056 unit of currency. You made a profit of 0.056, which is 5.6%!
Since the number of currencies is 3, you are only allowed a total of 2 conversions, while you have to end in the currency you started from. There are 6 possible sequences (1 2 1, 1 3 1, 2 1 2, 2 3 2, 3 1 3 and 3 2 3) for which 1 2 1 turns out to give a profit of 5.6%. Since this is more than 1%, you can output that sequence as the answer.
To get the profit of any sequence a b c ...z a, you can multiply the rates (matrix elements): rate[a,b]*rate[b,c]*...*rate[z,a].
In fact you can output any sequence, as long as the outcome of the multiplication is higher than 1.01 and the number of conversions is less than the number of currencies. There is a yellow checkmark in front of the problem, which means that more than one answer will be acceptible. In fact, for the given matrix the sequence 2 1 2 gives the same profit and is an equally valid answer.

Hope it helps,
-little joey

Alansoft
New poster
Posts: 5
Joined: Mon Feb 03, 2003 11:31 pm
Location: Brazil
Contact:

### Very good!

Hey Little Joey, thanks a lot!

That 1 2 1 = [1,2] * [2,1] tip is very good...

Intersting, in the 2nd example, the answer 1 2 4 1 gives 5217.833% Best regards,
[]'s

Alan

Alansoft
New poster
Posts: 5
Joined: Mon Feb 03, 2003 11:31 pm
Location: Brazil
Contact:

### Also right....

1 2 3 1 seems to be a valid solution... The yellow V icon located at left side of the problem description in the Vol I says that it have a special correction program... So more than one right answer might exists to one input table.
[]'s

Alan

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

I use DFS,I don't know where's the bug in my code
can someone help me if you have time,thank you very much..^^

Code: Select all

``````[cpp]#include <iostream.h>
#include <stdio.h>

int intMinN,intN;
double Data;
int intOK;
double MaxSum;
int Ans;

void visit (int In,int In2,int times,double sum,int intAns[])
{
int intT;
intAns[times]=In;

if (times<intMinN && (sum*Data[In][In2])>1.01)
{
MaxSum=sum*Data[In][In2];
intMinN=times;
for (intT=0 ;intT<=times ;intT++)
Ans[intT]=intAns[intT];
return;
}
else if (times>=intMinN)
return;
else
{
for (intT=1 ;intT<=intN ;intT++)
{
if (In==intT || Data[In][intT]==1)
continue;
visit (intT,In2,times+1,sum*Data[In][intT],intAns);
}
}
}

int main()
{
int intT,intT2;
int intAns;

freopen ("104in.txt","r",stdin);

while (cin >> intN)
{
intMinN=intN-1;
MaxSum=0;
intOK=0;

for (intT=1 ;intT<=intN ;intT++)
{
for (intT2=1 ;intT2<=intN ;intT2++)
{
if (intT==intT2)
{
Data[intT][intT2]=1;
continue;
}
cin >> Data[intT][intT2];
}
}

for (intT=1 ;intT<=intN ;intT++)
visit (intT,intT,0,1,intAns);

if (MaxSum==0)
cout << "no arbitrage sequence exists" << endl;
else
{
for (intT=0 ;intT<=intMinN ;intT++)
cout << Ans[intT] << " ";
cout << Ans << endl;
}
}
return 0;
}[/cpp]``````
Tanks again!!

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
try this

Code: Select all

``````4
1.0 1.0 1.0
1.007 1.0 1.0
1.0 1.0 1.0
1.0 1.0 1.0``````
output should be

Code: Select all

``1 2 1 2 1``
ps. a strange thing; my code with `double' produced wa and same code with `float' got me ac! (i used dp)
Istiaque Ahmed [the LA-Z-BOy]

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

### 104 Arbitrage

Hello. I didn't get the problem.
What do I have to find in this problem? Please explain if you can.

Thank you.
_____________
NO sigNature