PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES
Longest increasing subsequence
EXPLANATION:
Lemma: Let R be a subset of \{1,2,\dots, N\}. The set S is a possible set of indexes of remaining slippers if and only if, for any pair of indexes i<j with S_i\ge S_j if i\in R then also j\in R.
Proof:
Consider i\in R and i<j with s_i \ge s_j. Any guest who can take the j-th pair of slippers can take also the i-th pair of slippers, but the i-th pair is not taken and comes before the j-th pair, so the j-th pair is not taken.
Now, let us show that if the condition holds, then there is a configuration of guests so that R is exactly the set of remaining slippers.
If R coincides with \{1,2,\dots, N\} then it is clearly possible (if, for examples, there are no guests). Otherwise, let j be the smallest index so that j\not\in R. Assume that the first guest has shoes’ size equal to S_j. Since j\not\in S we know for sure that for any i<j (which belong to R by assumption) it holds S_i > S_j. Thus the first guest will take the i-th pair of slippers. This reasoning can be repeated until there are slippers remaining but which do not belong to R.
Now, consider a possible set of remaining pair of slippers R (which has to satisfy the condition of the lemma). A pair of slippers is special if it is not taken and its size is strictly larger than all previous pair of slippers. Notice that the special pairs of slippers constitutes a strictly increasing subsequence of the array S_1,S_2,\dots, S_N. Moreover, one can see that (as a consequence of the condition satisfied by R) an index i belongs to R if and only if there is a special j with j \le i and S_j\ge S_i.
Hence, the sequence of special pairs of slippers uniquely identifies the set R.
One can see, with the same reasoning, that any strictly increasing subsequence of S_1, S_2,\dots, S_N is a valid set of special slippers (i.e., it generates a set R which satisfies the condition of the lemma).
As a consequence of what we said, the number of possible sets R satisfying the condition of the lemma (that is, the answer to the problem) coincides with the number of strictly increasing subsequences.
Counting the strictly increasing subsequences is a classical problem and can be solved in O(N\log(N)) using a Fenwick tree (or a segment tree).
SOLUTION
The author’s solution can be found here.