104 - Arbitrage

[El-idioto]

Dear Gambit,

Actually, I see you set the exchange from currency A to currency A at 1.0. I set that at 0.0 because that will never be part of the shortest path.

Regarding input 2, my program gives the following steps. Between brackets is the previous currency on the shortest path.

Code: Select all

0.000000(-1)  3.100000(-1)  0.002300(-1)  0.350000(-1)
0.210000(-1)  0.000000(-1)  0.003530(-1)  8.130000(-1)
200.0000(-1)  180.5590(-1)  0.000000(-1)  10.33900(-1)
2.110000(-1)  0.089000(-1)  0.061110(-1)  0.000000(-1)

0.738500(3)  0.415286(2)  0.021388(3)  25.20300(1)
17.15430(3)  0.723570(3)  0.496824(3)  0.073500(0)
37.91739(1)  620.0000(0)  0.637373(1)  1467.944670(1)
12.22200(2)  11.03396(2)  0.004853(0)  0.738500(0)

53.178330(3)    3.86188600(2)   1.540155(3)   3.376273(1)
99.364860(2)    89.7060990(2)   0.039455(0)   6.004005(0)
3097.363254(3) 130.6470760(3)   89.706099(3)  5040.600(1)
2.3171320(1)    37.8882000(0)   0.045130(3)   89.706099(1)

1 2 4 1

[El-idioto]

In case you're still stuck, here's my AC program.
Simply uncomment the TEST define to get debug output (prints the profit matrix after every step).

Good luck,

Sander

[cpp]
// @JUDGE_ID: 33444KK 104 C++
//
// 104_Arbitrage: Try to find a way to make money from exchange rates
//


#include <cstdio>

// The base types
#ifdef WIN32
typedef __int8 int8;
typedef __int16 int16;
typedef __int32 int32;
typedef __int64 int64;
typedef unsigned __int8 uint8;
typedef unsigned __int16 uint16;
typedef unsigned __int32 uint32;
typedef unsigned __int64 uint64;
#else
typedef char int8;
typedef short int16;
typedef long int32;
typedef long long int int64;
typedef unsigned char uint8;
typedef unsigned short uint16;
typedef unsigned long uint32;
typedef unsigned long long int uint64;
#endif

// These macros safely delete (an array of) objects
#define SAFE_DELETE(pObj) { if(pObj) { delete pObj; pObj = NULL; } }
#define SAFE_DELETE_ARRAY(pArr) { if(pArr) { delete[] pArr; pArr = NULL; } }

// The maximum amount of currencies
#define MAX_CUR 20

// The minimum required profit
#define MIN_PROFIT 1.01


// This function returns the bigger of the two elements
template <class T> T Max(T tA, T tB)
{
return tA > tB ? tA : tB;
}

// The profit structure
struct PROFIT
{
double dProfit; // The highest profit after n steps
uint8 u8PrevCur; // The currency we came from in step n-1
};


// The city class
class CExchanges
{
private:
// The private variables
PROFIT m_pppProfit[MAX_CUR][MAX_CUR][MAX_CUR]; // The profits per distance
uint8 m_u8TotCur; // The total amount of currencies

// The private functions
void CalcNextStep(uint8 u8Matrix);

public:
// The public functions
CExchanges() {}
~CExchanges() {}
void CalcProfitSequence(double dMinProfit);
void PrintMatrix(uint8 u8Matrix);
void PrintSequence(uint8 u8From, uint8 u8To, uint8 u8Steps);
bool ReadExchangeRates();
};

// Uncomment the next line for debug output
#define TEST


//------------------------------------------------------------------------------------
// F U N C T I O N S
//------------------------------------------------------------------------------------


// This function is the entrance of the app
int main()
{
CExchanges exchange;

// Get the next exchange rates table
while(exchange.ReadExchangeRates())
exchange.CalcProfitSequence(MIN_PROFIT);

return 0;
}


//------------------------------------------------------------------------------------


