Suppose that you are given n red and n blue water jugs, all different shapes and
ID: 3594680 • Letter: S
Question
Suppose that you are given n red and n blue water jugs, all different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa. Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operations: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one-time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Please remember that you may not directly compare two red jugs or two blue jugs.
Design an algorithm running O(n log n) time to solve an average case.
Design a randomized algorithm running O(n log n) time to solve the grouping water-jug problem.
You may answer both parts using pseudo code.
Explanation / Answer
#include <stdlib.h>
typedef int jug;
static int tmp;
#define EXCHANGE(a, b) {tmp = a; a = b; b = tmp;}
int cmp(jug red, jug blue);
void quadratic_pair(jug *red, jug *blue, int size) {
for (int i = 0; i < size; i++) {
for (int j = i; j < size; j++) {
if (cmp(red[i], blue[j]) == 0) {
EXCHANGE(blue[i], blue[j]);
break;
}
}
}
}
int partition(jug *red, jug *blue, int p, int q);
void quick_pair(jug *red, jug *blue, int p, int r) {
if (p < r - 1) {
int q = partition(red, blue, p, r);
quick_pair(red, blue, p, q);
quick_pair(red, blue, q + 1, r);
}
}
int partition(jug *red, jug *blue, int p, int q) {
int pivot, i;
jug red_pivot, blue_pivot;
i = rand() % (q - p) + p;
EXCHANGE(red[i], red[q - 1]);
red_pivot = red[q - 1];
for (int i = p; i < q; i++) {
if (cmp(red_pivot, blue[i]) == 0) {
EXCHANGE(blue[i], blue[q - 1]);
break;
}
}
pivot = p;
for (int i = p; i < q - 1; i++) {
if (cmp(red_pivot, blue[i]) > 0) {
EXCHANGE(blue[pivot], blue[i]);
pivot++;
}
}
EXCHANGE(blue[pivot], blue[q-1]);
blue_pivot = blue[pivot];
int j = p;
for (int i = p; i < q - 1; i++) {
if (cmp(red[i], blue_pivot) < 0) {
EXCHANGE(red[j], red[i]);
j++;
}
}
EXCHANGE(red[q - 1], red[j]);
return pivot;
}
int cmp(jug red, jug blue) {
return red - blue;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.