OJ Board

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.

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.

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

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.

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

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?

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 ??

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

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,

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.

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

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.

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.

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.

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)!!!