This is a binary search problem, using simulation to check if a value R works. In the simulation part, say we’re only allowed to detonate cows at the exact locations of haybales.
How do we check quickly if we can explode all N haybales using K cows?
I tried an O(NK) approach where I generate an R-length sliding window for each haybale. I detonate at the location with the largest window. Once some haybales explode, I discount the exploded haybales from each window and find the maximum window length once again. I use prefix sums to calculate how many bales have exploded in a particular range.
I don’t think my code has the right approach. The R-length sliding window might not always work, since it’s essentially a greedy strategy where I detonate the maximum number of haybales possible each time. Can you please explain if or why my code’s logic is correct?
int ok(int R){
bool invalid[N] = {0};
int prefix[N] = {0};
// compute R-length sliding windows
pair<int, int> bales[N];
// haybales before bale j
for (int j = N-1, k = N-1; j >= 0; j--){
while(k > 0 && Pos[k-1] >= Pos[j] - R) k--;
bales[j].f = k;
}
// haybales after bale j
for(int j = 0, k = 0; j < N; j++){
while(k < N-1 && Pos[k+1] <= Pos[j] + R) k++;
bales[j].s = k;
}
for(int i = 0; i < K; i++){
// take the window with the most bales
int l, r;
int maxBales = -1;
for (int j=0; j < N; j++) if (!invalid[j]) {
int a = bales[j].f, b = bales[j].s;
// interval from a to b inclusive
int numInvalid = prefix[b] - (a ? prefix[a-1] : 0);
int total = (b - a + 1) - numInvalid;
if (total > maxBales){
maxBales = total;
l = a, r = b;
}
}
// every haybale from l to r inclusive detonates
for (int j = 0; j < N; j++){
if (l <= j && j <= r) invalid[j] = 1;
prefix[j] = invalid[j];
if (j) prefix[j] += prefix[j-1];
}
}
return prefix[N-1];
}
There is certainly a more efficient approach that is easier to code. The modified problem seems simple enough: find the maximum haybales that can explode if we can only detonate cows at the exact locations of haybales. Can you please help me find the right idea and provide code so I can make progress?
Thanks. I was looking for a more detailed explanation for the greedy strategy. The code does not AC on USACO; I proposed a slightly modified problem, and there’s no place to submit it.
Can anyone please explain, using a swapping argument or any other proof, why detonating the maximum number of haybales each time always succeeds?
Maybe it doesn’t work, since exploding the most haybales doesn’t necessarily produce the optimal sliding window in the next iteration. If so, can you please explain a strategy that would work and provide a counterexample to my proposed algorithm?
I also think it’s possible to solve this problem faster than O(NK) time, since the original problem is solvable in O(\min(N, K)) time. Can you please suggest a faster method (it need not even be greedy, it may just be clever simulation)? Thanks!
The solution to the real problem is different; it’s a simple while loop (simulation) and a two-pointer application. I understand the real problem’s solution - the whole reason for this thread is that I thought of a slight variation. In my modification, we can only detonate haybales at the array locations, not in between the coordinates. I created a greedy strategy for this latter problem, but I haven’t tested it (it’s a modified problem, there’s no place to submit it), and I don’t think it is right. Hence I am asking for help.
Yeah- your code’s incorrect. A countercase would be when we have 2 cows, each of power 3, and the bales are as follows:
1 3 4 5 7
(nvm this doesn’t work see my following post)
If I’m right, your algorithm would first detonate the middle, leaving a sort of chasm between the bales at 1 and 7, making it impossible for the remaining cow to explode them both.
However, if you launch a cow at 3 and 7, all the haybales would explode.
As for the correct approach, this might be overkill, but I think a DP approach might be possible.
With blast radius 3, exploding at position 4 detonates all haybales between 4-3 =1 to 4+3 = 7.
If you mean that the blast radius is 2 (from x-3 to x+3exclusive), then we would explode at location 3 since everything from 1 to 5 would detonate. Then only haybale 7 remains, so the idea would work.
I noticed that I sometimes use windows of haybales that have already exploded. In the above scenario, I would explode at haybale 5 next even though 5 was already detonated. So I modified my code to account for invalid[j].
for (int j=0; j < N; j++){
if (invalid[j]) continue;
int a = bales[j].f, b = bales[j].s;
// interval from a to b inclusive
int numInvalid = prefix[b] - (a ? prefix[a-1] : 0);
int total = (b - a + 1) - numInvalid;
if (total > maxBales){
maxBales = total;
l = a, r = b;
}
}
How would you use a DP approach to solve this problem?
If anyone else has a simpler approach, please let me know.
If R=3, my algorithm would detonate at position 4, removing everything from 1 to 6. Then it would detonate at position 9, removing all haybales.
If R = 2, detonating at position 4 removes 4, 5, 6 and then detonating at position 1 removes 4 haybales. I don’t think it’s possible to do any better,
If anyone else reading this thread has a proof for my greedy approach, please explain it. It seems elementary to argue, though I can’t quite understand how to go about the proof.
Or maybe it doesn’t work, since exploding the most haybales might leave a sub-optimal “chasm” in the next iteration?
My actual intent of this thread, though, is to actually look for a simple idea to my proposed problem that would work.
My O(NK) idea is very slow anyway (the actual USACO problem runs in O(\min(N,K)) time). Can anyone reading this thread please suggest a quicker or smarter solution that does work? Please also explain how you thought about your solution and why it succeeds.
After binary search, the greedy argument is proved more or less just as it’s described in the analysis. Does not require any swap argument.
A more rigorous version: The order you drop cows does not matter. Therefore WLOG drop the cows from left to right. Notice that we cannot skip haybales. Therefore the currently exploded haybales form a frontier that moves from left to right. Notice that it is better to have exploded more haybales than less (because if I can explode X haybales with Z cows I can also explode any Y<X by moving some cows to the left). Therefore each cow you drop should explode as many haybales as possible while still covering the leftmost unexploded haybale.
Same argument works for a variety of 1D point/interval greedy problems: just go left to right and optimize some value. Also is easier to think about (at least for me) if you think about cows as intervals with length 2R and bales as points.
This process can be simulated in O(N) time by tracking the frontier.
Thank you for your excellent explanation of the official solution. I understand the kind of argument we’d use for a similar 1D point/interval greedy problem: due to iterating left-to-right, we don’t have to worry about left points anymore. Once we find the leftmost unexploded haybale, we can continue detonating cows as right as possible, so we keep optimizing the number of bales we explode.
Your explanation helped me understand the official solution better. My intent for this thread was about a slight variation from the actual problem, where we can only detonate cows at the exact location of a haybale. We cannot explode a cow at any integer location, only at the actual array positions where the bales are located. The problem is to count the maximum number of haybales we can explode with K cows.
Please read my first post for an O(NK) idea I thought about (finding the 2R-length sliding window that encompasses the most haybales at each iteration). I am not sure if it is correct, and it isn’t efficient. I don’t think it’s the right way to go about solving my modified problem.
Can you please help me find the right idea for my new problem (maybe greedy or just clever simulation)? Please provide some text explanation and a snippet of code so I can make progress. Thanks!
Oh ok I missed that sentence. It should be an identical argument, all the steps of the proof still work, so the conclusion is the same: explode as many haybales as possible while covering the leftmost.
In general this type of problem can also be done with dp as well if you can’t think of the greedy. Let dp(i) = how many intervals you need to cover a prefix up to point i. Iterate left to right just like in the greedy. It can be done in O(n) time (after sorting) using pointers for either variant of the problem (bit harder for your variant).
Simple counterexample:
0 50 95 96 97 98 99 100 101 102 103 104 105 150 200
R = 50, answer should be 2.
Your greedy will give 3.
One way of seeing that the most to least greedy doesn’t work is by imagining an extreme case: stack a bunch of bales at one point (or basically at the same point like in my test case). That should not change the answer, yet it changes the most to least ordering.
Hello. My approach to this problem would also do binary search and do simulation to verify the mid value. This can be done by greedy, where when we see a hay bale at y, we explode a cow at interval [y,y+mid+mid].
Here is the code that I wrote base on my algorithm, and it worked
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5e4+5;
int x[maxn];
int n,k;
int check (int mid) {
int cnt = 0;
int position = -114514;
for (int i=1;i<=n;i++) {
if (position<x[i]) {
position = x[i]+mid+mid;
cnt++;
}
}
if (cnt>k) return 0;
else return 1;
}
int main () {
cin>>n>>k;
for (int i=1;i<=n;i++) cin>>x[i];
sort(x+1,x+1+n);
int left = 1;
int right = 1e9;
int ans = 0;
while (left<=right) {
int mid = (left+right)/2;
if (check(mid)) {
right = mid-1;
ans = mid;
}
else left = mid+1;
}
cout<<ans<<endl;
}
Are you sure about this? if there’s a cow at haybale x, it’s all the haybales at [x - mid], [x + mid] that explode.
Also, where did you get the weird starting value for position?
When you said you want to explode [x-mid,x+mid], substitute y=x-mid, you will get [y,y+mid+mid]. For the simulation part you can use greedy, which is to sort and iterate the hay bales, and have the left one (y) on some hay bales. This must be true because if there is a hay bale on a, and in my solution, I claimed that having y = a makes it optimized. This is proofed because when y>a, a is ignored so it cannot be, when y<a, the right side, which is y+mid+mid, decrease by a certain amount, which proofs that having y=a is optimized.
For \text{-114514}, its just a random number, I’m very sorry for not annotating it which caused confusion. It can be any number smaller or equal to zero.