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

scruff
New poster
Posts: 29
Joined: Wed Dec 24, 2003 5:22 am

Post by scruff »

Did your program pass all of the examples given on this board? If so why not try posting your code. If not then try to get it to pass the tests given on this board. The 10 16 10 16 10 one is a good example. It is hard to create an input that can fool your program. It is easier to look at code sometimes to see the mistake.

tlucz
New poster
Posts: 6
Joined: Tue Jan 27, 2004 1:41 pm
Location: Poland/Katowice

Post by tlucz »

There is my code (it's awful)

[cpp]#include <iostream>
#include <math.h>

using namespace std;

int ile_walut;
long double tabela [21][21];
long double tabela2[21][21];
int ile_zmian[21][21];
int ile_zmian2[21][21];
long double bylo,nowe;
int ile_bylo,ile_nowe;
int ciag[23][23][23];
int ciag2[23][23][23];

int main(void){
int i,j,k,m,a,b,n,licz;
licz=0;
while (cin >> ile_walut) {
licz++;
if (licz>1) cout << endl;
for(i=1;i<=ile_walut;i++)
for(j=1;j<=ile_walut;j++) {
ile_zmian[j]=1;
ile_zmian2[j]=1;
ciag[j][1]=i;
ciag[j][2]=j;
ciag2[j][1]=i;
ciag2[j][2]=j;
if (i!=j) {
cin >> tabela[j];
tabela2[j]=tabela[j];
}
else {
tabela[j]=1;
tabela2[i][j]=1;
}
}
for(m=2;m<=ile_walut;m++) {
for(k=1;k<=ile_walut;k++) {
for(i=1;i<=ile_walut;i++) {
for(j=1;j<=ile_walut;j++) {
bylo=tabela[i][j];
ile_bylo=ile_zmian[i][j];
nowe=tabela[i][k]*tabela[k][j];
ile_nowe=ile_zmian[i][k]+ile_zmian[k][j];
if ((nowe>bylo) && (ile_nowe<=m) && (nowe>tabela2[i][j])) {
tabela2[i][j]=nowe;
ile_zmian2[i][j]=ile_nowe;
a=ile_zmian[i][k];
b=ile_zmian[k][j];

for(n=1;n<=a+1;n++) {
ciag2[i][j][n]=ciag[i][k][n];
}
for(n=2;n<=b+1;n++) {
ciag2[i][j][a+n]=ciag[k][j][n];
}
}
}
}
}
for(i=1;i<=ile_walut;i++) {
if (tabela2[i][i]>1.01) {
for(j=1;j<=ile_zmian2[i][i]+1;j++) {
cout << ciag2[i][i][j];
if (j!=ile_zmian2[i][i]+1) cout << " ";
}
goto koniec;
}
}
for(i=1;i<=ile_walut;i++) {
for(j=1;j<=ile_walut;j++) {
for(n=1;n<=ile_zmian2[i][j]+1;n++) {
ciag[i][j][n]=ciag2[i][j][n];
}
tabela[i][j]=tabela2[i][j];
ile_zmian[i][j]=ile_zmian2[i][j];
}
}
}

cout << "no arbitrage sequence exists";
koniec:
i=1;
}
return 0;
}[/cpp]


It passed all board's and generator's tests. I think i must consider this problem once again. Thanks for your help.

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw

104 - Arbitrage (allways WA)

Post by Rav »

plz help :). i created quite complicated algorithm for this problem. its works in O(n^4). im sure its good, but i got WA. i was trying change floating size (float,double,long double,long long double) but it is'nt help.
if you have some test cases plz show it (i tryed forum's cases) or show something wrong in my code:
[cpp]
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct dl {
int nr;
dl *next;
} wal[21],list[500];


struct wymiany {
int last;
float stan;
} wym[21][21];

int list_size,size,arbitrage[22],arbitrage_dl;

float arb[21][21];

void pobierz_dane()
{
int i,k;
for (i=1;i<=size;++i)
for (k=1;k<=size;++k)
{
if (k==i)
arb[k]=1;
else
cin >> arb[k];
}
arbitrage_dl=25;

}

void dodaj_do_wymian(int poz,int nr,int last,float stan)
{
if (wym[poz][nr].stan==0)
{
dl *tmp;
tmp=wal[poz].next;
wal[poz].next=&list[list_size];
list[list_size].next=tmp;
list[list_size++].nr=nr;
}
wym[poz][nr].stan=stan;
wym[poz][nr].last=last;
}

void dodaj_do_arbitrage(int koniec,int poz,int nr)
{
float arbit=wym[poz][nr].stan*arb[poz][koniec],arbit_tmp;
int ilosc_wymian=nr,i,tmp,conr;
arbit_tmp=arbit;
while ((arbit_tmp<=1.01) && (ilosc_wymian<=size))
{
arbit_tmp*=arbit;
ilosc_wymian+=nr;
}
if ((arbit_tmp>1.01) && (ilosc_wymian<=size))
{
i=0;
arbitrage[i++]=poz;
conr=nr;
tmp=wym[poz][nr].last;
while (tmp!=0)
{
arbitrage[i++]=tmp;
tmp=wym[tmp][--nr].last;
}
for (;i<ilosc_wymian;++i)
arbitrage=arbitrage[i%conr];
reverse(&arbitrage[0],&arbitrage);
arbitrage=koniec;
arbitrage_dl=ilosc_wymian;
}
}


void znajdz(int start)
{
int i,k;
dl *tmp;

list_size=0;
for (i=1;i<=size;++i)
{
wal.next=NULL;
for (k=1;k<=size;++k)
wym[k].stan=0;
}
dodaj_do_wymian(start,1,0,1);
for (i=start+1;i<=size;++i)
{
for (k=start;k<i;++k)
{
tmp=wal[k].next;
while (tmp!=NULL)
{
if ((tmp->nr+1<arbitrage_dl) && (wym[k][tmp->nr].stan*arb[k]>wym[tmp->nr+1].stan))
dodaj_do_wymian(i,tmp->nr+1,k,wym[k][tmp->nr].stan*arb[k]);
tmp=tmp->next;
}
}
tmp=wal[i].next;
while (tmp!=NULL)
{
if ((tmp->nr<arbitrage_dl) && (wym[i][tmp->nr].stan*arb[i][start]>1))
dodaj_do_arbitrage(start,i,tmp->nr);
tmp=tmp->next;
}
}
}





int main()
{
int i;
while(cin >> size)
{
pobierz_dane();
for (i=1;i<size;++i)
znajdz(i);
if (arbitrage_dl==25)
cout << "no arbitrage sequence exists\n";
else
{
for (i=0;i<=arbitrage_dl;++i)
cout << arbitrage[i] << ' ';
cout << '\n';
}
}
return 0;
}[/cpp]
Sorry for my poor english
Best Regards Rav
Rafał Sokołowski

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

1) You can't do > 1.01 comparisions for floating point numbers.. because they are inaccurate, you need to do : x - 1.01 > EPS, where EPS = 1e-6 or something

