The hardest and most annoying problems for me to explain are those I actually wrote. Specially these ones that are actually easy problems. The more obvious a problem seems to me the harder it is to explain something.
Marble positioning
Problem statement. Given a list of at most 8 circle radiuses, find the minimum horizontal distance between the leftmost and rightmost circles if you can place them in any order as long as no two circles overlap.
All permutations
The solution can be split in two parts: First we can decide the order in which we place the circles. The second part is to decide the minimum distance between the leftmost and rightmost circle, without overlap.
For the first part, the images in the examples should tell us that there seems not to be a simple logic that can tell easily us what the best order is. But the number of circles will be small. There are at most 8! = 40320 different permutations of circles to try. We can generate all these permutations and find, for each of them, the minimum distance between the left-most and right-most circle. In order to generate all the permutations we can use backtracking. Although it is also possible to generate all permutations iteratively and C++ even has a next_permutation function.
Minimum width
For a fixed order of circles, find the minimum distance. Place the left-most circle in position 0. Start considering the version with only two circles: We need to place circle 1 in such a position greater than 0 and in such a way that circle 1 and 0 do not overlap. In addition making the distance between their points as small as possible.
We put the circles so close to each other that the exact distance between their centers is now (r0+r1). We can actually tell that circle 0's center is (p0, r0) part of circle 1's center is unknown (p1, r1). We can try an equation to find (p1-p0) using Euclidean distance as a starting point:
r0 + r1 = sqrt( (p1 - p0)^2 + (r1 - r0)^2 ) (r0 + r1)^2 = (p1 - p0)^2 + (r1 - r0)^2 (p1 - p0)^2 = (r0 + r1)^2 - (r1 - r0)^2 (p1 - p0)^2 = r0^2 + 2*r0*r1 + r1^2 - r0^2 + 2*r0*r1 - r1^2 (p1 - p0)^2 = 4 * r0 * r1 p1 - p0) = 2 * sqrt( r0 * r1 )
The minimum distance between the two circles is 2 * sqrt(r0 * r1).
When there are 3 circles. We can assume that we first found the minimum distance between the first two circles. There are two cases:
In this case, the new circle touches circle 1.
In this one, the new circle touches circle 0. It may also be possible that the new circle touches both circle 0 and 1. In any case, there should be at least one circle that touches the new circle. We can generalize: For each of the circles with a smaller index, we can find the minimum distance to place the new circle without overlaps. The maximum of these distances will be the result.
Code
int n = 0;
double[] radius;
// Given the radiuses in a fixed order, find the minimum
// p[n-1] - p[0]:
double minWidth()
{
double[] p = new double[n];
// Place the first marble on point 0.0:
p[0] = 0.0;
for (int i=1; i<n; i++) {
// Decide where to place marble i:
p[i] = 0;
for (int j=0; j<i; j++) {
double dis = p[j] + 2 * Math.sqrt(radius[i] * radius[j]);
// Dis is the minimum distance where we can place i
// without overlaping with j.
p[i] = Math.max(p[i], dis );
// The maximum of all the distances is the best place
// for p[i]
}
}
return p[n-1] - p[0];
}
// Use backtracking to generate each of the permutations of
// the original radius array:
void rec(int p)
{
if (p == n) {
// Remember the permutation with the best result:
best = Math.min(best, minWidth());
} else {
// Decide the radius for position p.
// We have already decided the smaller positions,
// so we need to pick a radius from indices >= p:
double radp = radius[p];
for (int i=p; i<n; i++) {
// Swap radius[p] and radius[i]
radius[p] = radius[i];
radius[i] = radp;
// Step in the recursion:
rec(p + 1);
// Restore radius[i]
radius[i] = radius[p];
}
radius[p] = radp
}
}
public double totalWidth(int[] radius)
{
n = radius.length;
this.radius = new double[i];
for (int i = 0; i < n; i++) {
this.radius = (double)radius[i];
}
// Start backtracking:
rec(0);
return best;
}
TravellingPurchasingMan
Problem statement it is too long to explain in a single paragraph.
Travelling salesman
Let us go with a similar problem (so similar, even the name of the problem is quite close). In this version of the problem, the stores are always open. In this version, it is always possible to buy all the products (assuming all stores are reachable) so let us try the minimum time before buying all products. This is quite close to the Travelling salesman problem.
The main differences is that we need to only visit some stores in which buying a product also takes time. We can simplify the problem by reducing it to a problem that has only store N-1 and the interesting stores. The travel distance between two interesting stores can be calculated as the minimum travel distance (direct or indirect) between the stores from the original problem. To calculate these distances we can use any shortest paths algorithm. We will use Floyd-Warshall because the constraints are low and it can be implemented in few lines. After this change, there is no reason to move from a store to another if you do not plan to buy a product from that store.
Describe the state as (x, mask): x is the current store position and mask is a bitmask representing the set of stores from which you already made a purchase. You are at score x, if you decide to move to store y, it would be because you plan to buy the product at y. Moving between x and y takes as many time as the travel time between the stores. Once you reach store y, you make the purchase taking DURATION time. In total, there is a cost to move from (x, mask) to (y, mask | (1<<y).
The result is the minimum time needed to move from (N-1, 0) to (z, 1111..1), for any z. This makes the problem exactly like travelling salesman.
Closed stores
Let us now include the closing time into the problem. Assume all stores are open at time 0, but each store has a closing time. It may no longer be possible to buy from all reachable stores, because time spent in reaching a store and buying a product may make you unable to buy in other stores.
This makes the time at which you arrive to node (x, mask) important. If the current time is t, and moving to store y makes the time increase to a value higher than the store's closing time, we will not be able to buy the product anymore. If it is so late that it is impossible to buy y's product, it is better not to even go there, we can make it so there is no edge between (x, mask) and (y, mask | (1<<y) ) depending on the current time.
Let t be the minimum time needed to reach state (x, mask), if at this time it is impossible to move from (x, mask) to (y, mask | (1<<y) ), it will never be possible. Thanks to this we only need to know the minimum time to reach state (x, mask) and it determines the edges to other states. As long as we find the minimum time of the closest states, the rest is still about finding the minimum paths. The other difference is with maximizing the number of purchases. We need to find a state (y, mask2) such that there is a path between (x, mask) and a (y, mask2) and mask2 has as many elements as possible.
Open time
Once we add the open time we have a different issue. The time at which you arrive to a store may be too early and we cannot make the purchase before it opens. However, we can just wait some time until the opening time and then make the purchase, thus we can just consider this as an addition to the purchase duration. We arrive to (x, mask) at time t and the distance between x and y was w seconds. If t + w is less than or equal to the closing time, then it is possible to make the purchase. However, if t + w is less than the opening time, we need to wait up until that time. The minimum time to arrive (y, mask|(1<<y)) will be max(t + w, OPEN_TIME ) + DURATION.
A fast enough solution
Although we have successfully reduced the problem to shortest paths, we need to be careful about the time. There are at most 16 interesting stores, this means there are 216 different values for mask and at most 17 values for x (N-1 could be a store that is not interesting). This yields an upper bound for the number of vertices equal to 17*216. The number of edges is smaller, for each vertex, there are at most 16 choices for other stores to visit. 16*17*216 edges may be too large for some Dijkstra implementations, the good news is that we can use a dynamic programming logic instead.
We will move iteratively in increasing order of the mask. We know that the first state is (N-2, 0). From it we can find the minimum costs of all states that have exactly one purchased product. Then for each (i, mask), we can find new costs for some states (j, mask | (1<<j) ) that will have a larger bit mask.
final int INF = 1000000000;
int [] distance;
public int maxStores(int n, String[] interestingStores, String[] roads) {
// Initial distance between any two stores (relevant or not):
int[][] dist = new int[n][n];
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
dist[i][j] = INF;
}
dist[i][i] = 0;
}
// Use the roads to fill that distance array:
for (int i = 0; i < roads.length; i++) {
String[] s = roads[i].split(" ");
int u = Integer.parseInt(s[0]);
int v = Integer.parseInt(s[1]);
int d = Integer.parseInt(s[2]);
dist[u][v] = dist[v][u] = Math.min(dist[v][u], d);
}
//Floyd-Warshall:
for (int k=0; k < n; k++) {
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
// Let us make the new problem that only contains the interesting stores
// and store N-1 (May or may not be interesting):
int m = interestingStores.length;
int[] open = new int[m + 1];
int[] close = new int[m + 1];
int[] duration = new int[m + 1];
int[] storeId = new int[m + 1];
int[] store = new int[n];
Arrays.fill(store,0,n,-1);
for (int i=0; i<m; i++) {
String[] x = interestingStores[i].split(" ");
int s = i;
store[ s ] = i;
open[i] = Integer.parseInt(x[0]);
close[i] = Integer.parseInt(x[1]);
duration[i] = Integer.parseInt(x[2]);
storeId[i] = s;
}
int maskLimit = (1<<m);
// Add store n-1 in case it was not interesting. Let us make it a interesting
// store that is permanently closed.
if (store[n-1] == -1) {
storeId[m] =n-1;
store[n-1] = m;
open[m] = -2;
close[m] = -1;
duration[m] = 0;
m++;
}
//distance[mask * m + x] holds the minimum time needed to reach state (x,mask)
distance = new int[maskLimit*m];
Arrays.fill(distance,0, m*maskLimit, INF);
// At time 0, we start at store (n-1) and no purchases were made.
distance[0*m + store[n-1] ] = 0;
// update the distance array in increasing order of masks:
for (int mask = 0; mask < maskLimit; mask++) {
for (int x=0; x < m; x++) {
if (distance[mask*m + s] < INF) {
int t = distance[mask*m + x];
// We decide to move to store nx:
for (int nx = 0; nx < m; nx ++) {
// If we move to store nx, it is because we want to make
// the purchase.
// Time necessary to move:
int nt = t + dist[ storeId[x] ][ storeId[nx] ];
if (nt <= close[nx]) { //If the store would not be closed:
// After arriving, we may need to wait until the store
// opens. Then we need duration[nx] time to make the purchase:
nt = Math.max(nt, open[nx] ) + duration[nx];
int nmask = mask | (1<<nx);
int nnode = nmask * m + nx;
// Update the distance:
if (distance[nnode] > nt ) {
distance[nnode] = nt;
}
}
}
}
}
}
// Find the mask that has the best number of purchases and is reachable:
int res = 0;
for (int j=0; j<maskLimit; j++) {
// Count the number of bits:
int c = 0;
for (int i=0; i<m; i++) {
if( (j&(1<<i)) != 0 ) {
c ++;
}
}
for (int i=0; i<m; i++) {
if ( distance[j*m + i] != INF ) {
res = Math.max(res, c);
}
}
}
return res;
}
No comments :
Post a Comment