## 104 - Arbitrage

Moderator: Board moderators

New poster
Posts: 3
Joined: Sat Aug 02, 2008 11:37 am

### Re: 104 Memory Limit Exceeded

i am solving it brute force using binary numbers by a loop till 1<<n (1^20=1048576) so it doesn't take so much time...here is my code check it please

Code: Select all

``````#include<iostream.h>

int main()
{
int flag,s,i,j,t,n,seq[22],finseq[22],maxx,l,f,k;
double mult,table[21][21];
while(cin>>n)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i==j)
table[i][j]=1.0;
else
cin>>table[i][j];

finseq[0]=-1;
maxx=60;
for(i=3;i<(1<<n);i++)
{
t=i; s=0; mult=1.0; l=-1; f=-1; k=0; flag=0;
while(t!=0)
{
if(t%2==1)
{
if(l==-1)
f=s;

seq[s]=s;

if(l!=-1)
mult*=table[seq[l]][seq[s]];

l=s;
k++;
if(k>=maxx)
{ flag=1; break; }
}
else
seq[s]=-1;
t/=2;
s++;
}
if(flag==1)
continue;
mult*=table[seq[l]][seq[f]];
seq[s]=seq[f];

s++;
if(mult>1.01)
if(k<maxx)
{
maxx=k; t=0;
for(j=0;j<s;j++)
if(seq[j]!=-1)
{ finseq[t]=seq[j]; t++; }
if(maxx==2)
break;
}
}
if(finseq[0]==-1)
cout<<"no arbitrage sequence exists"<<endl;
else
for(j=0;j<=maxx;j++)
if(j==maxx)
cout<<finseq[j]+1<<endl;
else
cout<<finseq[j]+1<<" ";
}
}
``````

New poster
Posts: 3
Joined: Sat Aug 02, 2008 11:37 am

### Re: 104...I give up

hey
i didn't know how to solve the problem using floyd warshall but when i saw your code i undersanded it but i want to know how to do it O(n^3), do you know how ???

iit2006015
New poster
Posts: 4
Joined: Fri Jul 18, 2008 9:44 pm

### Using DFS for the given problem

Using dfs , i m getting a TLE.Can anybody explain how can i use memorization in this to get rid of TLE !!!!!!!

// using the dfs
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<string>
#define pi 2acos(0);
#define MAX 1000001
using namespace std;
string i2s(int n)
{ stringstream ss;
ss<<n;
return ss.str();
}
int s2i(string h)
{ stringstream ss;
ss<<h;
int n;
ss>>n;
return n;
}
vector< vector<int> > res;
void dfs(int i,vector<int> seq,double price,int n,vector< vector<double> > re)
{ if(seq.size()>n)
{ return ;
}
for(int j=0;j<re.size();j++)
{ if(i!=j)
{ vector<int> seq1;seq1.clear();
for(int i1=0;i1<seq.size();i1++)
{ seq1.push_back(seq[i1]);
}
seq1.push_back(j);
double price1=(double)price * (double)re[j];
if(j==seq1[0] && price1>1.01)
{ res.push_back(seq1);
}
else
{ dfs(j,seq1,price1,n,re);
}
}
}
}
int main()
{ int n;
while(scanf("%d",&n)==1)
{ res.clear();
vector< vector<double> > re;re.clear();
vector< vector<double> > re1;re1.clear();
for(int i=0;i<n;i++)
{ vector<double> re2;re2.clear();
for(int j=0;j<n-1;j++)
{ double num;//cin>>num;
scanf("%lf",&num);
re2.push_back(num);
}
re1.push_back(re2);
}
for(int i=0;i<re1.size();i++)
{ vector<double> re2;re2.clear();
for(int j=0;j<i;j++)
{ re2.push_back(re1[j]);
}
re2.push_back(1.0);
for(int j=i;j<re1.size();j++)
{ re2.push_back(re1[j]);
}
re.push_back(re2);
}
// now the sequence is ready and we need to implement the dfs
for(int i=0;i<re.size();i++)
{ for(int j=0;j<re.size();j++)
{ if(i!=j)
{ vector<int> seq;seq.clear();
seq.push_back(i);seq.push_back(j);
double price=(double)re[j];
dfs(j,seq,price,n,re);
}
}
}
int index=0;
int min1=res[0].size();
for(int j=1;j<res.size();j++)
{ if(res[j].size()<min1)
{ index=j;
min1=res[j].size();
}
}
if(res.size()==0)
{ printf("no arbitrage sequence exists\n");
}
else
{ //cout<<(res[index][0]+1);
printf("%d",res[index][0]+1);
for(int j=1;j<res[index].size();j++)
{ //cout<<" "<<(res[index][j]+1);
printf(" %d",res[index][j]+1);
}
//cout<<endl;
printf("\n");
}
}
system("pause");
}

