PROBLEM LINK:
Author: Shivam Manchanda
Tester: Shubham Singhal
Editorialist: Shivam Manchanda
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
DP
QUICK EXPLANATION:
Use dynamic programming to pre-compute 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®
Let us maintain an array DP, where DP[i] represents minimum fibonacci numbers that sum-up to i. You can now make a recursive definition:
for(i from 1 to 50000)
{
if(i is fibonacci)
{
DP[i] = 1;
Store i;
}
else
{
for(j in all fibonacci less than i)
{
DP[i] = minimum of all(DP[i-j]+1);
}
}
}
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 operations
Take 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:
OPR[l]++;
OPR[r+1]--;
After performing all operations, take a cumulative sum of the array from index 1 to N, as follows:
for(i from 1 to N)
OPR[i]+=OPR[i-1];
Finally, you have OPR ready.
Answering Queries
As, we have computed the number of operations on each index OPR and P®, thus query can be answered simply as:
B[x] = B[x] + ( OPR[x] * ( P[A[x]] less than k ? 1 : 0 ) );
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.
Tester’s solution can be found here.