OPRTNS - EDITORIAL

easy-medium
editorial
fibonacci
nkcb2016
oprtns

#1

PROBLEM LINK:

Practice

Contest

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*=B*+ (no of operations* * (Fun(A*,k))).

EXPLANATION:

##Computer
Let us maintain an array DP, where DP* 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* = 1;
		Store i;
	}
	else
	{
		for(j in all fibonacci less than i)
		{
			DP* = 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* 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*+=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.

RELATED PROBLEMS: