Here is a codeforces problem 1420D. And I was seeing the solution from one of tourist livestream for this contest. And the solution he was explaining to this prolem is something like this; ~~~~~ int main() { ios::sync._with_ stdio(false); cin.tie(e); int n, k; cin >> n >> k; vector‹int> 1(n); vector r(n); for (int i = 0; i ‹ n; i++) { cin > 1[i] » r[i]; } vector‹int> order(n); iota(order.begin(), order.end(), ®); sort(order.begin(), order.end(), [&](int i, int j){ return l[i] < l[j]; }); // suppose l[1] <= l[2] <= .... <= l[n] // suppose we pick segments s[1] < s[2] < ... ‹ s[k] // we want segments s[1], s[2],.., s[k] to intersect in at least one point // <=> max(l[s[1]], l[s[2],... ,l[s[k]]) <= min(r[s[1]], r[s[2]],... ,r[s[k]]) // <=> l[s[k]] ‹= min(r[s[1]], r[s[2]],..., r[s[k]]) // <=> l[s[k]] <= r[s[1]] and l[s[k]] ‹= l[s[2]] and ... and l[s[k]] <= r[s[k — 1]]
Mint ans = 0; multiset<int> rs; for (int i : order) { while (!rs.empty() && *rs.begin() < l[i]) { rs.erase(rs.begin()); } int cnt = (int) rs.size(); ans += C(cnt, k - 1); rs.insert(r[i]); } cout << ans << '\n'; return 0;
} ~~~~~
However, I dont get it that how this solution is preventing the overcounting of the same set of k-elements at different states in the loop?
For example: consider n = 5, k = 2, and the on/off time as, [1, 10], [2, 10], [3, 10], [4, 10], [5, 10] Then, for each i =1 to 5:
i = 1: Multiset contains {(1, 10)}.
i = 2: Multiset contains {(1, 10), (2, 10)}.
i = 3: Multiset contains {(1, 10), (2, 10), (3, 10)}.
i = 4: Multiset contains {(1, 10), (2, 10), (3, 10), (4, 10)}.
i = 5: Multiset contains {(1, 10), (2, 10), (3, 10), (4, 10), (5, 10)}.
So we can clearly see that we can always choose the same set of k=2 element in almost every state starting from i = 2, and thus we end up counting the same set of k-elements multiple time.
So, I don't understand how this solution is preventing this over counting? It would be really helpful if someone can explain it.
Thanks.