OJ Board

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.

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.

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.

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)

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

1 2 3 1 is a true output too.

yellow mark mean there are more than 1 true output.

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?

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

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

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.

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

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

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]

plz use cpp tag

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.