2) I don't really see the code which limits the length of an arbitrage to less than n

3) If it helps, I think I used a 3dimensional array for the DP.

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw

Post by Rav »

thx for reply.
1) i change code i now have:

[cpp]
const double EPS=1e-6;
...
while ((arbit_tmp-1.01<=EPS) && (ilosc_wymian<=size)) /*limit arbitrage lenght and do check for cycles: when 1<arbitrage<=1.01 */
{
arbit_tmp*=arbit;
ilosc_wymian+=nr;
}
if ((arbit_tmp-1.01>EPS) && (ilosc_wymian<=size)) /*limit arbitrage lenght*/
...
[/cpp]
but i have still WA in 0.207s

2)i limit arbitrage length by size

3)i am using something like 3rd demension for my DP
[cpp]struct wymiany {
int last;
double stan;
} wym[21][21]; [/cpp]
Best Regards Rav
Rafał Sokołowski

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

Sorry I don't really have time to debug your program... why don't you post some test data and I'll post my results and you can work it out from there?

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw

Post by Rav »

what reasult should be for that ??
4
1 1.01 1
1 1 1
1 1 1
1 1 1

my prog write:
1 3 1 3 1

is this right ??
Rafał Sokołowski

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin »

my program gives 3 1 3 1 3, but it should be fine either way

rubendv
New poster
Posts: 9
Joined: Mon Mar 15, 2004 10:23 pm

Clarification 104

Post by rubendv »

Must the sequence always begin with the currency of country 1, that is, the currency of the country that corresponds to the first line of the matrix?
Thanks,

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

problem

Post by sohel »

I have some problems with this question.............
........ Using Floyd Warshall will find out whethere an arbitrage sequence exists , then it is also possible to print a path of such a sequence...
.. but how do you find the one with the fewest number of exchanges.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

Using Floyd you can find maksimum profit from chain of exchanges and if you use route matrix (generated with the same time when you compute profit) you gave such chain. Observe that when profit is bigger than earlier you must update route - in other cases: no update.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

Thanks...
... but I am still a little confused.

If we get a bigger profit and update the route than number of path increases.. but If you don't update it we still might make a profit and with fewer exchanges...

.. how do you know when to update the route.
We have to look for the minimum number of exchanges... not the maximum profit.

Some more hints would be appreciated. :P

Telavian
New poster
Posts: 1
Joined: Tue Jun 22, 2004 1:03 am

Problem with 104 example data?????

Post by Telavian »

I am attempting to solve problem #104. As I ran the example data I came up with some different answers.

For the data
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111

The sample output is 1 2 4 1 which according to my understanding of the problem is (if I am wrong please tell me)
3.1 * 8.13 * 2.11 = 53.17833.
The output my program gives is 2 4 3 2 which is
8.13 * .06111 * 180.559 = 89.7061.
If my understanding of the problem is correct then my answer is better with the same number of transactions.

My program gives the same answers for the other sample data. If you could please post some additional data with verified answers and I will test with that.
Please inform as to what is correct.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel »

Yes... you are correct that your sequence produces greater profit..

.. but the problem does not ask for the highest profit... it just wants a sequence that would yield a profit of more than 1.01%..
.. so your answer is not wrong..

and since it has a yellow tick associated with it so there are multiple answers and any answer would do.

Hope it helps. :wink:

gingioerge
New poster
Posts: 4
Joined: Thu Jul 01, 2004 2:12 pm

about 104: Arbitrage

Post by gingioerge »

What about this problem?
I read something about brute force on the list, but it is unecessary.
I found a solution in O(n^4),

Somebody found solution in O(n^3)?

now I'm trying for O(n^3), but I'm sceptic...
simply, Floyd isn't enough, because we have to reduce the problem also
by path lenght, so we have to find the best path between each pair
of node for each lenght.
Given best path of lenght K between each pair of node, finding best path
between each pair of lenght K+1 takes O(n^3)...so I think isn't possible
do all the work in O(n^3)!!!

Post Reply

Return to “Volume 1 (100-199)”