I tried to rewrite the getTime() function in the solution myself. What I did was I did not create the lef and rig arrays, I went straight into pushing x[i] or L-x[i] into the v vector for sorting, depending on d[i]. This produced different results for the latter test cases with w > 1 and it would not work, but I wonder why
Could you perhaps show us your code implementing your approach?
vector<pi> finish;
for(int i = 0; i < n; i++){
if(d[i] == 1){
finish.push_back({l-x[i], w[i]});
}
else finish.push_back({x[i], w[i]});
}
sort(finish.begin(), finish.end());
int t = 0;
for(auto& p : finish){
total -= p.second * 2;
if(total <= 0){
t = p.first;
break;
}
}
here, this is the part where I calculate t
What output did you receive on the sample input?
2, which is correct
I see your mistake. I don’t think you read the problem carefully.
Read this:
- A meeting occurs when two cows i and j occupy the same point, where that point is not a barn. In this case, cow i is assigned cow j’s previous velocity and vice versa. Note that cows could potentially meet at points that are not integers.
This indicates that a cow facing the positive direction could end up at the left barn by “bouncing” off a cow going in the negative direction and vice versa.
Your logic implies that a cow facing the positive direction will always end up on the right barn and vice versa, which is incorrect.
I got confused by this at first, but as highlighted in the editorial it doesn’t matter if I assign opposite velocities to cows that collide, it is the same thing if they just pass over each other. It seems like the getTime() function in the official solution ignores this part as well, but it worked properly unlike mine
I think I realize the difference between your solution and the editorials. You considered the right cows and the left cows on the same iteration.
Rather than doing for(int i=0; i<n; i++), you should store the right moving cows are left moving cows separately and implement it like you did except the loops should be for(int i=0; i<leftFacingCow.size(); i++) and for(int i=0; i<rightFacingCow.size(); i++).
Here would be the code that would correctly return the value of t for all test cases:
vector<pi> finish;
vector<int> rightTimes, leftTimes;
for(int i=0; i<n; i++){
if(d[i] == -1){
leftTimes.pb(x[i]);
} else {
rightTimes.pb(x[i]);
}
}
for(int i: leftTimes){
finish.pb({i, w[i]});
}
for(int i: rightTimes){
finish.pb({l-i, w[i]});
}
sort(all(finish));
int t = 0, tot = 0, cur = 0;
while(2*tot <= totWeight){
tot += finish[cur].second;
t++;
cur++;
}
return t;
1 Like
Indeed, but why does it not work with one iteration? Is it not okay to ignore the steps of pushing the times into rightTimes and leftTimes
Please read the editorial carefully. The part saying that “this multiset remains the same regardless of whether cows switch cows or not” means that the number of cows reaching the left barn remains constant rather than the precise cows that end up on the left barn. I advise you to read the following paragraph carefully. Hopefully, that will clarify your misunderstanding of this problem. However, I would agree that the sentence I mentioned was somewhat misleading to many students reading this editorial.
Ah that cleared things up for me. Now I see that the weights pushed back into finish with two iterations is different from the weights I pushed back into finish with one iteration. Thank you for answering, it was really helpful!
