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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Prob 104 Why I get WA? Please, help me!!!

Post by Revenger »

Please, help me to find where my program wrong :( I tested it many times but without any results

(* Arbitrage *)

[pascal]Program p104 (input, output);

Const MaxN = 20;

Type PathMas = array[1..2*MaxN]of integer;

Var Exc : array[1..MaxN,1..MaxN]of extended;
Best : array[1..MaxN]of record Value : single; Pred,Len : Integer;K : PathMas; end;
Path : array[1..MaxN,0..MaxN]of Integer;
Use : array[1..MaxN]of integer;
N,i,j,k : Integer;
ok,p : Integer;

begin
while not eof(input) do begin
Read(Input,N);
for i:=1 to N do
for j:=1 to N do if i<>j then
Read(Input,Exc[i,j]);

for k:=1 to N do begin

ok:=0; Path[k,0]:=-1;
for i:=1 to N do Best.Value:=0;
Best[k].Value:=1000;
Best[k].K[1]:=k;
Best[k].Len:=1;
for p:=1 to N do
for i:=1 to N do begin
for j:=1 to N do if i<>j then
if Best.Value*Exc[i,j]>Best[j].Value then begin
Best[j].Value:=Best.Value*Exc[i,j];
Best[j].Pred:=i;
Best[j].K:=Best.K;
Best[j].Len:=Best.Len+1;
Best[j].K[Best[j].Len]:=j;
if j=k then
if Best[k].Value>1010.000000001 then begin
ok:=1;
break;
end;
end;
if ok=1 then break;
end;
if Best[k].Len>N then ok:=0;
if ok=1 then begin
for j:=1 to N do Path[k,j]:=Best[k].K[j];
Path[k,0]:=Best[k].Len;
end;
end;

j:=100;
for i:=1 to N do
if Path[i,0]<>-1 then
if Path[i,0]<j then j:=Path[i,0];
if j=100 then writeln(Output,'no arbitrage sequence exists') else begin
for i:=1 to N do
if Path[i,0]=j then begin
j:=i;
break;
end;
for i:=1 to Path[j,0]-1 do Write(Output,Path[j,i]:0,' ');
Writeln(Output,Path[j,Path[j,0]]:0);
end;

end;
end.[/pascal]

[Edited by fpnc to improve visibility via pascal BBCode]

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 »

Sorry, I do not understand. How do you accomplish 3D Floyd-Warshall with a 2D matrix? Please enlighten me to your technique.

vectra14
New poster
Posts: 1
Joined: Mon Apr 22, 2002 4:11 am
Contact:

Post by vectra14 »

Caffeine, could you possibly provide a link to a site about this 3d implementation of Floyd Warshall? :)

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 »

Basically, make a 3d array: FWT[x][y]

For each i, let FWT be the shortest distance between x and y using at most i steps. Use DP to build from the bottom up. And then you should be able to look up the queries.

Daekar
New poster
Posts: 1
Joined: Thu Jun 20, 2002 6:20 am

104 - Arbitrage

Post by Daekar »

I cannot figure out what is wrong with this code. It works perfectly with the given examples, however it gets always "Wrong Answer" from the server. This problem started when I have introduced the "OK" variable, because it was exceding the time limit . Please, I need some help. Thank you.

import java.io.*;
import java.util.*;

