104 - Arbitrage
Moderator: Board moderators
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
DFS..
I think that this prob can't be solved by DFS.
If there are 20 nodes and 19 edges for each nodes, how can be DFS works? (It takes factorial time!)
Use DP.
I heard Floyd-Warshall(O^3) works fine for this problem.
But for me, I have no idea how it can be applicable.
So I modified Floyd-warshall, it takes O^4 but works fine.
(Actually, I also got some hints from one who solved this problem before me)
If there are 20 nodes and 19 edges for each nodes, how can be DFS works? (It takes factorial time!)
Use DP.
I heard Floyd-Warshall(O^3) works fine for this problem.
But for me, I have no idea how it can be applicable.
So I modified Floyd-warshall, it takes O^4 but works fine.
(Actually, I also got some hints from one who solved this problem before me)
Sorry for my poor English.
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
104
hi, everybody! how is it going?
I was thinking of algorithm for the given problem and it seems that the only possible way is to generate all possible permutations of k (k = 1,...,n-1) elements in ascending order (i.e. for k in ascending order) and for each permutation to check whether it is a "successful" or not. each permutation represents a sequence of exchanges. but the problem is that at the last step k equals to 19 = 20-1, what leads to 19! =121645100408832000 permutations to be checked, which is really enormous and obviously will cause TLE. I really cannot think of any other way of solving the problem.
could anyone give me a hint how to solve the problem?
I was thinking of algorithm for the given problem and it seems that the only possible way is to generate all possible permutations of k (k = 1,...,n-1) elements in ascending order (i.e. for k in ascending order) and for each permutation to check whether it is a "successful" or not. each permutation represents a sequence of exchanges. but the problem is that at the last step k equals to 19 = 20-1, what leads to 19! =121645100408832000 permutations to be checked, which is really enormous and obviously will cause TLE. I really cannot think of any other way of solving the problem.
could anyone give me a hint how to solve the problem?
it would be great if you replied this post. really.
-
- Experienced poster
- Posts: 147
- Joined: Fri Jun 13, 2003 10:46 pm
my DP solution takes O(n^3) time. i dont have my code with me so there maybe some mistakes. in any case, bear with me.
since any legal sequence would work, you basically loop through all starting currencies. for each starting currency, compute all the data resulting from one exchange if you have say $1 of the starting currency. now each of these exchanges, compute the next set of exchanges (that is the equilvalent of the amount of money you can with $1 starting currency get after two exchanges), but greedily only take the maximum. then check for each, if you can get more than 1.01 or more of the starting currency (1%)
good luck
since any legal sequence would work, you basically loop through all starting currencies. for each starting currency, compute all the data resulting from one exchange if you have say $1 of the starting currency. now each of these exchanges, compute the next set of exchanges (that is the equilvalent of the amount of money you can with $1 starting currency get after two exchanges), but greedily only take the maximum. then check for each, if you can get more than 1.01 or more of the starting currency (1%)
good luck
special test cases
hi
could somebody tells more test cases , beacuse my prog get WA after 5.4 seconds. i using DP and pass all test cases. please help.
Rav
could somebody tells more test cases , beacuse my prog get WA after 5.4 seconds. i using DP and pass all test cases. please help.
Rav
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
i dont know Floyd-Warshalll argorithm but i use DP here i my code. it works on test input and on my inputs but i dont know where is error. judge gives WA. please help.
if somebody could test it on case or tell my where is bug or tricky input. i be very glad. Rafał Sokołowski.
[cpp]
#include<stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <iostream>
using namespace std;
double tab[20][20],zapas[20][20],profit;
int koniec,rozmiar,ilosc,arb[22],minilosc=22,tmp[22];
int sprawdz(int,int,double);
void pobierz_tablice();
void popraw(int);
void wypisz1(int);
void wypisz2(int);
void pobierz_tablice ()
{
int wsk_poz,wsk_pion;
for (wsk_poz=0;wsk_poz<rozmiar;++wsk_poz)
for (wsk_pion=0;wsk_pion<rozmiar;++wsk_pion)
{
if (wsk_pion!=wsk_poz)
cin >> tab[wsk_poz][wsk_pion];
else
tab[wsk_poz][wsk_pion]=1.0;
}
}
void popraw (int r1)
{
int wsk_poz,wsk_pion,id,wsk;
double max;
for (wsk_poz=r1-1;wsk_poz<rozmiar;++wsk_poz)
zapas[r1-1][wsk_poz]=tab[r1-1][wsk_poz];
for (wsk_poz=r1;wsk_poz<rozmiar;++wsk_poz)
{
for (id=r1-1,max=0.0;id<wsk_poz;++id)
if (zapas[id][wsk_poz]>max)
max=zapas[id][wsk_poz];
for (wsk_pion=r1-1;wsk_pion<rozmiar;++wsk_pion)
{
if (wsk_pion!=wsk_poz)
zapas[wsk_poz][wsk_pion]=tab[wsk_poz][wsk_pion]*max;
else
zapas[wsk_poz][wsk_pion]=tab[wsk_poz][wsk_pion];
}
if (zapas[wsk_poz][r1-1]>1.0)
{
koniec=wsk_poz;
sprawdz (0,r1-1,tab[wsk_poz][r1-1]);
}
}
}
int sprawdz (int il,int poziom,double maxi)
{
int pt,wsk_poz,wsk_pion,wsk,tk;
double kupa;
tmp[il]=poziom;
if ((poziom==koniec) && (maxi>1.01))
{
if ((minilosc>il) || ((minilosc==il) && (maxi>profit)))
{
profit=maxi;
minilosc=il;
for (wsk=0;wsk<=il;++wsk)
arb[wsk]=tmp[wsk];
arb[wsk]=arb[0];
}
}
else if ((poziom==koniec) && (maxi>1.0))
{
++il;
wsk=1;
tk=il;
kupa=maxi;
while ((maxi<=1.1) && (il<=rozmiar))
{
++wsk;
il+=tk;
maxi*=maxi;
}
--wsk;
il-=tk;
if (((il-1<=rozmiar) && (il<=minilosc)) || ((il-1<=rozmiar) && (il-1<=minilosc) && (maxi>profit)))
{
profit=maxi;
minilosc=il-1;
for (il=0;il<wsk;++il)
for (pt=0;pt<tk;++pt)
arb[tk*il+pt]=tmp[pt];
arb[wsk*tk]=arb[0];
}
il=tk;
--il;
maxi=kupa;
}
++il;
for (wsk_pion=koniec;wsk_pion>poziom;--wsk_pion)
sprawdz(il,wsk_pion,maxi*tab[poziom][wsk_pion]);
}
int main()
{
int wsk;
#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif
while (cin >> rozmiar)
{
minilosc=22;
pobierz_tablice ();
profit=0.0;
for (wsk=1;wsk<rozmiar;++wsk)
popraw (wsk);
if (minilosc!=22)
{
for (wsk=0;wsk<=minilosc+1;++wsk)
cout << arb[wsk]+1 << ' ';
cout << '\n';
}
else
cout << "no arbitrage sequence exists\n";
}
}
[/cpp]
if somebody could test it on case or tell my where is bug or tricky input. i be very glad. Rafał Sokołowski.
[cpp]
#include<stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <iostream>
using namespace std;
double tab[20][20],zapas[20][20],profit;
int koniec,rozmiar,ilosc,arb[22],minilosc=22,tmp[22];
int sprawdz(int,int,double);
void pobierz_tablice();
void popraw(int);
void wypisz1(int);
void wypisz2(int);
void pobierz_tablice ()
{
int wsk_poz,wsk_pion;
for (wsk_poz=0;wsk_poz<rozmiar;++wsk_poz)
for (wsk_pion=0;wsk_pion<rozmiar;++wsk_pion)
{
if (wsk_pion!=wsk_poz)
cin >> tab[wsk_poz][wsk_pion];
else
tab[wsk_poz][wsk_pion]=1.0;
}
}
void popraw (int r1)
{
int wsk_poz,wsk_pion,id,wsk;
double max;
for (wsk_poz=r1-1;wsk_poz<rozmiar;++wsk_poz)
zapas[r1-1][wsk_poz]=tab[r1-1][wsk_poz];
for (wsk_poz=r1;wsk_poz<rozmiar;++wsk_poz)
{
for (id=r1-1,max=0.0;id<wsk_poz;++id)
if (zapas[id][wsk_poz]>max)
max=zapas[id][wsk_poz];
for (wsk_pion=r1-1;wsk_pion<rozmiar;++wsk_pion)
{
if (wsk_pion!=wsk_poz)
zapas[wsk_poz][wsk_pion]=tab[wsk_poz][wsk_pion]*max;
else
zapas[wsk_poz][wsk_pion]=tab[wsk_poz][wsk_pion];
}
if (zapas[wsk_poz][r1-1]>1.0)
{
koniec=wsk_poz;
sprawdz (0,r1-1,tab[wsk_poz][r1-1]);
}
}
}
int sprawdz (int il,int poziom,double maxi)
{
int pt,wsk_poz,wsk_pion,wsk,tk;
double kupa;
tmp[il]=poziom;
if ((poziom==koniec) && (maxi>1.01))
{
if ((minilosc>il) || ((minilosc==il) && (maxi>profit)))
{
profit=maxi;
minilosc=il;
for (wsk=0;wsk<=il;++wsk)
arb[wsk]=tmp[wsk];
arb[wsk]=arb[0];
}
}
else if ((poziom==koniec) && (maxi>1.0))
{
++il;
wsk=1;
tk=il;
kupa=maxi;
while ((maxi<=1.1) && (il<=rozmiar))
{
++wsk;
il+=tk;
maxi*=maxi;
}
--wsk;
il-=tk;
if (((il-1<=rozmiar) && (il<=minilosc)) || ((il-1<=rozmiar) && (il-1<=minilosc) && (maxi>profit)))
{
profit=maxi;
minilosc=il-1;
for (il=0;il<wsk;++il)
for (pt=0;pt<tk;++pt)
arb[tk*il+pt]=tmp[pt];
arb[wsk*tk]=arb[0];
}
il=tk;
--il;
maxi=kupa;
}
++il;
for (wsk_pion=koniec;wsk_pion>poziom;--wsk_pion)
sprawdz(il,wsk_pion,maxi*tab[poziom][wsk_pion]);
}
int main()
{
int wsk;
#ifndef ONLINE_JUDGE
close (0); open ("myprog.in", O_RDONLY);
close (1); open ("myprog.out", O_WRONLY | O_CREAT, 0600);
#endif
while (cin >> rozmiar)
{
minilosc=22;
pobierz_tablice ();
profit=0.0;
for (wsk=1;wsk<rozmiar;++wsk)
popraw (wsk);
if (minilosc!=22)
{
for (wsk=0;wsk<=minilosc+1;++wsk)
cout << arb[wsk]+1 << ' ';
cout << '\n';
}
else
cout << "no arbitrage sequence exists\n";
}
}
[/cpp]
Last edited by Rav on Wed Jul 23, 2003 7:26 am, edited 2 times in total.
I don't think all source shortest path can work.
My idea:
The problem is the intertwine of two factors: "shortest path" and "profit".
if a->b->c->a yield 1.5 and a->d->a yield 1.4, all source shortest path will give the first one because it yields more. However according to the problem the later should be the answer.
All source shortest path is infact a dynamic programming solution, which I didn't think apply to this problem. THe reason is there's no partial solution. At the time you determine a partial solution, for example the path from i to j (i!=j), if you base your update decision on the yeild, you'll make the error discussed above. If you choose to keep the partial solution that have the shortest path, you didn't know whether it will yield profit in the end. Thus you can't determine a partial solution on its own.
I guess the only way to solve this problem is using brutal force.
The problem is the intertwine of two factors: "shortest path" and "profit".
if a->b->c->a yield 1.5 and a->d->a yield 1.4, all source shortest path will give the first one because it yields more. However according to the problem the later should be the answer.
All source shortest path is infact a dynamic programming solution, which I didn't think apply to this problem. THe reason is there's no partial solution. At the time you determine a partial solution, for example the path from i to j (i!=j), if you base your update decision on the yeild, you'll make the error discussed above. If you choose to keep the partial solution that have the shortest path, you didn't know whether it will yield profit in the end. Thus you can't determine a partial solution on its own.
I guess the only way to solve this problem is using brutal force.