The problem is as follows;
int main) {
ios:: sync.
_with_ stdiofalse);
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 1[i] < 1[31;
;
suppose 1[1] <=1[2] <=+・
<= 1[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(I[s[1]],
1[s[2]1,
... ,
1[s[k]]) <= min(r[s[1]], r[s[2]],
... ,
r[s[k]])
1[s[k]] ‹= min(r[s[1]], r[s[2]],
..., r[s[k]])
<=> 1[s[k]] <= r[s[1]] and 1[s[k]] ‹= r[s[2]] and
... and 1[s[k]] <= r[s[k - 1]]
Mint ans = 0;
multiset<int> rs;
for (int i : order) {
while (Irs.empty() && *rs.begin() < 1[i]) {
rs.erase(rs.begin());
}
int cnt = (int) rs.size();
// choose k-1 segments from cnt
ans += C(cnt, k - 1); rs.insert(r[i]);
cout «< ans « '\n';
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;
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.