Editorial for DMOPC '18 Contest 2 P5 - Another Sequence Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: r3mark

For the first subtask, dynamic programming suffices. More specifically, let dp[n][m] be the number of sequences with n elements and sum to exactly m. It is easy to see that dp[n][m]=\sum_{i=1}^K dp[n-1][m-a_i]. So transition can be done in \mathcal{O}(K).

Time Complexity: \mathcal{O}(NMK)

For the second subtask, some math (e.g. generating functions, stars and bars) yields a closed form. It is well-known that the number of ways to add n non-negative numbers to sum to s is \binom{s+n-1}{s}. So the final answer is going to be \displaystyle -N+\sum_{s=0}^M \binom{s+N-1}{s}The -N is because M is not in the set. Then by the hockey-stick identity, this sum becomes \displaystyle -N+\binom{M+N}{M}.This can be easily calculated in \mathcal{O}(M\log M).

Time Complexity: \mathcal{O}(M \log M)

For the third subtask, note that there are at most M non-zero elements in the sequence. Using the dynamic programming solution from the first subtask, we can compute the number of sequences without using any 0's using a certain number of terms in \mathcal{O}(M^2K). Then with a little math, we can find the number of sequences which have a certain number of non-zero terms and the rest 0.

Time Complexity: \mathcal{O}(M^2K)

For the final subtask, we use the \times 2 ,\ + 1 trick mentioned here. If dp1[i] is the number of sequences of length n which sum to exactly i and dp2[m] is the number of sequences of length 2n which sum to exactly m, then \displaystyle dp2[m]=\sum_{i=0}^m dp1[i]\cdot dp1[m-i]. A similar formula can be found to calculate the number of sequences of length n+1. So instead of checking all n's, only \mathcal{O}(\log_2N) are necessary. Note that this is equivalent to exponentiation by squaring and is much more obvious if this problem is interpreted as a matrix multiplication problem or interpreted with its generating function.

Time Complexity: \mathcal{O}((M^2+MK)\log N)


Comments


  • 2
    BaturaDima  commented on Oct. 12, 2018, 10:51 a.m.

    Can you describe second task solution more concrete? And provide correct time compexety for it.


    • 0
      r3mark  commented on Oct. 12, 2018, 4:10 p.m.

      The derivation of the answer has been provided and the time complexity has been fixed. I treated the modular inverse operation as \mathcal{O}(1) in the original time complexity.