757 - Gone Fishing

[hongping]

I dont know what's wrong with my code. I am using dynamic programming. Upon submission I get runtime error, invalid memory reference. But I think I allocated enough memory. Can anyone tell me what's wrong or perhaps provide some good test data? Thanks.


[cpp]

#include <stdio.h>

#include <iostream.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;



#define maxn 30

#define maxt 200



int a[maxn][maxt],l[maxn][maxt],s[maxn][maxt],p[maxn][maxt];

int t[maxn],f[maxn],d[maxn];

int tt[maxn][maxn];



int n,h;



void input(){

int i;

cin >> h;

for (i=0;i<n;i++)

cin >> f;

for (i=0;i<n;i++)

cin >> d;

for (i=0;i<n-1;i++)

cin >> t;

}



void process(){

int i,j,k;

h*=12;



// time from one lake to another

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

k=0;

for (j=i;j<n-1;j++){

k+=t[j];

tt[j+1]=k;

}

}

k=f[0];

memset(a,0,sizeof(a));

memset(l,0,sizeof(l));

int prevt,ct,v,ct2;



l[0][0]=f[0];

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

// move here from previous lake

for (ct=h;ct>=0;ct--){

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

prevt=ct-tt[j]-1;

if (prevt<0) continue;

// move here from a previous lake

if (a[j][prevt]+f>a[ct]){

a[ct]=a[j][prevt]+f;

l[ct]=max(0,f[i]-d[i]);

p[i][ct]=j;

s[i][ct]=ct-1;



// from current position

for (ct2=ct+1;ct2<=h;ct2++){

v=min(d[i],l[i][ct2-1]);

if (a[i][ct2-1]+l[i][ct2-1]>a[i][ct2]){

a[i][ct2]=a[i][ct2-1]+l[i][ct2-1];

l[i][ct2]=l[i][ct2-1]-v;

p[i][ct2]=j;

s[i][ct2]=ct-1;

}

}

}

}

}

// from current position

if (i==0)

for (ct2=1;ct2<=h;ct2++){

v=min(d[i],l[i][ct2-1]);

if (a[i][ct2-1]+l[i][ct2-1]>a[i][ct2]){

a[i][ct2]=a[i][ct2-1]+l[i][ct2-1];

l[i][ct2]=l[i][ct2-1]-v;

p[i][ct2]=i;

s[i][ct2]=s[i][ct2-1];

}

}



}



// debug

for (j=0;j<=h;j++){

break;

cout << j << ": ";

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

cout << a[i][j] << "/" << l[i][j] << "/" << p[i][j] << "/"<<s[i][j] << " ";;

}

cout << endl;

}

//cout << endl;



// find best

int best=-1,ci,cj;

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

if (best<a[i][h])

{

ci=i;

best=a[i][h];

}

}

int ts[maxn],total=best,prev;

memset(ts,0,sizeof(ts));

cj=h;

k=l[ci][cj];



// find time spent in each lake

while (1==1){

ts[ci]=cj-s[ci][cj];

if (ci==0) break;

prev=p[ci][cj];

cj=s[ci][cj]-tt[prev][ci];

ci=prev;

}





// output

for (i=0;i<n-1;i++){

cout << 5*ts[i] << ", ";

}

cout << 5*ts[n-1] ;

cout << endl;

cout << "Number of fish expected: " << best << endl;

}



void main(){

int nn=0;

int f=1;

while (cin>>n){

if(!n) break;

if (f)f=0;else cout << endl;

input();

process();

}

}

[/cpp]

[amstex]

Hi,
I used DP to solve this problem but I got Runtime Error. Would anyone give some test cases for me to debug? Thank you.

[Rajib]

Try this:

INPUT:

4
4
10 15 50 30
0 3 4 3
40 20 1

OUTPUT:

240, 0, 0, 0
Number of fish expected: 480

[jagadish]

My program gets TLE i am not sure if its due to error in logic or time complexity ( is O(n^4) good enough ? )

Can some check this I/O please ..
i believe multiple input goes like this ..

Code: Select all

2

25
16
20 23 65  88 11 12 13 144 15   6 117 118  49  140  142  142  142 44 45 146  47  118  99  190  188
1  2  3   4  5   6  7  8   9  10 12  12   22  4     5    6   7   18  9  10  12  10   9    1    1
4  11 2  133 4   5  6  7   8   9 10  12   12  22    4    5   6   7  18  9   10  112  32   8

25
16
120 23 65  88 11 12 13 144 15   6 117 118  49  140  142  142  142 44 45 46  47  118  99  110  188
1  2  3   4  5   6  7  8   9  10 12  12   22  0     5    6   7   18  9  0  12  10   9    8    2
1  1  12  13 4   5  6  7   8   9 10  12   12  22    4    5   6   7  18  9   10  12  32   8

25
16
120 23 65  88 11 12 13 34 15   6 17 192  49  140  142  142  24 44 145 46  47  118  99  180  18
5  2  1   4  5   6  7  8   9  10 12  12   22  0     5    6   7   18  9  0  12  10   9    2    2
11  2  0  33 4   5  6  7   8   9 10  12   12  22    4    5   6   7  8  9   1  12  32   8

0

2
16
123 65
1  1
1

3
16
1 31 192
1 1 11
1 1

3
16
2 191 125
1 1 1
1 1

0

edit :

my algorithm had major flaws .most of the outputs here were wrong ...no wonder i was getting WA
mf : thanx for the link

[Solaris]

I have been getting WA in this problem for a quite a long time now..

The last post in this thread was more than one year ago.. but still I am a little bit confused seeing the sample I/O given by jagadish.

For example in the last input the total time is 16 hours. But summing up the plan shown in his output we get 1730 minutes which is far greater than 16 hours (=960 minutes). In fact most of the outputs generated by my program does not match with that of jagadish.. I dont know whether my understanding of the problem or jagadish'es output is wrong.

... my program passes the input given by Rajib

Anyway.. this seems to be multiple input problem... But the problem itself takes multiple test cases (terminating by n=0)..

It will be a great help for me if someone can plzzzzzzzzzzzzzz post some test inputs and outputs (with the multiple input criteria)

thanks in advance

[mf]

You can try test data at http://www.acm.inf.ethz.ch/ProblemSetAr ... index.html

The problem is not multiple input anymore (it used to be.)
jagadish's I/O is incorrect.

[Solaris]

got AC..

It was a simple re-initialization check..

Thanks mf... your test data really helped me a lot..