104  Arbitrage
Moderator: Board moderators
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?
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?

 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]
[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]
#104  Arbitrage (Runtime Error: Invalid memory access)
[cpp]/* @JUDGE_ID: 18472KP 104 C++ "All Pairs Shortest Paths" */
#include <stdio.h>
int path[20][20];
void printpath(int src, int pos) {
if (src != pos)
printpath(src, path[src][pos]);
printf("%d ", pos + 1);
}
int main() {
bool arbitrage;
double conv[20][20];
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]
#include <stdio.h>
int path[20][20];
void printpath(int src, int pos) {
if (src != pos)
printpath(src, path[src][pos]);
printf("%d ", pos + 1);
}
int main() {
bool arbitrage;
double conv[20][20];
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]

 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
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
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:
Now with the diagonal:
The output must be: 1 2 1
But I can't understand where it comes from. What's the multiplication sequence!?
Help me, please!
Thanks.
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
Code: Select all
3
1.0 1.2 .89
.88 1.0 5.1
1.1 0.15 1.0
But I can't understand where it comes from. What's the multiplication sequence!?
Help me, please!
Thanks.
[]'s
Alan
Alan
Nobody!?
Hello.
As I see nobody understood the logic too! Or I didn't explained well... Please help me!
Thanks in advance.
As I see nobody understood the logic too! Or I didn't explained well... Please help me!
Thanks in advance.
[]'s
Alan
Alan

 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[1], convert it to currency[2] and convert it back to currency[1]. 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[1], you get 1.00 * rate[1,2] = 1.00*1.2 = 1.20 unit of currency[2]. If you convert 1.20 unit of currency[2] to currency[1], you get 1.20 * rate[2,1] = 1.20*0.88 = 1.056 unit of currency[1]. 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
The sequence 1 2 1 means: start with currency[1], convert it to currency[2] and convert it back to currency[1]. 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[1], you get 1.00 * rate[1,2] = 1.00*1.2 = 1.20 unit of currency[2]. If you convert 1.20 unit of currency[2] to currency[1], you get 1.20 * rate[2,1] = 1.20*0.88 = 1.056 unit of currency[1]. 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
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,
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
Alan
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
Alan
104 Wrong Answer
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..^^
Tanks again!!
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[30][30];
int intOK;
double MaxSum;
int Ans[30];
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[30];
freopen ("104in.txt","r",stdin);
while (cin >> intN)
{
intMinN=intN1;
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[0] << endl;
}
}
return 0;
}[/cpp]

 Learning poster
 Posts: 94
 Joined: Wed Jul 31, 2002 12:44 pm
 Location: Dacca, Bangladesh
 Contact:
try this
output should be
ps. a strange thing; my code with `double' produced wa and same code with `float' got me ac! (i used dp)
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
Code: Select all
1 2 1 2 1
Istiaque Ahmed [the LAZBOy]

 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.
What do I have to find in this problem? Please explain if you can.
Thank you.
_____________
NO sigNature
NO sigNature

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