104 - Arbitrage

[shady_mokhtar]

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<<" ";   
   }
}

plz reply ...thx

[shady_mokhtar]

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]

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

Thanks in advance !!!!!!!!!!!!

// 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]

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]

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]

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

[A.Nonyme]

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]

Got the hint from gits's 7 year's old post and finally solved it!

[happyson10]

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.LinkedList;
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 ;
LinkedList<ArrayList<String>> aPath = new LinkedList<ArrayList<String>>();
for(int i=1; i<n; i++){
list = new ArrayList<String>();
list.add(String.valueOf(1)); //rate
list.add(String.valueOf(i)); //country #x
aPath.add(list);
}

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 )
return toString(list) + j + " " + startIndex;

tmp = new ArrayList<String>();
tmp.add(String.valueOf(newRate));
for(int k=1; k<list.size(); k++){
tmp.add(list.get(k));
}
tmp.add(String.valueOf(j));
aPath.addLast(tmp);
}
}
}
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()){
int n = in.readInt();
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)
array[j] = in.readDouble();
}
}

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.
public int readInt() {
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.
public double readDouble() {
return scanner.nextDouble();
}

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


}

[brianfry713]

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

[happyson10]

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]

No, you should print 1 2 1 2 1 as that is n=4 transactions.

[happyson10]

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.LinkedList;
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 ;
LinkedList<ArrayList<String>> aPath = new LinkedList<ArrayList<String>>();
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>();
list.add(String.valueOf(array[j])); //rate
list.add(String.valueOf(i)); //country #x
list.add(String.valueOf(j)); //country #x

aPath.add(list);
}
}

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
return toString(list) + j;

tmp = new ArrayList<String>();
tmp.add(String.valueOf(newRate));
for(int key=1; key<list.size(); key++){
tmp.add(list.get(key));
}
tmp.add(String.valueOf(j));
aPath.addLast(tmp);
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]

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