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 problem 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<int> 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.