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

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Sat Aug 21, 2004 6:46 am

[cpp]
AC
[/cpp]

txandi
New poster
Posts: 25
Joined: Sun Feb 29, 2004 2:06 am

104 - WA

Post by txandi » Wed Nov 17, 2004 10:21 pm

Need Help!!!
I've summited it lots of times, but still WA :cry:
My algorithm is simple, I save in a table (table[j][k]) the best way to reach "j", starting from "i" with "k" iterations.

What's wrong?? Is it precission??

My code

[cpp]#include <iostream>
#include <vector>

#define EPS 0.0000001

using namespace std;

int main()
{
int n;

while(cin >> n){
double best[n][n][n+1];
int path[n][n][n];
double table[n][n];

int i,j,k,z;

for(i=0;i<n;i++){
table=1;
for(j=0;j<n;j++)
if(i!=j) cin >> table[j];
}

for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n+1;k++)
best[j][k]=0;

for(i=0;i<n;i++)
best[0]=1;

int min=40;
int inimin;

for(i=0;i<n;i++){
bool fin=false;
for(j=1;(j<n+1)&&(j<min);j++){
for(k=0;(k<n)&&(!fin);k++){
for(z=0;(z<n)&&(!fin);z++){
if(best[k][j]<best[z][j-1]*table[z][k]){
best[k][j]=best[i][z][j-1]*table[z][k];
path[i][k][j-1]=z;
if((i==k)&&(best[i][k][j]-1.01>EPS)){
min=j-1;
inimin=i;
fin=true;
}
}
}
}
}
}

if(min==40) cout << "no arbitrage sequence exists" << endl;
else{
int list[min+1];
int a=inimin;
for(i=min;0<=i;i--){
list[i]=path[inimin][a][i];
a=path[inimin][a][i];
}
for(i=0;i<=min;i++)
cout << list[i]+1<< " ";
cout << inimin+1<<endl;
}
}
return 0;
}[/cpp]
Thanks in advance

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

hints for 104

Post by gits » Fri Jan 14, 2005 9:13 pm

I've been trying to solve this problem for sooo long and finally got AC so today is a memorable day for me :)

So here are some clues for those who haven't solved it yet.

1) There are some posts talking about floating point errors, but I didn't check for any in my solution. I use a simple test

Code: Select all

if (profit > 1.01) ...
However, I don't use subtractions and they may create errors.

2) My solution is similar to a Floyd-Warshall (which runs in O(n^3)) but I use an additional outer loop, with the number of exchanges involved, so it's O(n^4) and was within the time limit. I use a 3d table (the new dimension is the number of steps); the rest is pretty much like F-W.

If you grow desperate as I did :D I can further explain how I solved it.

Good luck!

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sat Jan 15, 2005 3:12 pm

Yes, I need further explaination. Please go on.
I stay home. Don't call me out.

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

Post by gits » Sat Jan 15, 2005 5:47 pm

Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid.

Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem...

As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, search the net for floating point errors. However, you won't have to deal with these errors to solve this problems (at least I didn't).

Hope this helps :wink:

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Sun Jan 16, 2005 10:49 am

OK, I'll read the Floyd-Warshall algorithm. Thank you.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Jan 17, 2005 6:24 am

Well, I still don't quite understand. I think the Floyd-Warshall algorithm doesn't suit this problem. Can you tell me how do you modify the algorithm?
I stay home. Don't call me out.

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

Post by gits » Mon Jan 17, 2005 4:59 pm

Floyd-Warshall finds all the mininum paths between every vertex and all the other vertexes. However, in this problem you not only have to find the shortest path, it also has to make a profit of more than 1%.

Simple F-W goes like this:

Code: Select all

// initialization
for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    best[i][j] = path[i][j];
    path[i][j] = i;
  }
}

for (k = 0; k < n; k++) {
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      if (best[i][k] + best[k][j] < best[i][j]) {
        best[i][j] = best[i][k][ + best[k][j];
        path[i][j] = k;
      }
    }
  }
}
For this problem, instead of having best[j] and path[j] I have best[j][s] and path[j][s], which means "best path from i to j in s steps". I also have an outer loop, representing the number of steps.

Code: Select all

// initialization
best[i][j][s] = 0, for all i,j,s
best[i][j][1] = input for the program
best[i][i][1] = 1, for all i
path[i][j][1] = i, for all i, j

for (steps = 2; steps <= n; steps++)
  for k...
    for i..
      for j..
        tmp = best[i][k][steps-1] * best[k][j][1]
        if (tmp > table[i][j][steps]) {
          table[i][j][steps] = tmp;
          path[i][j][steps] = k;
        }
What we are doing is to find the most profitable way to go from i to j in "steps" steps, trying for each to use k as the point just before j. As you can see, this is O(n^4) but since max n is 20 it's ok.

After this, you scan though best[s] (best way to go from i to i again, in s steps). Remember that you want the minimum number of steps that yields a profit; so it's this:

Code: Select all

for (steps = 2; steps <= n; steps++)
  for (i = 0; i < n; i++)
    if (best[i][i][steps] > 1.01) {
      // score!
    }