// This function calculates the (next) profit matrix
void CExchanges::CalcNextStep(uint8 u8Matrix)
{
// The most profitable way to go from A to Z in n steps P(A,Z,n) which
// goes through the highest yielding currency X is:
// P(A,Z,n) = P(Z,X,n-1) + P(X,Z,1)

// Calculate the profit matrix for n steps
for(uint8 u8From=0;u8From<m_u8TotCur;u8From++)
{
for(uint8 u8To=0;u8To<m_u8TotCur;u8To++)
{
double dBest;
uint8 u8Best = 0;

// Find the best path in n-1 steps
dBest = m_pppProfit[u8Matrix-1][u8From][u8Best].dProfit * m_pppProfit[0][u8Best][u8To].dProfit;
for(uint8 u8=1;u8<m_u8TotCur;u8++)
{
double dNew = m_pppProfit[u8Matrix-1][u8From][u8].dProfit * m_pppProfit[0][u8][u8To].dProfit;

// Do we have a better path?
if(dNew > dBest)
{
// We have a better path
dBest = dNew;
u8Best = u8;
}
}

// Expand the path with the best path
m_pppProfit[u8Matrix][u8From][u8To].dProfit = dBest;
m_pppProfit[u8Matrix][u8From][u8To].u8PrevCur = u8Best;
}
}
}


//------------------------------------------------------------------------------------


// This function calculates the most profitable sequences
void CExchanges::CalcProfitSequence(double dMinProfit)
{
bool bFound = false;
uint8 u8Steps = 1;

#ifdef TEST
PrintMatrix(0);
#endif

// Calculate the matrices
while(!bFound && u8Steps < m_u8TotCur)
{
// Calculate the next step
CalcNextStep(u8Steps);

#ifdef TEST
PrintMatrix(u8Steps);
#endif

// Can we go from x back to x and make at least the specified profit?
for(uint8 u8Cur=0;u8Cur<m_u8TotCur;u8Cur++)
{
// Have we found a profitable sequence?
if(m_pppProfit[u8Steps][u8Cur][u8Cur].dProfit >= dMinProfit)
{
// We found a profitable sequence
PrintSequence(u8Cur, u8Cur, u8Steps);
bFound = true;
break;
}
}

// Go to the next step
u8Steps++;
}

// Haven't we found a profitable sequence?
if(!bFound)
printf("no arbitrage sequence exists\n");
}


//------------------------------------------------------------------------------------


// This function prints a sequence
void CExchanges::PrintSequence(uint8 u8From, uint8 u8To, uint8 u8TotSteps)
{
uint8 pu8Path[MAX_CUR], u8Pos = 0;

// There is actually 1 step more, since there is a step 0 (the given exchange rates)
u8TotSteps++;

// Start at the last currency
pu8Path[u8Pos++] = u8To;

// Trace the path back
for(uint8 u8Step=1;u8Step<u8TotSteps;u8Step++)
{
// Add the step
pu8Path[u8Pos] = m_pppProfit[u8TotSteps-u8Step][u8From][pu8Path[u8Pos-1]].u8PrevCur;
u8Pos++;
}

// End with the first currency
pu8Path[u8Pos] = u8From;

// Print the (1-based) sequence in the correct order
for(int8 i8Step=u8TotSteps;i8Step>=0;i8Step--)
printf("%u%s", pu8Path[i8Step]+1, i8Step > 0 ? " " : "\n");
}


//------------------------------------------------------------------------------------


// This function prints the contents of a matrix
void CExchanges::PrintMatrix(uint8 u8Matrix)
{
// Print the contents of the sum matrix
for(uint8 u8From=0;u8From<m_u8TotCur;u8From++)
for(uint8 u8To=0;u8To<m_u8TotCur;u8To++)
printf("%f(%u) %s",
m_pppProfit[u8Matrix][u8From][u8To].dProfit,
m_pppProfit[u8Matrix][u8From][u8To].u8PrevCur,
u8To < m_u8TotCur-1 ? " " : "\n");

printf("\n");
}


