## Friday, October 31, 2014

### UVa Problem 10440 - Ferry Loading II

Problem:

Please find the problem here.

Solution:

Competitive Programming hinted on using a greedy algorithm. So I thought about that in a few different ways.

Eager moving does not work

Say, you have capacity 100, only a 100 cars stopped by, a ferry has a large trip time. Waiting for all car stopped by and move is the most efficient way, moving eagerly is not.

Lazy moving does not work, either

Same setting, but 101 cars stopped by. Waiting for 100 cars and then move is not good, move on the first car, by the time the ferry returned we have accumulated a lot of pending car, we can multiplex the time between waiting car and moving in this case.

Plan backwards seems promising, but too complex.

The ideal case is when the last car arrives, if we could get the ferry there and move, that would be great, in order to do that, the ferry must leave before one round trip time before the last ferry available, this may of may not be feasible. Thinking this direction it seems quite complex to move on, so I think something else.

Now this works: Starting from the beginning of time, we make choices, and these choices lead us to a different states. Suppose we model the states as a graph, and we assign edge weights as time/number of trips between the states, then the problem of planning the ferry becomes finding a shortest path on this graph.

Using the Dijkstra's algorithm, we can find shortest path. All edges are positive so we don't need to worry. The problem is the expanding of the state graph can be big, and much of the state space don't need to be explored. Fortunately it is easy for us to modify Dijkstra algorithm to not requiring the whole graph is start.

Let's go through this input:

2 10 3
10
30
40

Suppose we start with the state { time = -1, processed_cars = 0, pending_cars = 0, num_trips = 0 }.

At time = -1, there is no car, the only possible move for us to do is to wait until the first car arrives, at time 10, so the state becomes { time = 10, processed_cars = 0, pending_cars = 1, num_trips = 0 }.

At this state, we have two choices, we can wait, or we can move, this results in two states
{ time = 30, processed_cars = 0, pending_cars = 2, num_trips = 0} and { time = 30, processed_cars = 1, pending_cars = 1, num_trips = 1}.

The states are then put in a priority queue and processed in priority order, that make sure we find the shortest path.

Code:

#include "stdafx.h"

// #define LOG

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1381

#include "UVa10440.h"

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct UVa10440_state
{
public:
UVa10440_state(int time, int processed_cars, int pending_cars, int trip_count) : time(time), processed_cars(processed_cars), pending_cars(pending_cars), trip_count(trip_count)
{

}
int time;
int processed_cars;
int pending_cars;
int trip_count;
};

// return 1  if left priority > right
// return 0  if left priority = right
// return -1 if left priority < right
int compare_priority(const UVa10440_state* left, const UVa10440_state* right)
{
if (left->time < right->time)
{
return 1;
}
else if (left->time > right->time)
{
return -1;
}
if (left->trip_count < right->trip_count)
{
return 1;
}
else if (left->trip_count > right->trip_count)
{
return -1;
}

return 0;
}

void bubble_down(vector<UVa10440_state*>& priority_queue, int current_index, int& size)
{
while (true)
{
int left_child_index = (current_index + 1) * 2 - 1;
int right_child_index = left_child_index + 1;
bool has_left = left_child_index < size;
bool has_right = right_child_index < size;

if (has_left && has_right)
{
if (compare_priority(priority_queue[left_child_index], priority_queue[right_child_index]) == 1)
{
if (compare_priority(priority_queue[left_child_index], priority_queue[current_index]) == 1)
{
UVa10440_state* temp = priority_queue[current_index];
priority_queue[current_index] = priority_queue[left_child_index];
priority_queue[left_child_index] = temp;
current_index = left_child_index;
}
else
{
break;
}
}
else
{
if (compare_priority(priority_queue[right_child_index], priority_queue[current_index]) == 1)
{
UVa10440_state* temp = priority_queue[current_index];
priority_queue[current_index] = priority_queue[right_child_index];
priority_queue[right_child_index] = temp;
current_index = right_child_index;
}
else
{
break;
}
}
}
else if (has_left)
{
if (compare_priority(priority_queue[left_child_index], priority_queue[current_index]) == 1)
{
UVa10440_state* temp = priority_queue[current_index];
priority_queue[current_index] = priority_queue[left_child_index];
priority_queue[left_child_index] = temp;
current_index = left_child_index;
}
else
{
break;
}
}
else
{
break;
}
}
}

UVa10440_state* delete_min(vector<UVa10440_state*>& priority_queue, int& size)
{
UVa10440_state* result = priority_queue[0];
priority_queue[0] = priority_queue[size - 1];
priority_queue[size - 1] = NULL;
size--;
bubble_down(priority_queue, 0, size);
return result;
}

