104 - Arbitrage

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

104 Arbitrage ??

Post by hank » Fri Dec 20, 2002 5:12 pm

(sorry, my english is poor... :wink: )

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

Post by titid_gede » Fri Dec 20, 2002 6:37 pm

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

Post by R » Wed Jan 15, 2003 4:38 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.

any comments?

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

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

Post by ec3_limz » Mon Jan 20, 2003 5:50 pm

[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
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

Help me

Post by Gaolious » Fri Jan 24, 2003 10:37 pm

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

Post by Alansoft » Mon Feb 03, 2003 11:49 pm

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.
[]'s

Alan

cplusplus
New poster
Posts: 13
Joined: Fri Feb 07, 2003 10:20 pm

Post by cplusplus » Fri Feb 07, 2003 10:42 pm

[quote="R

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

Nobody!?

Post by Alansoft » Sun Feb 09, 2003 1:30 am

Hello.

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

Thanks in advance.
[]'s

Alan

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Feb 09, 2003 2:08 am

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
New poster
Posts: 5
Joined: Mon Feb 03, 2003 11:31 pm
Location: Brazil
Contact:

Very good!

Post by Alansoft » Sun Feb 09, 2003 2:37 am

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

Post by Alansoft » Sun Feb 09, 2003 2:44 am

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

104 Wrong Answer

Post by de » Sat Mar 15, 2003 5:08 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[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!!

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Fri Apr 25, 2003 11:07 am

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]

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

104 Arbitrage

Post by Farid Ahmadov » Wed Apr 30, 2003 7:39 pm

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

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

Post by Farid Ahmadov » Wed Apr 30, 2003 9:26 pm

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.
_____________
NO sigNature

Post Reply

Return to “Volume 1 (100-199)”