SLIPPERS - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

DRAFT EXPLANATION:

Note: The editorial is underway. To not keep you waiting however, the draft editorial of the author is attached below.

A given final configuration i_1<i_2<...<i_k of indexes of remaining slippers is possible if and only if s_{i_j} \ge s_i for some i_j<i implies that i=i_{j'} for some j < j'. Consider the indexes of running maximums m_1<m_2<...<m_h of (s_{i_j}). The crucial observation is that (m_j) identifies the sequence (i_j) and all the increasing subsequences are valid sequences of running maximums. Hence, the answer to the problem is the number of strictly increasing subsequences, which may be computed (with a Fenwick tree) in O(N\log(N)).

2 Likes

Can we get to see the authors code @dario2994 If possible sir