Ferry Loading

This problem caused me a lot of frustration when I began on competitive programming. Not because it is particularly hard to solve, but because I wasn't able to come up with a solution and I couldn't wrap my head around solutions of more experienced coders. I decided to revisit it this time.

Ferry Loading

source

We're asked to maximize the number of cars that can be loaded in order onto a ferry with two lanes and a maximum length. We cannot skip any car in the lane thus having a car in the ferry means that all cars that appeared in the waiting line before it must have been loaded in to the ferry.

In this particular problem the main issue is coming up with the states we're going to be storing in the DP table, once that is out the way, everything else is implementation details.

Let $L$ be the maximum length the ferry can hold,$S_k$ be the sum of the lengths of all cars $1..k$, $C_i$ be the length of car $i$ and $dp(i,j)$ be a boolean function that indicates whether we can load cars $1..i$ onto the ferry using $j$ centimeters in the port lane. Thus, our recursive function would start taking form as:

However, here we're only taking into account the cases in which we are loading a car into the port of the ferry and ignoring the starboard. So we need to revise the recursion to also take it into account and with this, we're ready to fill our DP table. I chose to do it using a recursive function and storing the times the port is chosen in order to be able to reconstruct the solution.

As a final observation before coding the solution, since we're not given the number of cars in each test case before hand, it is convenient to limit ourselves to processing the first 200. Given the constraints in the statement, we know that it is impossible to load more than that.

#include<bits/stdc++.h>
#define MAX_CARS 210

using namespace std;

bool dp[MAX_CARS][MAX_CARS * 3000], seen[MAX_CARS][MAX_CARS * 3000], to_port[MAX_CARS][MAX_CARS * 3000];
int car[MAX_CARS], sum[MAX_CARS], length, n;
pair<int,int> ans;

void fill(int , int);
void output(int , int);

int main(){
  ios::sync_with_stdio(false);
  int T; cin >> T;
  bool line = false;

  while(T--){
    if(line) cout << endl;
    line = true;
    cin >> length;
    length *= 100;
    
    memset(dp, 0, sizeof dp);
    memset(seen, 0, sizeof seen);
    memset(to_port, 0, sizeof to_port);
    fill(car, car + MAX_CARS, 0);
    fill(sum, sum + MAX_CARS, 0);
    n = 0;
    int x;
    while(cin >> x && x){
      if(n <= 200){
        ++n;
        car[n] = x;
        sum[n] = sum[n-1] + x;
      }
    }
    dp[0][0] = true;
    ans = make_pair(0, 0);
    fill(0, 0);
    
    cout << ans.first << endl;
    output(ans.first, ans.second);
  }
  return 0;
}
void fill(int c, int port){
  if(c < n && !seen[c][port]){
    seen[c][port] = true;
    if( port + car[c+1] <= length){
      if(c + 1 > ans.first) ans = make_pair(c + 1, port + car[c+1]);
      dp[c+1][port + car[c+1]] = true;
      to_port[c+1][port + car[c+1]] = true;
      fill(c + 1, port + car[c+1]);
    }
    if(sum[c] - port + car[c+1] <= length){
      if(c + 1 > ans.first) ans = make_pair(c + 1, port);
      dp[c+1][port] = true;
      fill(c+1, port);
    }
  }
}
void output(int c, int port){
  if(c == 0) return;
  output(c - 1, port - (to_port[c][port] ? car[c] : 0));    
  cout << (to_port[c][port] ? "port" : "starboard") << endl;
}