Why is my greedy approach wrong for Codeforces 2248B?
I'm trying to solve Codeforces 2248B, and I came up with a multiset-based greedy approach.
My idea is the following:
For every b[i], I want to choose two elements from the current multiset:
lo= the smallest availablea, preferablyst.begin(), such thatlo < b[i]hi= the smallest availableagreater thanb[i]i.e.st.upper_bound(b[i])
Then I replace those two elements with b[i].
So conceptually:
auto lo = st.begin();
auto hi = st.upper_bound(b[i]);
if (lo == st.end() || *lo >= b[i] || hi == st.end()) {
// impossible
}
st.erase(lo);
st.erase(hi);
st.insert(b[i]);
I initially implemented something very similar:
sort(a.begin(), a.end());
sort(b.begin(), b.end());
multiset<ll> st(a.begin(), a.end());
if (n < 2 * m) {
cout << "NO\n";
return;
}
for (int i = 0; i < m; i++) {
auto hi_it = st.lower_bound(b[i]);
if (hi_it == st.begin() || hi_it == st.end()) {
cout << "NO\n";
return;
}
auto lo_it = st.begin();
st.erase(lo_it);
st.erase(hi_it);
st.insert(b[i]);
}
cout << "YES\n";
My intuition is that choosing the smallest possible lower element should be safe because it leaves all the larger elements available for future b[i] values.
Similarly, choosing the smallest possible upper element should also be safe because I'm consuming the closest possible value above b[i] rather than wasting a larger value.
My intuition is that choosing the smallest possible lower element should be safe because it leaves all the larger elements available for future b[i] values.Similarly, choosing the smallest possible upper element should also be safe because I'm consuming the closest possible value above b[i] rather than wasting a larger value.
However, I understand that my greedy choice is apparently not correct.
What I'm struggling with is understanding exactly where the logic breaks.