uday
New poster
Posts: 1
Joined: Thu Jul 30, 2009 7:35 am

### Runtime Error

I am constantly getting runtime error...can someone pls let me know what is it that i am doing wrong..ive tried most test cases on the forum and they are giving expected results....thanks for any help:-

Code: Select all

``````#include<cstdio>
#include<vector>
#include<string>
#include<iostream>
#include<sstream>
using namespace std;
int main()
{ int n;
outer: while((cin>>n)!=0)
{

/*   if(ret==EOF)
break;*/
vector<vector<double> > input(n,vector<double> (n));
int i=0,j=0,k=0,l=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j) { input[i][j]=1; continue;}
scanf("%lf",&input[i][j]);
}
}
vector< vector<double> > value(n,vector<double>(n));
vector<vector<double> >  tmp(n,vector<double>(n));
vector< vector<string> >  list(n,vector<string>(n));
vector< vector<string> >  tmp_list(n,vector<string>(n));
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
value[i][j]=input[i][j];
char* str;
int len=sprintf(str,"%d %d\n",i+1,j+1);
//cout<<str<<"\n";
list[i][j]=string(str,len);
//cout<<list[i][j]<<"\n";
}
}
//system("pause");

bool flag=false;
string ans("");
double max=0;
double out_max=0;
for(i=1;i<n;i++)
{

for(j=0;j<n;j++)
{
flag=false;
for(k=0;k<n;k++)
{

max=0;
string newList;
for(l=0;l<n;l++)
{
if(j==l) continue;
if(input[j][l]*value[l][k]>max)
{
max=input[j][l]*value[l][k];
newList=list[l][k];
}
}

tmp[j][k]=max;
stringstream out; out<<(j+1);
string str_temp=out.str();
str_temp+=" ";
str_temp += newList;

tmp_list[j][k]=string(str_temp);
if(tmp[j][k]>1.01 && j==k)
{
if(!flag) {ans=tmp_list[j][k]; out_max=tmp[j][k];flag=true;}
else if(tmp_list[j][k].compare(ans)<0) {ans=tmp_list[j][k];out_max=tmp[j][k];}
}
}
if(flag)
{  cout<<ans;

goto outer;
}

}
vector<vector<double> >  tmp1(tmp);
vector< vector<string> >  list2(tmp_list);
value=tmp1; list=list2;

}
if(!flag)
printf("no arbitrage sequence exists\n");
}
//system("pause");
return 0;
}

``````

modarres
New poster
Posts: 1
Joined: Thu Sep 10, 2009 10:09 am

### Re: 104...I give up

hi all
can you correct my code too ?
it gives correct answer for the sample input :
thx

input :
3
1.2 .89
.88 5.1
1.1 0.15
4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111
2
2.0
0.45
6
0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.1 0.0 0.0
0.0 0.0 1.0 0.0 0.0
0.0 5.0 0.0 0.0 0.0
0.0 0.0 0.0 0.0 9.0
0.0 0.0 0.0 0.0 1.0

