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.
I’m still not sure if your algorithm is correct for this version of the problem. We can only drop cows where haybales are, and what your algorithm does is drop a cow so that it just reaches the leftmost unexploded bale.
The dp is a range minimum where the left endpoint moves monotonically right, which can be done in O(N) time with a deque.
But you can notice that you don’t even need a range minimum, since the dp table is monotonically increasing (if you define it to be dp[i] = covering at least cows 1 through i). So it can be done with two pointers in O(n), more or less equivalent to the greedy solution.