Friday, October 31, 2014

Problem:

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;
}

Tuesday, October 28, 2014

UVa Problem 10340 - All in All

Problem:

Solution:

Maintain two pointers, initially pointing at the beginning of the string. If the character matches, advance both pointers, otherwise advance only the second pointers.

That's it, what a simple problem!

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1281

#include "UVa10340.h"

#include <iostream>
#include <string>

using namespace std;

int UVa10340()
{
while (true)
{
string first_string;
string second_string;
cin >> first_string;
if (cin.eof())
{
break;
}
cin >> second_string;
unsigned int first_pointer = 0;
unsigned int second_pointer = 0;
while (first_pointer < first_string.length() && second_pointer < second_string.length())
{
if (first_string[first_pointer] == second_string[second_pointer])
{
first_pointer++;
second_pointer++;
}
else
{
second_pointer++;
}
}
if (first_pointer == first_string.length())
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
return 0;
}

UVa Problem 10020 - Minimal coverage

Problem:

Solution:

This is the first problem that involves a greedy algorithm I solved on UVa. The basic idea is to pick the interval so that it covers as much as possible to the right without creating holes.

So suppose I have these intervals:

[0, 4]
[1, 2]
[2, 5]
[3, 7]
[5, 7]

First thing first, we must cover 0, so we have no choice but picking [0, 4] as our first interval.

Next, we look at [1, 2], there is no point picking [1, 2] at all, we cannot cover anything more with this.

Then, we consider [2, 5], well, we might be able to cover more space with [2, 5], so let's consider it.

Then, we consider [3, 7], now we know [2, 5] is useless because we can cover more space with [3, 7] than [2, 5], note that [3, 7] does not cover [2, 3), but that does not matter, for we have already covered [2, 3) using our first [0. 4], now we are considering [3, 7]

Next, we consider [5, 7], note that [5, 7] does not cover (4, 5), so we decide [3, 7] is what we will pick, as it cover most space subjected to the no hole constraint.

To prove that the greedy algorithm works, we use the greedy algorithm stay ahead techniques. The algorithm maximize the space given least number of segments, so it minimize the number segment given the space constraint!

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=961

#include "UVa10020.h"

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

using namespace std;

int UVa10020()
{
int number_of_test_cases;
cin >> number_of_test_cases;
for (int c = 0; c < number_of_test_cases; c++)
{
int m;
cin >> m;
vector<pair<int, int> > intervals;
while (true)
{
int from;
int to;
cin >> from;
cin >> to;
if (from == 0 && to == 0)
{
break;
}
intervals.push_back(pair<int, int>(from, to));
}

// Start greedy algorithm
int uncovered_index = 0;

sort(intervals.begin(), intervals.end());

// Constructing max cover
vector<pair<int, int> > max_cover;
int required_min = 0;
bool current_best_valid = false;
pair<int, int> current_best;
bool feasible = true;
for (vector<pair<int, int> >::iterator ii = intervals.begin(); ii != intervals.end(); ii++)
{
pair<int, int> current = *ii;
if (current.first <= required_min)
{
if (current.second > current_best.second)
{
current_best.first = current.first;
current_best.second = current.second;
current_best_valid = true;
}
}
else
{
if (current_best_valid)
{
// Current best is the actual best - nothing beyond this will meet the requirement
max_cover.push_back(current_best);

// Now we require more!
required_min = current_best.second;
current_best_valid = false;

if (required_min >= m)
{
// I have already covered M, we can stop now
break;
}
}

if (current.first <= required_min)
{
if (current.second > current_best.second)
{
current_best.first = current.first;
current_best.second = current.second;
current_best_valid = true;
}
}
else
{
feasible = false;
break;
}
}
}
if (current_best_valid)
{
max_cover.push_back(current_best);
}

if (feasible)
{
cout << max_cover.size() << endl;
for (vector<pair<int, int> >::iterator ii = max_cover.begin(); ii != max_cover.end(); ii++)
{
cout << ii->first << " " << ii->second << endl;
}
}
else
{
cout << 0 << endl;
}

if (c != number_of_test_cases - 1)
{
cout << endl;
}
}
return 0;
}

UVa Problem 410 - Station Balance

Problem:

Solution:

Today I started the new subsection on competitive programming - greedy algorithms. The book covers surprising little about greedy algorithm. To me - the greedy paradigm is hard. Come up with some greedy approximation is easy, but I often don't know for certain if a greedy algorithm would work.

This problem, for example, at the first glance, I wouldn't even try greedy to start with.

So I cheated - I spent some time thinking about how would I solve this problem using greedy, but I failed, I read the algorithm in the book and implemented it.

The algorithm state in the book is quite simple as this. Add to the list a bunch of object with 0 mass so that the number of object is exactly twice the number of chambers. Pair up the largest with the smallest and so on.

The book does not cover why this algorithm is optimal. I thought I would try to do it here, but turn I also can't. This only show greedy is really hard. In my attempts, I tried to follow the approaches taught in Algorithm Design (PDF)chapter 4, this is the best book I have found so far about greedy algorithms.

To be honest, I haven't tried very hard, but at the face of it, I don't even know what is the local, myopic criterion that is being optimized, so it is hard to apply the greedy stay ahead trick. For exchange arguments, since we are optimizing a sum that involve non-linearity (you don't know for sure if it is bigger than A or not), there are difficulties there too. Exchange arguments seems more promising but I am not there yet. Yet another idea? I think we might want to show sum of square instead of that sum of imbalance, sum of squares is probably easier to show, but does minimizing sum of squares lead to minimizing sum of imbalance, um, not sure.

Maybe someday I will have the Eureka moment, but well, not now. I will update this post by then.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=351

#include "UVa410.h"

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int UVa410()
{
int case_number = 1;
while (true)
{
int number_of_chambers;
int number_of_elements;
cin >> number_of_chambers;
if (cin.eof())
{
break;
}
cin >> number_of_elements;
vector<int> masses;
for (int i = 0; i < number_of_elements; i++)
{
int mass;
cin >> mass;
masses.push_back(mass);
}

// I have read the book - to be honest - I wouldn't be able to come up
// with this greedy algorithm myself now

sort(masses.begin(), masses.end());

int large_index = masses.size();
int small_index = large_index - 2 * number_of_chambers;

double mean = 0;

for (vector<int>::iterator mi = masses.begin(); mi != masses.end(); mi++)
{
mean += *mi;
}
mean = mean / number_of_chambers;

cout << "Set #" << case_number << endl;
double imbalance = 0;
for (int i = 0; i < number_of_chambers; i++)
{
double chamber_sum = 0;
cout << i << ":";
if (small_index >= 0)
{
chamber_sum += masses[small_index];
cout << " " << masses[small_index];
}
if (large_index > 0)
{
cout << " " << masses[large_index - 1];
chamber_sum += masses[large_index - 1];
}
double diff = chamber_sum - mean;
imbalance += (diff > 0 ? diff : -diff);
small_index++;
large_index--;
cout << endl;
}
std::cout << std::setprecision(5) << std::fixed;
cout << "IMBALANCE = " << imbalance << endl;
cout << endl;

case_number++;
}

return 0;
}