output :

1 2 1
3 1 2 3
no arbitrage sequence exists
5 6 5

source :

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include<iostream>
using namespace std;

int starti ;
int startj ;

int ComputeFloydAPSP(float *C, int n, float *A, string* s) //returns 0 if path was found and 1 if not
{

if (n < 2 ){
return 1 ;
}
int i,j,k;
for (int i1=0 ;i1<n ;i1++){
for(int j1=0;j1<n;j1++){
char sz[3]="";
sprintf(sz,"%d",j1+1);
s[i1*n+j1]=sz;
A[i1*n+j1] = C[i1*n+j1] ;

}
}

for (int e1=0;e1<n;e1++){
for (int w1=0;w1<n;w1++){
if (A[e1*n+w1] * A[w1*n+e1] > 1){
starti = e1 ;
startj = w1 ;
return 0 ;
}
}
}

for (k=0; k<n; k++)
{
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{

if (i!=j ){
if ( (*(A+i*n+k)) * (*(A+k*n+j)) > *(A+i*n+j) )
{

*(A+i*n+j) = (*(A+i*n+k)) * (* (A+k*n+j));

s[i*n+j]=s[i*n+k]+" "+s[k*n+j];
if (A[i*n+j]*C[i*n+j]>1){
starti = i ;
startj = j ;
return 0 ;
}
// }
}
}
}
}
}
return 1;
} // Floyd's algorithm

int main()
{
int n ;
while (cin >> n){

float* C = new float[ n*n ];
float* A = new float[ n*n ];

for (int i4=0 ;i4<n ;i4++){
for (int j4=0;j4<n;j4++){
if (i4==j4){
C[i4*n+j4] = 1;
}else{
cin >> C[i4*n+j4] ;
}
}
}

string* s = new string[n*n];

int result = ComputeFloydAPSP(C, n, A, s);
if (result ==0){

cout << starti+1 << " " << s[starti*n+startj] << " " << starti+1 << endl;
}else{
cout << "no arbitrage sequence exists" << endl ;
}

for (int i=0 ;i<n;i++){
for (int j=0 ;j<n ;j++){
A[i*n+j]= A[i*n+j] * C[j*n + i] ;
}
}

}

return 0 ;
}

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: hints for 104

The most important problem of those who cant get Acepted ......
the output may have loops 1->2->3->1->2->3->1 may produce a profit more than .01 but 1->2->3 wont ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

A.Nonyme
New poster
Posts: 1
Joined: Sat Nov 27, 2010 8:46 pm

### Re: hints for 104

Still WA
I tested all additional usecases from the board.
Here is my code :

Code: Select all

``````#include <cstdlib>
#include <iostream>

using namespace std;

namespace {

template<size_t N>
inline void PrintSolution(const unsigned (&iPath)[N][N][N], unsigned iLength, unsigned iCurrency) {
for(unsigned aCurrency = iCurrency; iLength; --iLength) {
cout << aCurrency << '-';
aCurrency = iPath[iLength][iCurrency][aCurrency];
}
cout << iCurrency << endl;
}

template<size_t N>
inline void MakeMoney(const double (& iConvertionTable)[N][N], size_t iNbCurrency) {

static double aBest[N][N][N];
static unsigned aPath[N][N][N];

for(unsigned s = 2; s <= iNbCurrency; ++s)
for(unsigned m = 1; m <= iNbCurrency; ++m)
fill_n(aBest[s][m],iNbCurrency+1,0.);

for(unsigned m = 1; m <= iNbCurrency; ++m)
for(unsigned n = 1; n <= iNbCurrency; ++n) {
aBest[1][m][n] = iConvertionTable[m][n];
aPath[1][m][n] = n;
}

double d;
for(unsigned s = 2; s <= iNbCurrency; ++s) {
for(unsigned i = 1; i <= iNbCurrency; ++i)
for(unsigned m = 1; m <= iNbCurrency; ++m) {
for(unsigned n = 1; n <= iNbCurrency; ++n) {
d = aBest[s-1][m][i] * aBest[1][i][n];
if(d > aBest[s][m][n]) {
aBest[s][m][n] = d;
aPath[s][m][n] = i;
}
}
}

for(unsigned m = 1; m <= iNbCurrency; ++m)
if(aBest[s][m][m] > 1.01)
return PrintSolution(aPath,s,m);

}
cout << "no arbitrage sequence exists" << endl;
}
}

