I redid USACO Silver Paired up. My approach is to pair the cow with smallest output with the cow with largest output as long as possible. I implement this using standard two pointers. The key loop which gives an error follows.
while (i <= j) {
ans = max(ans, pairs[i].f + pairs[j].f);
int amt = min(pairs[i].s, pairs[j].s);
pairs[i].s -= amt;
pairs[j].s -= amt;
if (pairs[i].s == 0) ++i;
if (pairs[j].s == 0) --j;
//cout << pairs[i].s << " " << pairs[j].s << endl;
}
In the sample input, we have i = j = 1 and pairs[i].s = pairs[j].s = 2. Then amt = 2 and the pairs[i].s and pairs[j].s should both come out to be 2-2 = 0.
If I do the following 4 lines in this order:
pairs[i].s -= amt;
pairs[j].s -= amt;
if (pairs[i].s == 0) ++i;
if (pairs[j].s == 0) --j;
their values pairs[i].s and pairs[j].s are instead -2. The program results in an infinite loop.
However, if I change the order of the lines:
pairs[i].s -= amt;
if (pairs[i].s == 0) ++i;
pairs[j].s -= amt;
if (pairs[j].s == 0) --j;
the program gives the correct answer.
Why did simply separating the two subtraction lines (pairs[i].s -= amt and pairs[j].s -= amt) make a difference? The first order of execution seems to cause obstructive implicit behavior that I don’t follow.