↓ USACO 2014 December Gold 1 Problem Statement | TL;DR
Code attached at the bottom.
TL;DR problem statement
N (2<=N<=20) cows each has a height, a weight, and a strength (the max weight it can support on its shoulders).
You need to stack up a subset of these cows so that
- each cow can support the weight on its shoulders
- the total height reaches a provided constant H (1<=H<=1e9)
Following that, maximize the additional weight that the cow stack can still support, and output that number. If impossible, print impossible.
Computational resource limit: 1000ms, 128MB
Back to full problem statement
Analysis
N<=20 just gives you a sense of where this is going: to have some kind of optimized status value for each combination of cows, with the combination crammed down into 20 bits (because all combinations is also the independent presence/absence of all cows). We'll come back to this.
The key is the equivalence of one cow to a one-cow stack of cows, and viewing a stack of cows as composed of non-overlapping substacks. These substacks can be considered immutable to the big stack, and therefore have their own height, weight, and strength.
Of course, a stack is genuinely an array of cows. For a stack S, the height and weight are obvious, and the strength is the minimum of each cow's strength minus the weight above it.
For a stack AB formed of stack A on top of B, the numbers are as below:
height(AB) = height(A) + height(B)
weight(AB) = weight(A) + weight(B)
strength(AB) = min(strength(A), strength(B) - weight(A))
We can see that order doesn't matter until you look at the strength. In fact, for a particular set of cows, their order on a single stack matters only to the strength. We will call a stack of a set of cows optimal to the set if the stack strength is high as it can get to.
We join stacks to make bigger ones, and it's easy to see why we don't need to consider using suboptimal stacks as building blocks: the strength formula above tells us that an optimal stack won't do worse than a suboptimal one, and as far as joining stacks goes, we don't care about what actually make up the stacks save for that their sets don't overlap so no cows are used twice.
So, if you go over all combinations of optimal length-N and length-M stacks for which their sets don't overlap, you will get all optimal length-(N+M) stacks. And for every stack of height>=H that we get, we can update the result value.
I considered going from length 1 to 2 to 4 to 8 and so on, but found the number of stack-joining operations blowing up (each time about the square of the number of possible sets). What's wrong with this is that with each stack size, we actually trim off many suboptimal sets, but we skipped many of these steps when we jumped up the numbers.
What I eventually did was just adding 1 cow at a time. This limits the number of loops to 2^20*20 which is approx. 2e7, snuggly fitting into the time limit.
But how to store and look up the sets their optimal stack states? We cram the information of the presence of 20 cows into 20 bits, and there're just about 1e6 cow combinations possible. We could store a lot of data for each set this way, even more than we need.
To traverse all n-cow sets before going to (n+1)-cow sets, we use a queue similar to what we do in BFS (because I can't think of an elegant iterative way), starting from an empty set (0), and for each queue front, we examine the set plus another from any of the unused cows and push to the queue as we see fit.
Of course we could get this to run cleaner: obviously we can trim the unreachable sets. But another one not so obvious is that once the height gets to H, we update the max strength and throw away the set. Why? Well, if it's already height H, making the stack even higher is only going to decrease the strength.
At this point I realize that I made a mistake that actually made the second optimization obsolete. When you see it, it should have been fixed, but the problematic code is below. Pause here and see if you can see what's wrong. Well? I stop the stack only when it updates the max strength, causing sets that don't work as well to pass. This lets through about half of these sets. Pretty bad, huh?
if (dh[q[qf]] >= H && ds[q[qf]] > maxs) // If height is reached and strength is better
{
maxs = ds[q[qf]]; // Update global valid max-strength
continue; // Any more added cows will not increase strength
}
The two lines above that, checking whether the in-queue element is reachable, is also redundant, because if the element is unreachable it will not be in queue. I commented them out but you can still see them.
This is my first post. I try to explain this problem as simply as possible. Please comment if you think I could have been more clear in some parts:)
Full source code
// guard.c
#include <stdio.h>
#include <string.h>
#define MAXN 20
#define MIN(a, b) ( (a < b) ? a : b )
#define MAX(a, b) ( (a > b) ? a : b )
#define INF64 0x7fffffffffffffff
typedef long long ll;
ll H, N;
ll h[MAXN], w[MAXN], s[MAXN];
ll dh[1<<MAXN], dw[1<<MAXN], ds[1<<MAXN];
ll maxs = -1;
int q[1<<MAXN], qf, qr;
FILE *f;
int main()
{
int _0, s_prime;
f = fopen("guard.in", "r");
fscanf(f, "%lld%lld", &N, &H);
for (_0 = 0; _0 < N; ++_0)
fscanf(f, "%lld%lld%lld", h+_0, w+_0, s+_0);
fclose(f);
memset(ds, -1, sizeof(ds));
ds[0] = INF64;
for (qf = 0; qf <= qr; ++qf) // Loop through compressed combination states with binary digit sum
{
// printf("ds[0x%x]=%lld\n", q[qf], ds[q[qf]]); // // There. Debug print.
// if (ds[q[qf]] < 0) // // If unreachable
// continue; // // Ignore
if (dh[q[qf]] >= H) // If height is reached
{
if (ds[q[qf]] > maxs) // If strength is better
maxs = ds[q[qf]]; // Update global valid max-strength
continue; // Any more added cows will not increase strength
}
for (_0 = 0; _0 < N; ++_0) // Loop through possible add-1's
{
if (!(q[qf] & 1<<_0) && (s_prime = MAX( MIN(ds[q[qf]] - w[_0], s[_0]), MIN(s[_0] - dw[q[qf]], ds[q[qf]]) )) > ds[q[qf] | 1<<_0]) // If added-one is unused AND strength is better
{
ds[q[qf] | 1<<_0] = s_prime; // Update strength, obviously
if (!dh[q[qf] | 1<<_0]) // If height-uncached (also weight-uncached and not-in-queue)
{
dh[q[qf] | 1<<_0] = dh[q[qf]] + h[_0]; // Cache height
dw[q[qf] | 1<<_0] = dw[q[qf]] + w[_0]; // Cache weight
q[++qr] = q[qf] | 1<<_0; // Push into queue
}
}
}
}
f = fopen("guard.out", "w");
if (maxs < 0)
fputs("Mark is too tall\n", f);
else
fprintf(f, "%lld\n", maxs);
fclose(f);
return 0;
}
Top comments (0)