104

titid_gede · Post by **titid_gede** » Thu May 01, 2003 3:58 pm

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.

titid_gede · Post by **titid_gede** » Thu May 01, 2003 4:00 pm

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.

titid_gede · Post by **titid_gede** » Thu May 01, 2003 4:07 pm

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.

Diskerr · Post by **Diskerr** » Thu May 01, 2003 5:51 pm

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)

Towhid · Post by **Towhid** » Fri Jun 06, 2003 7:32 pm

why 1 2 3 1 is not an output for sample inp 2

Hisoka · Post by **Hisoka** » Fri Jun 06, 2003 8:29 pm

1 2 3 1 is a true output too.

yellow mark mean there are more than 1 true output.

Experimenter · Post by **Experimenter** » Sat Jul 12, 2003 5:41 pm

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?

bugzpodder · Post by **bugzpodder** » Sun Jul 13, 2003 12:17 am

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 · Post by **Rav** » Tue Jul 22, 2003 9:59 am

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 · Post by **titid_gede** » Tue Jul 22, 2003 5:12 pm

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.

Rav · Post by **Rav** » Tue Jul 22, 2003 9:53 pm

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

Larry · Post by **Larry** » Tue Jul 22, 2003 11:59 pm

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

Rav · Post by **Rav** » Wed Jul 23, 2003 12:29 am

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]

bugzpodder · Post by **bugzpodder** » Wed Jul 23, 2003 2:58 am

plz use cpp tag

ytz · Post by **ytz** » Thu Jul 24, 2003 6:10 pm

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.

OJ Board

104 - Arbitrage

DFS..

prob 104

special test cases

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