void insert(vector<UVa10440_state*>& priority_queue, int& size, UVa10440_state* new_item)
{
if (priority_queue.size() == size)
{
priority_queue.push_back(new_item);
}
else
{
priority_queue[size] = new_item;
}
size++;

int current_index = size - 1;
while (current_index > 0)
{
int parent_index = (current_index + 1) / 2 - 1;
int compare_result = compare_priority(priority_queue[current_index], priority_queue[parent_index]);

if (compare_result == 1)
{
UVa10440_state* temp = priority_queue[current_index];
priority_queue[current_index] = priority_queue[parent_index];
priority_queue[parent_index] = temp;
current_index = parent_index;
}
else if (compare_result == 0)
{
priority_queue[current_index] = priority_queue[size - 1];
priority_queue[size - 1] = NULL;
size--;
bubble_down(priority_queue, current_index, size);
break;
}
else
{
break;
}
}
}

int UVa10440()
{
int number_of_test_cases = 0;
cin >> number_of_test_cases;
for (int c = 0; c < number_of_test_cases; c++)
{
int ferry_capacity;
int trip_time;
int number_of_cars;
cin >> ferry_capacity;
cin >> trip_time;
cin >> number_of_cars;
vector<int> arrival_times;
for (int i = 0; i < number_of_cars; i++)
{
int arrival_time;
cin >> arrival_time;
arrival_times.push_back(arrival_time);
}

vector<UVa10440_state*> priority_queue;

int size = 1;
priority_queue.push_back(new UVa10440_state(-1, 0, 0, 0));

UVa10440_state* last_best = NULL;

while (size > 0)
{
// Step 1: Find the current best state
UVa10440_state* current_best = delete_min(priority_queue, size);

#ifdef LOG
cout << endl;
cout << "After delete min, the priority queue has " << size << " elements after the moves." << endl;
for (unsigned int p = 0; p < priority_queue.size(); p++)
{
if (priority_queue[p] == NULL)
{
cout << "(null)" << endl;
}
else
{
cout << priority_queue[p]->time << ", " << priority_queue[p]->processed_cars << ", " << priority_queue[p]->pending_cars << ", " << priority_queue[p]->trip_count << endl;
}
}
cout << endl;
#endif

if (last_best != NULL)
{
if (last_best->time == current_best->time && last_best->trip_count == current_best->trip_count && last_best->processed_cars == current_best->processed_cars)
{
// It is possible that the duplicate removal does not work :( because the minimum is on another branch
continue;
}
}
last_best = current_best;

#ifdef LOG
cout << "Processing current best at time " << current_best->time << " with " << current_best->processed_cars << " processed and " << current_best->pending_cars << " pending with " << current_best->trip_count << " trips." << endl;
#endif

if (current_best->processed_cars == number_of_cars)
{
cout << current_best->time - trip_time << " " << current_best->trip_count << endl;
break;
}

// Step 2: What moves are available
if (current_best->pending_cars > 0)
{
// In this case, we can consider moving right now
int new_time = current_best->time + 2 * trip_time;
int new_processed_cars = current_best->processed_cars + min(current_best->pending_cars, ferry_capacity);
int new_unseen_cars = number_of_cars - (upper_bound(arrival_times.begin(), arrival_times.end(), new_time) - arrival_times.begin());
int new_pending_cars = number_of_cars - new_processed_cars - new_unseen_cars;
int new_trip_count = current_best->trip_count + 1;
insert(priority_queue, size, new UVa10440_state(new_time, new_processed_cars, new_pending_cars, new_trip_count));
}

if (current_best->pending_cars < ferry_capacity)
{
// In this case we can consider waiting
unsigned int next_move_index = upper_bound(arrival_times.begin(), arrival_times.end(), current_best->time) - arrival_times.begin();
if (next_move_index < arrival_times.size())
{
int new_time = arrival_times[next_move_index];
int new_processed_cars = current_best->processed_cars;
int new_unseen_cars = number_of_cars - (upper_bound(arrival_times.begin(), arrival_times.end(), new_time) - arrival_times.begin());
int new_pending_cars = number_of_cars - new_processed_cars - new_unseen_cars;
int new_trip_count = current_best->trip_count;
insert(priority_queue, size, new UVa10440_state(new_time, new_processed_cars, new_pending_cars, new_trip_count));
}
}
#ifdef LOG
cout << endl;
cout << "The priority queue has " << size << " elements after the moves." << endl;
for (unsigned int p = 0; p < priority_queue.size(); p++)
{
if (priority_queue[p] == NULL)
{
cout << "(null)" << endl;
}
else
{
cout << priority_queue[p]->time << ", " << priority_queue[p]->processed_cars << ", " << priority_queue[p]->pending_cars << ", " << priority_queue[p]->trip_count << endl;
}
}
cout << endl;
#endif
}
}
return 0;
}