//------------------------------------------------------------------------------------


// This function reads a matrix with exchange rates
bool CExchanges::ReadExchangeRates()
{
bool bResult = false;
uint16 u16TotCur;

// Get the total amount of currencies
if(scanf("%hu", &u16TotCur) == 1)
{
// Set the total amount of currencies
m_u8TotCur = (uint8)u16TotCur;

// Read the exchange rates of all currencies
for(uint8 u8From=0;u8From<m_u8TotCur;u8From++)
{
// Read the exchange rates for the currency
for(uint8 u8To=0;u8To<m_u8TotCur;u8To++)
{
// Is it the currency itself?
if(u8From == u8To)
m_pppProfit[0][u8From][u8To].dProfit = 0.0;
else
scanf("%lf", &m_pppProfit[0][u8From][u8To].dProfit);
}
}

bResult = true;
}

return bResult;
}
[/cpp]

[kleber]

Hello friends,

I'm trying to solve the 104 problem, but I couldn't understand what I need to do to solve it. I couldn't understand the inputs. Is there anybody who can help me, explaing me more didacticaly what I need to do in that problem ?

Thansk for any help.

Kleber

[Dominik Michniewski]

You must find shortest chain of exchanges, which gives you maximal profit, but such chain coudn't be longer than number of currencies and profit must be greater (or equal - I don't remember) than 1%.

Input contains cross-matrix for currencies. It means that in matrix on position (i,j) exist value which means how many currency 'j' can you buy when you got 1 unit of currency 'i'.

Best regards
DM

[kleber]

Right, but I didn't understand that cross-matrix of currencies. For example:

3
1.2 .89
.88 5.1
1.1 0.15

what does that input sample above mean ? How can I start to prepare that matrix to solve the problem ? Let's suppose we have 3 currencies (A$, B$, C$), can you explain me (using these currencies and the input sample above) what does it mean ?

Thanks,

Kleber

[scruff]

Ok, your matrix looks like this:

Code: Select all

3 
1.2 .89 
.88 5.1 
1.1 0.15 

The first line 3 means that you have three countries to trade currencies between.

The next line 1.2 .89 means if you have 1 unit of country A$'s currency then you can get 1.2 units of country B$'s currency. Moreover, you can get .89 of country C$'s currency from 1 unit of country A$'s currency

The next line .88 5.1 means that if you have 1 unit of country B$'s currency (B$ because we are on row two of the matrix or on the second countries exchange rates) then you can get .88 units of country A$'s currency, also you can get 5.1 units of country C$'s currency from 1 unit of country B$'s currency

Finally, the last line 1.1 0.15 means that if you have 1 unit of country C$'s currency (C$ because we are now on the third row of our matrix) you can get 1.1 units of country A$'s currency, and you can get .15 units of country B$'s currency for just 1 unit of country C$'s

The matrix has been minimized to save basic or assumed rates. These assumed rates are for trading from country A$'s currency to country A$'s currency. Obviously you can't just give the bank $100 and expect to get anything else but $100 back from them. These exchanges are removed from the input matrix, but you can insert them again to make the exchanges a little bit more clear. The matrix would then look like this:

Code: Select all

1      1.2    .89 
.88    1       5.1 
1.1   0.15    1

These added 1's are are just for changing from A$'s currency to A$'s currency.

You can also view the matrix like an adjacency list from a graph. Where the rows represent the starting currency and the columns represent the ending currency. Like so:

Code: Select all

     To -> | Country A$  Country B$  Country C$
___________|___________________________
From       |
Country A$ |    1                .88              1.2
Country B$ |    .89              1                5.1
Country C$ |     1.1              .15               1

This is the same exact matrix as you will notice just a little bit different way of looking at it. So... if I want to get from country C$'s currency to country B$'s currency, I would, go down the rows until I got to country C$'s row, and then I would go across to get to country B$'s column. I am now at the exchange rate to exchange 1 unit of country C$'s currency to country B$'s currency. This exchange rate is .15... meaning for $1 of C$ currency I get $0.15 of B$'s currency.

