Is it Sorted or Not (ENIGMA - PLINTH'20 LNMIIT)

help
1

Can someone explain the solution to this problem ?

2

  1. Note that q = C_n^k = \frac{n!}{k! (n - k)!}, and the actual question is to calculate p, i.e. the number of ways to choose an ordered sequence of length k from an array A.

  2. Precompute modular factorials and inverse factorials of numbers up to n. Can be done in O(n + \log \texttt{mod}) or O(n \log \texttt{mod}), depending on how do you do it. Any of those is certainly ok

  3. Build a frequency counter from the array A, i.e. std::map mp: mp[key] = number of indices i such that a[i] == key. This can be done by a simple loop for (auto ai: a) ++mp[ai];. Another lightweight O(n \ln n)

  4. For simplicity, you can further build a vector cnt of map’s values in the ascending order of keys. Since std::map’s keys are already sorted, this can be done by another simple loop: for (auto kv: mp) cnt.push_back(kv.second);. + O(n)

  5. Use dynamic programming with dp[i][j] = number of ways to choose an ordered sequence of length j from first i distinct numbers. Initial condition is dp[0][0] = 1 and the transitions formulas can be obtained by considering i-th number: we have cnt[i] of them, and if we choose to add m of them to any of existing ordered sequences, then we have A_{\texttt{cnt[i]}}^m = \frac{\texttt{cnt[i]}!}{(\texttt{cnt[i]}-m)!} ways to do it. The answer will be dp[cnt.size()][k]. Speaking of time, we have no more than k \cdot \left(\sum_{i = 1}^{\texttt{cnt.size()}} (\texttt{cnt[i]} + 1)\right), transitions, which is no more than 2 n k.

You can check my submission for more details

4 Likes
3

Bro, i am not getting how you are finding p. if possible please explain with an example.

4

Let’s suppose that initial array is [1,1,2,3,3,3]. Frequency map will be {1:2, 2:1, 3:3}.

  • Let’s consider 1s: we have two of them. We have 1 way not to use any of them, 2 ways to use one of them, and 2 ways to use both. Hence dp[1] = [1,2,2,0,0,...]

  • Let’s consider 2s: we have one of them. We have 1 way not to use any of them (dp[1][j] goes to dp[2][j]once), and 1 way to use one of them (dp[1][j] goes to dp[2][j+1] once). Hence dp[2] = 1 * [1,2,2,0,0,...] + 1 * [0,1,2,2,0,...] = [1,3,4,2,0,...]

  • Let’s consider 3s: we have three of them. We have 1 way not to use any of them (dp[2][j] goes to dp[3][j]), 3 ways to use one of them (dp[2][j] goes to dp[3][j+1] three times), 6 ways to use two of them (dp[2][j] goes to dp[3][j+2] six times), and 6 ways to use them all (dp[2][j] goes to dp[3][j+3] six times). Hence dp[3] = 1 * [1,3,4,2,0,...] + 3 * [0,1,3,4,2,0,...] + 6 * [0,0,1,3,4,2,0,...] + 6 * [0,0,0,1,3,4,2,0,...] = [1,6,19,38,48,36,12,...]

Hence our array has 1 sorted sequence of length 0 (that’s an empty one), 6 sequences of length 1 (any of the elements), 19 sequences of length 2 (corresponding indices are (0,1), (0,2), (0,3), (0,4), (0,5), (1,0), (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,3), (4,5), (5,3), (5,4)), 38 sequences of length 3, etc.

1 Like
5

Thanks bro