10261 - Ferry Loading

[mido]

Don't think so....

For any greedy algm you think of, you'd probably be able to find a counter case...

Good luck...

[chuzpa]

hi if someone could help me with MORE I/O, i'll apreciate it ...

I have some I/O I think they're right ...

INPUTS ...

Code: Select all

15

20
101
207
155
143
512
335
108
977
567
201
188
311
112
0

6 
200 
200 
400 
400 
0

1
200
100
0

1
100
200
0

1
100
100
0

1
10
20
30
40
50
0

50
2500
3000
1000
1000
1500
700
800
0

1
10
20
30
40
50
60
0

1
10
20
30
40
40
60
0

15
100
100
200
200
300
300
400
400
500
500
0

1
200
0

22
1200
500
2000
450
200
0

1
10
7
2
11
13
34
22
45
1
2
10
4
50
0

1
10
7
2
11
13
34
22
45
1
2
10
4
39
0

100

100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
0
 

OUTPUTS

Code: Select all

13
starboard
starboard
port
port
starboard
port
port
starboard
port
starboard
port
port
port


4
starboard
port
starboard
port

0

1
starboard

2
starboard
port

5
starboard
starboard
starboard
starboard
port

6
port
starboard
starboard
starboard
port
port

5
starboard
starboard
starboard
starboard
port

6
starboard
starboard
starboard
starboard
port
port

10
starboard
port
starboard
starboard
starboard
starboard
starboard
port
port
port

0

5
port
port
starboard
port
starboard

12
starboard
port
port
starboard
port
starboard
port
starboard
port
port
port
port

13
starboard
port
port
starboard
port
starboard
port
starboard
port
port
port
port
port

200
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port

[/code]

[chuzpa]

I've got Accepted a few days ago ... , anyways the I/Os I posted are correct, I hope they help someone...

[tarukas]

I got WA at all time.
Can somebody can help me ?

My thought:
1. Find out the most car can be loaded on ferry(n cars).
2. Using DP(Knapsack way, the length of ferry is the size, just single side) to create the table.
3. Takes car as most as possible and find the most balanced result.

For sample input, My code output is

Code: Select all

6
port
starboard
starboard
starboard
port
port

My C code:

Code: Select all

