Simple dynamic programming
Count the number of non-decreasing subarrays of the given array A.
How to get 20 points
Let’s choose the left bound, say L. After the left bound is fixed, let’s choose the right bound, say R. And now, let’s check that the subarray A[L, R] is non-decreasing.
In other words, let’s iterate through all possible subarrays and then, for each of them, check whether it is a non-descreasing one or not.
Choosing the left bound takes O(N) operations, choosing the right bound takes O(N) operations too, and checking subarray also takes O(N) operations. Since these operations are nested, hence the total complexity will be O(N3).
This solution is good enough to solve the first subtask.
How to get 50 points
Let’s choose the left bound, say L. Let the right bound, say R, be equal to L initially. Then while the elements are non-decreasing keep increasing the right bound R. At some moment, you will certainly stop. The amount of non-decreasing subarrays with the left bound at L will be equal to R-L+1 for every fixed L. The sum of all this values is the answer to the problem.
Choosing the left bound takes O(N) operations, and finding the right bound takes O(N) operations. Since these operations are nested, the complexity of the whole solution will be O(N2).
This solution solves the first and the second subtask, but is still not good enough to get the full points.
How to get 100 points
Let’s introduce an array B of N elements, where the ith element of B defines the amount of the correct subarrays with the right bound equal to i.
Now, let’s give the rules for calculating the ith element of B:
- if A[i-1] ≤ A*, then B = B[i-1] + 1* since every non-decreasing subarray that ends at the (i-1)th element can be continued with the ith element without loss of non-decreasingness and one more non-decreasing subarray that ends at the ith element is A[i, i].
- if A[i-1] > A*, then B = 1* since any subarray that ends at the (i-1)th element will lose its’ non-decreasingness if continued with the ith element, so the only suitable subarray will be A[i, i].
So, the answer will be equal to the sum of all elements of B. The complexity is O(N), because the computation of the array B turns out to be a single for-loop with a condition for the computation of B* inside.
Can be found here
Can be found here