If the "if" never matches, then there is no arbitrage sequence. If it matches, you have to print the path. To print the path, use path[steps], which is the vertex just before the last (i).

For instance, if i is 1 and steps is 4. Check path[1][1][4]. Suppose it is 2. So the path ends with "... 2 1". Now check path[1][2][3]. Supposing it's 4, the path ends with "... 4 2 1". Now check path[1][4][2]. If it's 5, the path is "... 5 4 2 1". Finally check path[1][5][1], which will be obviously 1. So the complete path is "1 5 4 2 1" (exactly 4 steps).

Just remember that path[j][s] is the vertex which is before the last one in a path from i to j in s steps. If s is 1, the path is simply "i j". In this problem you have to start and finish in the same currency; that's why we only search in best[steps].

Hope this helps, I almost wrote the complete program! :)

You could also stop the algorithm as soon as you found a solution. In other posts, some people talked about a O(n^3) solution but I can't figure it out... if someone has such a solution please mail it to me, I would love to learn how to do this in a better way.

Good luck and happy coding!

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Jan 17, 2005 5:37 pm

What means the array table[][][] in your second code?
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Wed Jan 19, 2005 5:31 am

I think it should be:

Code: Select all

for (steps = 2; steps <= n; steps++) 
  for k... 
    for i.. 
      for j.. 
        tmp = best[i][k][steps-1] * best[k][j][1] 
        if (tmp > best[i][j][steps-1] && tmp > best[i][j][steps])
        { 
          best[i][j][steps] = tmp; 
          path[i][j][steps] = k; 
        }
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Wed Jan 19, 2005 7:10 am

Dear gits, now I have no problem about the algorithm. But could you tell me why the "floating point error:Overflow"?
I stay home. Don't call me out.

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

Post by gits » Wed Jan 19, 2005 11:52 am

Hi! table was a misspelling, I intended to write "best". So it's:

Code: Select all

for (steps = 2; steps <= n; steps++)
  for k...
    for i..
      for j..
        tmp = best[i][k][steps-1] * best[k][j][1]
        if (tmp > best[i][j][steps]) {
          best[i][j][steps] = tmp;
          path[i][j][steps] = k;
        } 
Sorry for the confusion! Notice that best[j][s] is pre-loaded with 0, for all i,j and s >= 2.

Are you getting floating point error? If you post your code I may help.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Wed Jan 19, 2005 4:45 pm

Oh, now I have not floating point error, that was just because of a wrong typing.
But I got WA. This is my code which works all right on the sample input.

Code: Select all

#include<stdio.h>
int main()
{
  int n,/*维数*/
      i,j,k,step,
      path[20][20][20],/*用来记录最佳路径*/
      get,
      seq[20];/*最后要输出的数组*/
  double best[20][20][20],/*best[i][j][s]表示从i到j花了s步的最大利润*/
         temp;
  while(scanf("%d",&n)==1)
  {
    get=0;
    for(step=0;step<n;step++)
      if(step==0)
      {
        for(i=0;i<n;i++)
          for(j=0;j<n;j++)
          {
            if(i==j)
              best[i][j][step]=1.0;
            else
              scanf("%lf",&best[i][j][step]);
            path[i][j][step]=i;
          }
      }
      else
        for(i=0;i<n;i++)
          for(j=0;j<n;j++)
            best[i][j][step]=0;
    for(step=1;step<n;step++)/*题目要求最多n步*/
      for(k=0;k<n;k++)
        for(i=0;i<n;i++)
          for(j=0;j<n;j++)
          {
            temp=best[i][k][step-1]*best[k][j][0];
            if(temp>best[i][j][step])
            {
              best[i][j][step]=temp;
              path[i][j][step]=k;
            }
          }
    for(step=1;step<n;step++)
    {
      for(i=0;i<n;i++)
      {
        if(best[i][i][step]>1.01)
        {
          seq[step]=path[i][i][step];
          for(j=step-1;j>=0;j--)
            seq[j]=path[i][seq[j+1]][j];
          for(j=0;j<=step;j++)
            printf("%d ",seq[j]+1);
          printf("1\n");
          get=1;
          break;
        }
      }
      if(get==1)
        break;
    }
    if(get!=1)
    printf("no arbitrage sequence exists\n");
  }
  return 0;
}
Last edited by ImLazy on Tue Feb 15, 2005 12:45 pm, edited 1 time in total.
I stay home. Don't call me out.

gits
New poster
Posts: 19
Joined: Sun Oct 26, 2003 10:08 pm
Location: Aveiro, Portugal
Contact:

Post by gits » Wed Jan 19, 2005 5:09 pm

try this input:

Code: Select all

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 should be

Code: Select all

5 6 5
but your program gives

Code: Select all

5 6 1
which is wrong, because you have to end in the same place as you started.

Actually, you have a silly bug :D check again the line

Code: Select all

printf("1\n");
This is supposed to be the last country, which should be the same as the first... but the first isn't always 1, as in the input above. So, just change that line to

Code: Select all

printf("%d\n", i+1)
and you should be fine :wink:

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Thu Jan 20, 2005 5:21 am

Now I get AC. Thank you very much.
I stay home. Don't call me out.

Post Reply

Return to “Volume 1 (100-199)”