int main(int, char **) {
unsigned aNbCurrency = 0;
double aConvertionTable[21][21];
while(!(cin >> aNbCurrency).eof()){
for(unsigned i = 1; i <= aNbCurrency; ++i) {
for(unsigned j = 1; j < i; ++j)
cin >> aConvertionTable[j][i];
aConvertionTable[i][i] = 1.;
for(unsigned j = i+1; j <= aNbCurrency; ++j)
cin >> aConvertionTable[j][i];
}
MakeMoney(aConvertionTable,aNbCurrency);
}
return EXIT_SUCCESS;
}
``````

gongzhitaao
New poster
Posts: 1
Joined: Mon Aug 06, 2012 6:18 pm
Location: Shanxi

### mark for 104

Got the hint from gits's 7 year's old post and finally solved it!
I m not yet strong enough to be perfectionist. But someday I will make a dent in the universe.

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

### WA on #104

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Locale;
import java.util.Scanner;

class Main
{

private static final String NOTFOUND = "no arbitrage sequence exists";

/*
* Time O( ) Space O()
*/
public String arbitrage(double[][] array, int n) {

//init
ArrayList<String> list ;
for(int i=1; i<n; i++){
list = new ArrayList<String>();
}

int startIndex, endIndex;
double currRate, newRate;
ArrayList<String> tmp;
for (int circle = 2; circle <=n; circle++) {
for(int i=aPath.size(); i>0; i--){
list = aPath.pop();
currRate = Double.valueOf(list.get(0));
startIndex = Integer.valueOf(list.get(1));
endIndex = Integer.valueOf(list.get(list.size() - 1));

for(int j = endIndex + 1; j <= n ; j ++){
newRate = currRate * array[endIndex][j];

if( newRate * array[j][startIndex] > 1.01 )

tmp = new ArrayList<String>();
for(int k=1; k<list.size(); k++){
}
}
}
}
return NOTFOUND;
}

private String toString(ArrayList<String> list){
StringBuilder sb = new StringBuilder();

for(int i=1; i<list.size(); i++){
sb.append(list.get(i));
sb.append(" ");
}

return sb.toString();
}

/**
* @param args
*/
public static void main(String[] args) {
Main sv = new Main();
StdIn in = sv.new StdIn();

try{
while(!in.isEmpty()){
double[][] array = new double[n+1][n+1];

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(i != j)
}
}

System.out.println(sv.arbitrage(array, n));
}
}catch(Exception e){
//e.printStackTrace();
}finally{
in.close();
}

}

class StdIn{
private Scanner scanner;

//Create an input stream for standard input.
public StdIn() {
scanner = new Scanner(new BufferedInputStream(System.in), "UTF-8");
scanner.useLocale(new Locale("en", "US"));
}

// Return the next int from the input stream.
return scanner.nextInt();
}

//Is there only whitespace left on standard input?
public boolean isEmpty() {
return !scanner.hasNext();
}

// Return the next double from the input stream.
return scanner.nextDouble();
}

public void close(){
this.scanner.close();
}
}

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA on #104

Input:

Code: Select all

``````4
1 0 0
1.005 0 0
0 0 0
0 0 0``````
AC output:

Code: Select all

``1 2 1 2 1``
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

### Re: WA on #104

brianfry713 wrote:Input:

Code: Select all

