104 - Arbitrage

[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?

[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]

[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?

[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]

[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

[Alansoft]

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!?

Help me, please!

Thanks.

[cplusplus]

[quote="R

[Alansoft]

Hello.

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

Thanks in advance.

[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

[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,

[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.

[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!!

[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

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)

[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.

[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.