/*
* Name: knapsack
* Params:   iCIA--> Input array for car, Start from "0"
* iCN --> Number of cars in input array, Start from "1"
* iFL	--> Ferry Length, Start from "0"
*/
void knapsack(int *iCIA, int iCN, int iFL)
{
int **exist;	/* exist table */
int **last;		/* Take last one car? */
int iTL = 0;	                /* (Totla length of input cars ) */
int diff = 99999999;	/* the different of two sides*/

int *iPI;		/* (Port Index Array */
int *iPFI;		/* (Port Final Index) */
int iPFN= 0;	/* (Port Final Num)*/

int iTPL = 0;	/* (Total Port Langth) */
int iFOB = 0;	/* (Final OnBoad Car Num ) */

int idx;
int iTLtmp;
int iFLtmp;
int iCNtmp;

int i, j, k, l, m, n, o;

DPRINTF("Numbers of car= %d, Ferry Length= %d\n", iCN, iFL);

if(iCN == 0)	/* No car can loaded on ferry */
{
printf("0\n\n");
return;
}

exist	= (int **) malloc(sizeof(int *) * (iCN + 1));
exist[0]= (int *)  malloc(sizeof(int) * (iCN + 1) * (iFL + 1));
last 	= (int **) malloc(sizeof(int *) * (iCN + 1));
last[0]	= (int *)  malloc(sizeof(int) * (iCN + 1) * (iFL + 1));

for(i = 1; i <= iCN; i++){
	exist[i] = exist[i - 1] + (iFL+ 1);
	last[i]	 = last[i - 1] + (iFL + 1);
}

for(i = 0 ; i < iCN; i++)
	iTL += iCIA[i];

DPRINTF("Total Input Length= %d\n", iTL);


exist[0][0] = YES;

for(i = 1; i <= iFL; i++)
      exist[0][i] = NO;

/* knapsack */
for(i = 1; i <= iCN; i++)
{
   for(j = 0; j <= iFL; j++)
   {
      exist[i][j] = last[i][j] = NO;  /* Initial value*/
      if(exist[i-1][j])
     {
	DPRINTF("last[%d][%d]=NO\n", i, j);
	exist[i][j]	= YES;
	last[i][j] = NO;
     }
     else
     {
              if(j >= iCIA[i-1])
             {
	if(exist[i- 1][j- iCIA[i- 1]])
	{
	DPRINTF("last[%d][%d]=YES(%d)\n", i, j, iCIA[i-1]);
	exist[i][j] = YES;
	last[i][j]   = YES;   /* Take last one car */
	}
             }
     }
   }
}

DPRINTF("Max car for count= %d, iFL= %d\n", iCN, iFL);

iPI = (int *)malloc(sizeof(int) * iCN);
iPFI = (int *)malloc(sizeof(int) * iCN);

for(i = 0; i < iCN; i++)
    iPFI[i] = NO;

/* Find the most balanced result for each exist[][]*/
for(i= iCN, j= iFL; i != 0 && j > 0 && iFL > 0 && iTL > 0; j--)
{
    iFLtmp = j;
    iTLtmp = iTL;
    iTPL = 0;

    for(o = 0; o < iCN; o++)
         iPI[o] = NO;

    if(exist[i][j] == YES)
   {
       DPRINTF("exist[%d][%d]= YES\n", i, j);

       for(k = i; k > 0; k--) /* Find Up */
       {
           if((last[k][j] ==YES) && (last[k-1][j] == NO))
           {
	DPRINTF("last[%d][%d]last= YES\n", k, j);
	for(idx= 0, l= k, m= j; l!= 0 && m > 0; )
	{
	    if(last[l][m] == YES)
	    {
                       iPI[idx++] = --l;
                       iTPL += iCIA[l];
	       m -= iCIA[l];
                    }
	    else
	    {
	            l--;
	    }
	}

	iCNtmp = i;				

	/* Port side msut >= iTL-iTPL */
	if(iTPL >= (iTLtmp-iTPL))
	{
	     if(diff > (iTPL - (iTLtmp - iTPL)))
                     {						          if(iCNtmp >= iFOB)
	          {
	             iFOB = iCNtmp;
	             iPFN = idx;				
                             diff = (iTPL - (iTLtmp - iTPL));
						
							             DPRINTF("diff=> %d, iFOB= %d\n", diff, iFOB);
	
	             for(n = 0; n < idx; n++)   /* save the result */
		iPFI[n] = iPI[n];
	          }
                      }
	 }
	else
	{
	    if(iFOB != 0)
	        goto found;
	}
          }
       }
    }

    if((j == 1) && (iFOB ==0))
   {
      i--;
      j  = iFL;
      iTL  -= iCIA[i];
   }
}

found:
   free(iPI);

   printf("%d\n", iFOB);

   for(i = 0; i < iPFN; i++)
      DPRINTF("iPFI[%d]= %d\n", i, iPFI[i]);

   for(i = 0, j = iPFN - 1; i < iFOB ; i++)
   {
      if(iPFI[j] == i)
      {
          if(j != 0)
              j--;
          printf("starboard\n");
       }
       else
       {
            printf("port\n");
        }
   }

[tarukas]

I have tried some test input according to previous posts in forum.
And I thought the output of mine is correct.
I also write a random input generator for testing.
But I still cannot find out that why I got WA.
Can somebody can give me some test data for debug purpose?

The post http://online-judge.uva.es/board/viewto ... ight=10261 contain some I/O.

According to this. My Output is:

Code: Select all

13
starboard
port
port
starboard
port
starboard
port
port
starboard
starboard
starboard
starboard
starboard

4
port
starboard
port
starboard

0

1
port

2
port
starboard

5
port
starboard
port
port
starboard

6
starboard
port
port
port
starboard
starboard

5
port
starboard
port
port
starboard

6
port
port
port
port
starboard
starboard

10
port
starboard
port
port
port
port
port
starboard
starboard
starboard

0

5
starboard
starboard
port
starboard
port

12
port
starboard
port
starboard
port
port
port
starboard
starboard
starboard
starboard
starboard

13
port
starboard
starboard
port
starboard
port
starboard
port
starboard
starboard
starboard
starboard
starboard

2
port
starboard

200
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
port
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard
starboard

Any ideas?

[sanjoy_nemo]

i'm trying this problem for a long time now. i'm new in dp. here is my C++ code:

Code: Select all

#include<stdio.h>
#include<string.h>


int memo[600][20000];
int que[600],qi;
char side[5][600],ms;

int load(int port_sz,int star_sz,int ci)
{
    if(ci>=ms)
    {
        strcpy(side[1],side[0]);
        ms=ci;
    }
    if((port_sz<0 || star_sz<0 || ci==qi) || (port_sz<que[ci] && star_sz<que[ci]))
        return 0;
    if(memo[ci][star_sz])
        return memo[ci][star_sz];

    int x,y;
    side[0][ci]='p';
    x=port_sz>=que[ci]?load(port_sz-que[ci],star_sz,ci+1):0;
    side[0][ci]='s';
    y=star_sz>=que[ci]?load(port_sz,star_sz-que[ci],ci+1):0;
    int t=x>=y?x+1:y+1;
    side[0][ci]=0;
    return memo[ci][star_sz]=t;
}


int main()
{
    int icas,ncas,i,j,n,x;
    //memo=new int[10010][10010][210];

    scanf("%d",&ncas);
    for(icas=0;icas<ncas;icas++)
    {
        if(icas)
        {
            printf("\n");
            memset(memo,0,sizeof(memo));
            memset(side,0,sizeof(side));
        }
        scanf("%d",&n);
        n*=100;
        qi=0;
        while(scanf("%d",&que[qi]) && que[qi])
            qi++;
        ms=0;
        x=load(n,n,0);
        printf("%d\n",x);
        for(i=0;i<x;i++)
        {
            if(side[1][i]=='p')
                printf("port\n");
            else if(side[1][i]=='s')
                printf("starboard\n");
        }

    }
    return 0;
}

i'll appreciate any kind of help ( i/o, alternate solution, err correction or else)

[sadia_atique]

I'm getting WA for this problem..I've tried all I/O posted here,and my code gives correct output for them..cannot find the bug,anyone please help kindly

Code: Select all

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int cars[205];
int sum[205];
int L,N,Max;
int DP[205][100*100+5];
int trace[205][100*100+5];
int func(int ind,int port)
{
   //printf("ind:%d port:%d\n",ind,port);
    if(ind==N+1)
      return 0;      
   
   if(DP[ind][port]!=-1) return DP[ind][port];
  
   int ret1=0,ret2=0,Ans;
   if(port+cars[ind]<=L){                
     ret1=1+func(ind+1,port+cars[ind]);
     }
   if(sum[ind]-port<=L){
     ret2=1+func(ind+1,port);
     }
   if(ret1==0 && ret2==0)
   {
      trace[ind][port]=0;
      return DP[ind][port]=0;        
   }
   
   if(ret2>ret1)
      trace[ind][port]=2; 
             
   else
      trace[ind][port]=1;
      
   //printf("ind:%d port:%d ret1:%d ret2:%d Ans:%d\n",ind,port,ret1,ret2,Ans);
   Ans=max(ret1,ret2);
   return DP[ind][port]=Ans;  
}
int main()
{
    int Ans,i,j,k,n,T;
    bool first=true;
    scanf("%d",&T);
    while(T--)
    {
       
       sum[0]=0;
       scanf("%d",&L);
       L*=100;
       i=1;
       //printf("L:%d\n",L);
       while(scanf("%d",&n) && n!=0)
       {
          cars[i]=n;
          //printf("i:%d cars[i]:%d\n",i,cars[i]);
          sum[i]=sum[i-1]+n;
          i++;                       
       }
       N=--i;
       //printf("N:%d\n",N);
       memset(trace,0,sizeof(trace));
       memset(DP,-1,sizeof(DP));
       Ans=func(1,0);
       if(first) first=false;
       else puts("");
       printf("%d\n",Ans);
       if(Ans==0)
       {
         continue;
         }
       for(j=0,i=1; i<=Ans; i++)
       {
          puts(trace[i][j]==1?"starboard":"port");
          if(trace[i][j]==1) j+=cars[i];          
       }
       
    }
    return 0;
}

[brianfry713]

Input:

Code: Select all

1

98
3551
8043
6203
1798
1190
0

AC output:

Code: Select all

3
starboard
port
starboard

[brianfry713]

Input:

Code: Select all

1

90
4167
6071
5239
2440
1381
2446
2502
3324
7985
2749
1693
8172
3128
1088
1026
5850
408
7692
1130
3087
7157
2922
1599
2992
7558
4696
8821
4818
1558
6123
9833
9273
5841
8719
1712
7122
1165
7762
4094
9050
510
9335
969
3539
423
1895
3036
4379
3234
4066
7366
391
635
8865
6931
8093
3560
9400
6558
8667
9170
6390
7939
8658
5109
9552
9428
9822
7313
3521
8871
1471
2855
3487
8558
3178
8931
5241
7457
2164
2954
8471
6103
3489
7335
3034
1581
4543
6081
1786
3209
8898
8076
4795
7555
6832
7994
6982
6653
5307
4150
9172
425
6906
2658
8883
3731
1588
7771
4836
7301
724
3306
3403
4113
4288
9985
9242
8731
6065
1027
5587
8610
2750
382
9813
3230
2023
6794
9783
7230
944
2701
1302
1497
8908
3832
5128
4143
1602
9864
1443
2226
6817
4747
9887
1105
4731
9128
3483
4444
3802
2718
3053
6453
3000
6513
9583
8571
3307
3112
5801
7799
9362
750
9196
8269
4483
7971
6059
5985
7835
7403
1859
8299
2149
1745
9304
527
4521
2787
4871
1970
5405
1572
0

AC output:

Code: Select all

2
port
starboard

[akurniawan]

hello, can anybody help me, what's wrong with my program? i've been trying for 2 days now

Code: Select all

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define FORS(i,a,b) for (int i = a; i <= b; ++i)
#define FORD(i,a,b) for (int i = a; i > b; --i)
#define FORDS(i,a,b) for (int i = a; i >= b; --i)
#define FORE(i,a) for (typeof(a.begin()) i = a.begin(); i != a.end(); ++i)
#define SET(a,v) memset(a, v, sizeof a)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define ALL(a) a.begin(), a.end()
#define oo 1023123123
#define nl '\n'

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

int n, _f, car[205], sum[205], dp[205][10005], idx, taken[205][10005];

int f(int i, int l) {
  if (i == idx) return 0;

  int &ans = dp[i][l];
  if (ans != -1) return ans;

  ans = 0;
  if (l + car[i] <= _f) {
    // cout << "a : " << i << " " << l << " " << car[i] << " " << l + car[i] << " " << ans <<nl;
    taken[i][l + car[i]] = 1;
    ans = max(ans, f(i + 1, l + car[i]) + 1);
  }
  if ((sum[i - 1] - l) + car[i] <= _f) {
    // cout << "b : " << i << " " << l << " " << car[i] << " " << ans << nl;
    taken[i][l] = 0;
    ans = max(ans, f(i + 1, l) + 1);
  }
  return ans;
}

int main() {_
  bool blank = false;
  cin >> n;
  while (n--) {
    if (blank) cout << nl; blank = true;
    cin >> _f;

    int in;
    idx = 0;
    while (cin >> in && in) {
      car[idx] = in;
      sum[idx] = (!idx) ? in : sum[idx - 1] + in;
      idx++;
    }

    _f *= 100;
    SET (dp, -1);
    SET (taken, -1);
    int res = f(0, 0);
    cout << res << nl;
    if (res) {
      int len;
      FORS (i, 0, 10000) {
        if (taken[res - 1][i] == 1) {
          len = i;
        }
      }

      string s = "";
      // int totLeft = 0, totRight = 0;
      FORDS (i, res - 1, 0) {
        // cout << i << " " << len << " " << taken[i][len] << nl;
        if (taken[i][len] == 1) {
          // totLeft += car[i];
          s = "port\n" + s;
          len -= car[i];
        } else if (taken[i][len] == 0) {
          // totRight += car[i];
          s = "starboard\n" + s;
        }
      }
      // cout << totLeft << " " << totRight << nl;
      cout << s;
    }
  }

  return 0;
}

[brianfry713]

I think the issue is with your taken array. One way to solve this using backtracking is:
Keep a visited set on the current index and length of left and right sides of the ferry. If this state has already been visited, then return.
Keep a bool array that lists which side each car goes on for the current state.
Keep a global max_cars and bool array which lists which side each car goes on for the best answer.

Also note that there may be more than 200 cars in the input, you should ignore any after that.

[dhruba07]

How many cars will be there ? There is a comment that there may be 200 cars,we ignore after that.Why would we ignore that?