Problems

• http://codeforces.com/contest/938/problem/E - Combinatorics, Solved
• http://codeforces.com/problemset/problem/919/E - Number theory, Solved
• http://codeforces.com/contest/901/problem/B - Next
• https://community.topcoder.com/stat?c=problem_statement&pm=14819 - Absorbing Markov Chains
• http://codeforces.com/contest/932/problem/E - Derivative
• https://community.topcoder.com/stat?c=problem_statement&pm=11510&rd=14540 - Expected Value

Tutorial

• http://codeforces.com/blog/entry/19887
• https://brilliant.org/wiki/absorbing-markov-chains/

Solutions

Problem E 939 - Max History

By concentrating on individual elements and finding the number of occurrences of it, we can solve the problem in linear time. It’s obvious that the largest element never gets added to the sum. So, for each \(a^{i^{th}}\) we need to find the number of elements that are lesser it and let \(d^{i^{th}}\) denotes that. The resultant equation is,

\(= \sum_{i=1}^n a_{i} * \sum_{j=1}^{d_{i}+1} \left(\binom {d_{i}}{j-1} * (j-1)! * (n-j)! \right)\) \(= \sum_{i=1}^n a_{i} * \sum_{j=1}^{d_{i}+1} ( d_{i} * (n-j)! / (d_{i} -j + 1 )! )\) \(= \sum_{i=1}^n a_{i} * d_{i} * (n - d_{i} - 1)! \sum_{j=1}^{d_{i}+1} \binom {n-j}{n-d_{i}-1}, multiply \, and \, divide \, by \, (n - d_{i} - 1)!\) \(= \sum_{i=1}^n a_{i} * d_{i} * (n - d_{i} - 1)! * \binom {n}{n-d_{i}}, \, by \, hockey-stick \, identity \, \sum_{m=k}^n \binom mk = \binom {n+1}{k+1}.\) \(= \sum_{i=1}^n { (a_{i} * n!) / (n - d_{i}) }.\)