``````4
1 0 0
1.005 0 0
0 0 0
0 0 0``````
AC output:

Code: Select all

``1 2 1 2 1``
From the requirement: If no profiting sequence of n or fewer transactions exists, then the line "no arbitrage sequence exists" should be printed.
so here it should print "no arbitrage sequence exists", am i right ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA on #104

No, you should print 1 2 1 2 1 as that is n=4 transactions.
Check input and AC output for thousands of problems on uDebug!

happyson10
New poster
Posts: 20
Joined: Wed Nov 14, 2012 11:20 pm

### Re: WA on #104

Yes, you are right, it's 4 transaction.

I have got AC with Floyd Marshall algorithm. Anyone can help to see the following straight-forward approach.

package com.uva.ArbitrageN104;

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

class Main
{

private static final String NOTFOUND = "no arbitrage sequence exists";
//static final double EPS = 1e-6d;

/*
* Time O( ) Space O( )
*/
public String arbitrage(double[][] array, int n) {
//init
ArrayList<String> list ;
HashMap<String, String> rates = new HashMap<String, String>();
for(int i=1; i<n; i++){
for(int j=1; j<n; j++){
rates.put(getStr(i, j), String.valueOf(array[j]));

if(array[j] <= 0 || i == j)
continue;

list = new ArrayList<String>();

}
}

int start, end;
double currRate, newRate;
ArrayList<String> tmp;
for(int k=n-2; k>0; k-- ) { // n-2 instead of n-3, max allowed transaction is n.
for(int i=aPath.size(); i>0; i--){
list = aPath.pop();

start = Integer.valueOf(list.get(1));
end = Integer.valueOf(list.get(list.size() - 1));
currRate = Double.valueOf(list.get(0));

for(int j = 1; j < n ; j ++){
newRate = currRate * array[end][j];

if(newRate <= Double.valueOf(rates.get(getStr(start, j))) )
continue;

//if( newRate - 1.01 > EPS && start == j ) // comparison for floating point numbers are inaccurate, it's to "=="
if( newRate > 1.01 && start == j ) // this does work

tmp = new ArrayList<String>();
for(int key=1; key<list.size(); key++){
}
rates.put(getStr(start, j), String.valueOf(newRate));
}
}
}

return NOTFOUND;
}

static String getStr(int i, int j) {
return i + " " + j;
}

private String toString(ArrayList<String> list){
StringBuilder sb = new StringBuilder();

for(int i=1; i<list.size(); i++){
sb.append(list.get(i));
sb.append(" ");
}

return sb.toString();
}

public static void main(String[] args) {
Main sv = new Main();
Scanner in = new Scanner(new BufferedInputStream(System.in), "UTF-8");

try{
while(in.hasNext()){
int n = in.nextInt() + 1;
double[][] array = new double[n][n];

for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if(i != j){
array[j] = in.nextDouble();
if(array[j]<0 ) array[j] = 0;
}else
array[j] = 1;
}
}

System.out.println(sv.arbitrage(array, n));
}
}catch(Exception e){
//e.printStackTrace();
}finally{
in.close();
}
}
}

guang.yang
New poster
Posts: 1
Joined: Mon Dec 10, 2012 8:19 am

### Re:

sandy007smarty wrote:@gits:
I got AC, but I have this doubt.
tmp = best[k][steps-1] * best[k][j][1]

I feel the above statement should be:-

Code: Select all

``best[i][k][steps-m]*best[k][j][m]``
and m should vary from 1 to steps-1 (making the solution O(n^5)).

But why is it not required? Why is just calculating for m=1 enough?
I had the same question as you did. But gave it a second thought, assume x is the vertex before j no matter what m is:
if (x > k), them x will be checked later under the same steps outer loop
else if (x < k), it should have been checked already (in the k outer loop), best[j][k-1] would contains best[x][steps-1] * best[x][j][1] if it produced more profit.
else, currently under check

So m is not required. Agree?