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}) }.\)