class Main
{
static double[][] tabela;
static int[] seq;
static int tam, cont;
static boolean[] jah;
static boolean volta, ok;

static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main (String[] args)
{
String entrada, retorno;
StringTokenizer token;

while((entrada = Main.ReadLn(255)) != null)
{
token = new StringTokenizer(entrada);
tam = Integer.parseInt(token.nextToken());
tabela = new double[tam][tam];
jah = new boolean[tam];
volta = false;
seq = new int[tam + 1];
cont = 0;
retorno = "";

for(int i = 0; i < tam; i = i + 1)
{
token = new StringTokenizer(entrada = ReadLn(255));
for(int j = 0; j < tam; j = j + 1)
{
if(i != j)
tabela[j] = Main.parseDouble(token.nextToken());
else
tabela[j] = 1;
}
}

for(int i = 2; i <= tam; i = i + 1)
{
for (int j = 0; j < tam; j = j + 1)
if (!volta)
{
if(!jah[j])
Main.arbitrage(j, i);
}
else
break;

if(volta)
break;
}

for(int i = 0; i <= tam; i = i + 1)
if(seq != 0)
retorno = retorno + seq + " ";
else
break;
if(retorno.equals(""))
retorno = "no arbitrage sequence exists";
System.out.println(retorno);
}
}

public static void arbitrage(int j, int i)
{
if(i == 0)
{
double temp = 1;
seq[cont] = seq[0];
for (int k = 0; k < tam; k = k + 1)
{
int s1 = seq[k] - 1;
int s2 = seq[k + 1] - 1;
if(s1 >= 0 && s2 >= 0)
temp = temp * tabela[s1][s2];
else
break;
}
volta = ((temp - 1) > 0.01);
if(!volta)
{
seq[cont] = 0;
ok = true;
}
else
return;
}

if(jah[j])
return;

if(i > 0)
{
seq[cont] = j + 1;
cont = cont + 1;
jah[j] = true;
i = i - 1;
for (int k = 0; k < tam; k = k + 1)
if(!volta && !ok)
Main.arbitrage(k, i);
else
{
ok = false;
break;
}
if(!volta)
{
cont = cont - 1;
seq[cont] = 0;
jah[j] = false;
}
}
}

public static double parseDouble(String t)
{
int temp = t.indexOf('.');
if(temp == -1)
return Integer.parseInt(t);

String a = t.substring(0, temp);
int x = 0;
if(!a.equals(""))
x = Integer.parseInt(a);

a = t.substring((temp + 1), t.length());
int z = 0;
if(!a.equals(""))
z = Integer.parseInt(a);

temp = 1;
for(int i = 0; i < a.length(); i = i + 1)
temp = temp * 10;
x = temp * x + z;
return (((double) x) / temp);
}

}

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

104 You are wrong

Post by Revenger »

I think that your algorithm is wrong. I just wonder how you write this program without any arrays! I have O(n^3) algorithm. Try to think about this.

Pokemonster
New poster
Posts: 10
Joined: Mon Jul 01, 2002 11:15 pm
Location: Germany

Input in problem 104

Post by Pokemonster »

Just wondering if I understand the input correct.
The resulting table for an input like

3.1___0.0023___0.35
0.21__0.00353__8.13
200___180.559_10.339
2.11__0.089____0.06111

is

1.0___3.1_____0.0023___0.35
0.21__1.0_____0.00353__8.13
200__180.559__1.0_____10.339
2.11__0.089___0.06111__1.0

right ?

cause when calculating the sample sequence (1 2 4 1)
the arbitrage is about 5300% !!!
(1 x 3.1 x 8.13 x 2.11)

Infos appreciated :-)

ALex

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN »

Yes, you are right~

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

Word "Diagnal" says it out!

Post by 1_UtterBlue »

Word "Diagnal" says all out!
James.Hao (Bonjour!)

1_UtterBlue
New poster
Posts: 12
Joined: Sun Mar 10, 2002 2:00 am
Location: China
Contact:

Post by 1_UtterBlue »

Could anyone of you give me the idea how to solve P104 with Dynamic Programming? I got totally no IDEA! Please help! :roll:
James.Hao (Bonjour!)

Sasko
New poster
Posts: 3
Joined: Tue Sep 03, 2002 3:31 am

p104

Post by Sasko »

My program have solutions for the test casesin in the p104 and also for some like 10 16 10 16 10 (k cycled). The program is in O^3 complexity.
But I am geting Time limit exided.
If someone can tell me what I am missing????

Thanks

Haomiao
New poster
Posts: 5
Joined: Sat Nov 16, 2002 11:28 am
Location: Xi'an,China
Contact:

something about 104...dynamic progamming?

Post by Haomiao »

who can prove the dynamic programming accuracy...

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 use Floyd-Warshall to find a negative cycle.

peterlin
New poster
Posts: 5
Joined: Wed Dec 18, 2002 4:46 pm

Is ACM - 104 exist a O(n^3) algo ?

Post by peterlin »

I have heard about...
I am very curious is it really exist ?
If it exist...Can someone simply explain it how to work ?

Best wishes,
Peter

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 model this as a graph problem, in particular, finding a negative cost cycle in a graph. This can be solved in O(n^3) using a modified Floyd-Warshall algorithm (and some Dynamic Programming knowledge).

Post Reply

Return to “Volume 1 (100-199)”