PROBLEM LINK:Author: Shivam Manchanda Tester: Shubham Singhal Editorialist: Shivam Manchanda DIFFICULTY:EASYMEDIUM PREREQUISITES:DP QUICK EXPLANATION:Use dynamic programming to precompute $Fun(r,k)$ for all 1≤r≤50000. Now during the input of operations, calculate how many operations are applied at each index. For every index $B[i]=B[i]+$ (no of operations[i] $*$ (Fun(A[i],k))). EXPLANATION:Computer P(r)Let us maintain an array DP, where $DP[i]$ represents minimum fibonacci numbers that sumup to i. You can now make a recursive definition:
$NOTE:$ If you try to check all numbers (as j)less than i, you might get TLE. But as storing fibonacci numbers smaller than i will definitely get AC. Applying operationsTake an array OPR, where $OPR[i]$ represents number of operations on index i. Initialize this array with 0. Now, for every operation performed from L to R, do this:
After performing all operations, take a cumulative sum of the array from index 1 to N, as follows:
Finally, you have $OPR$ ready. Answering QueriesAs, we have computed the number of operations on each index OPR and P(r), thus query can be answered simply as:
TIME COMPLEXITY$O(N+M+Q)$ ALTERNATIVE SOLUTION:The part to compute number of operations applied can also be done using Segment Trees but in $O(n*logn)$. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 02 Oct '16, 10:41
