Page 4 of 15
104 Arbitrage ??
Posted: Fri Dec 20, 2002 5:12 pm
by hank
(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?
Posted: Fri Dec 20, 2002 6:37 pm
by titid_gede
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]
Posted: Wed Jan 15, 2003 4:38 pm
by R
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.
any comments?
#104 - Arbitrage (Runtime Error: Invalid memory access)
Posted: Mon Jan 20, 2003 5:50 pm
by ec3_limz
[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]
Help me
Posted: Fri Jan 24, 2003 10:37 pm
by Gaolious
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
P104 - Can't understand the logic
Posted: Mon Feb 03, 2003 11:49 pm
by Alansoft
Hello!
I have read the problem 104 but can't understand what's the table logics.
In this sample input:
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!?
Help me, please!
Thanks.
Posted: Fri Feb 07, 2003 10:42 pm
by cplusplus
[quote="R
Nobody!?
Posted: Sun Feb 09, 2003 1:30 am
by Alansoft
Hello.
As I see nobody understood the logic too!
Or I didn't explained well... Please help me!
Thanks in advance.
Posted: Sun Feb 09, 2003 2:08 am
by little joey
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
Very good!
Posted: Sun Feb 09, 2003 2:37 am
by Alansoft
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,
Also right....
Posted: Sun Feb 09, 2003 2:44 am
by Alansoft
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.
104 Wrong Answer
Posted: Sat Mar 15, 2003 5:08 pm
by de
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[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=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[0] << endl;
}
}
return 0;
}[/cpp]
Tanks again!!
Posted: Fri Apr 25, 2003 11:07 am
by the LA-Z-BOy
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
ps. a strange thing; my code with `double' produced wa and same code with `float' got me ac! (i used dp)
104 Arbitrage
Posted: Wed Apr 30, 2003 7:39 pm
by Farid Ahmadov
Hello. I didn't get the problem.
What do I have to find in this problem? Please explain if you can.
Thank you.
Posted: Wed Apr 30, 2003 9:26 pm
by Farid Ahmadov
OK. I read it very careful and understood it. But now the problem is TLE. I use DFS and get TLE. Please give some I/O.