[chuppy]

Hi all,

As many of the guys here suggested it, I tried to solve the problem using the Floyd algorithm but with no success It is intended for finding the minimum paths in graph. If we use it in this case, it's possible to have cycles because we have to multiply numbers lower and higher than 1... Is this the right algorithm for this problem?

Thanks.

[scruff]

Yes this is a correct algorithm for this problem although you have to change it some. The biggest advice I've seen someone give for this problem is to calculate the profits after each exchange and save them in a 3 dimensional table. 2 of the dimensions for the exchange rates and the third dimension is for the number of exchanges so far.

In other words
input:
3
1.2 .89
.88 5.1
1.1 0.15
first exchange is just the given values
[ 0 1.2 0.89]
[ 0.88 0 5.1]
[ 1.1 0.15 0]

second exchange
[ 1.056 0.1335 6.12]
[ 5.61 1.056 0.7832]
[ 0.132 1.32 0.979]

[cpp]
for(j=1;j<=n;++j){// number of exchanges
for(i=0;i<n;++i){ // starting currency
for(k=0;k<n;++k){ // ending currency
Find_the_most_profitable_exchange_from_i_to_k(i,k);
}
}
}
[/cpp]

[junbin]

Is there any helpful guy who can post some test cases , cause my program works fine with test cases and I used DP . Please helppppp!!!

If your program works for all your own test data, then it's probably correct in terms of algorithm.. this is a pretty straight forward DP problem.

However, when I did the problem, I had 50+ wrong submissions.. the main problems (which I found later) were these:

1) floating point errors.
2) You need an arbitrage of MORE than 1.01.
3) The length of the arbitrage is capped.
4) floating point errors.
5) floating point errors.
6) floating point errors.
7) You get the idea.

[tlucz]

4) floating point errors.
5) floating point errors.
6) floating point errors.

Could you explain what floating point errors may be in this problem. I used a modified Floyd-Warshall algorithm, I passed all my and forum's tests but I still give WA in online judge. I don't know why.

[junbin]

Is there any helpful guy who can post some test cases , cause my program works fine with test cases and I used DP . Please helppppp!!!

Tips:

1) Check your floating point numbers.. the judge has some data that is VERY close to 1.01. If I remember right, you need to get MORE than 1.01.. (do floating point comparison, if it's about 1.01, reject. only when it's more than eps do you accept a solution)

2) Make sure the length of the arbitrage is within specification (max leng is n i think)

3) You can't use traditional flyod warshall here if that is what you are doing.. you need a 3 layer matrix.

4) I doubt anyone who solved the problem long ago will have any test data handy.. it's better if you just generate some random data of your own and then post it.. I'll post the results I get with my program.

[scruff]

why not try this random input generator.

http://people.eecs.ku.edu/~rucker/valladolid/

[gits]

in problem 104, the sample input

4
3.1 0.0023 0.35
0.21 0.00353 8.13
200 180.559 10.339
2.11 0.089 0.06111

yelds output

1 2 4 1

(which gives 3.1*8.13*2.11=53.17833% profit). However, my program gave solution

1 2 3 1

which also turns out to be correct (3.1*0.00353*200=2.1886% profit).

The problem states that we should output the shortest sequence that profits more than 1%; since these two sequences are both length 3, which one is correct? The one that gives greatest profit or any of the two?

If anyone could also post some more test cases it would be very appreciated.

Thanks for your time and good luck :)

[UFP2161]

The problem description states what to do:

If there is more than one sequence that results in a profit of more than 1 percent you must print a sequence of minimal length, i.e., one of the sequences that uses the fewest exchanges of currencies to yield a profit.

[tlucz]

This program generates only input data with short output sequence. My program pass all that tests. Have anybody test input data with long output sequence.