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

Post Reply
titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

i dont think the problem is in the input / output. Brute force always leads to 2 replies : Accepted and Time limit exceeded. if you got time limit exceeded you have to change your algorithm. try to use such a DP algo for this problem.
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

i dont think the problem is in the input / output. Brute force always leads to 2 replies : Accepted and Time limit exceeded. if you got time limit exceeded you have to change your algorithm. try to use such a DP algo for this problem.
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

i dont think the problem is in the input / output. Brute force always leads to 2 replies : Accepted and Time limit exceeded. if you got time limit exceeded you have to change your algorithm. try to use such a DP algo for this problem.
Kalo mau kaya, buat apa sekolah?

Diskerr
New poster
Posts: 16
Joined: Sun Apr 06, 2003 8:43 am
Location: Korea, Republic of

DFS..

Post by Diskerr »

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)
Sorry for my poor English.

Towhid
New poster
Posts: 38
Joined: Wed May 28, 2003 5:30 pm
Location: Bangladesh
Contact:

prob 104

Post by Towhid »

why 1 2 3 1 is not an output for sample inp 2
From 0 to 0

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

1 2 3 1 is a true output too.

yellow mark mean there are more than 1 true output.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

104

Post by Experimenter »

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?
it would be great if you replied this post. really.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

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

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wrocław

special test cases

Post by Rav »

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

actually i havent solved this problem yet. but i heard something from my friend, if there are several shortest possible answers, choose one with biggest profit. hope it can help.
Kalo mau kaya, buat apa sekolah?

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wrocław

Post by Rav »

HI
but there is a special correction program for this problem (yellow colour). I repeat my beg : could somebody gives some inputs ??
thanks

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

You can look at this problem as a graph problem (shortest path), and use DP/Floyd-Warshall...

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wrocław

Post by Rav »

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]
Last edited by Rav on Wed Jul 23, 2003 7:26 am, edited 2 times in total.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

plz use cpp tag

ytz
New poster
Posts: 5
Joined: Tue Jul 22, 2003 4:31 pm

I don't think all source shortest path can work.

Post by ytz »

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.

Post Reply

Return to “Volume 1 (100-199)”