ICL1905 EDITORIAL

PROBLEM LINK: https://www.codechef.com/problems/ICL1905

DIFFICULTY: EASY-MEDIUM

PROBLEM

Given N planets, you can visit any subsegment of planets so as to gain profit. The costs associated with each visit are as follows:

  • For each planet you visit, you gain A coins.

  • For the i-th planet you visit, you lose C[i] coins.

  • If you visit the segment [L,R], you have to pay gap(L,R) coins such that gap(L,R)=max[(D[r]−D[l])^2] where L<=l<=r<=R.

Find the maximum profit that you can achieve.

EXPLANATION

For any segment [L,R], the profit is A*(R-L+1)-C[L]-C[L-1]-...-C[R]-gap(L,R).

To compute C[L]+...+C[R], we compute a prefixSum array where prefixSum[i]=C[0]+C[1]...+C[i].

Then, C[L]+C[L+1]+...+C[R]=prefixSum[R]-prefixSum[L-1].

To compute the gap(L,R), we may first notice that gap(L,R) is maximum when |D[l]-D[r]| is maximum. This is maximum for the case where D[l]=max(L,R) and D[r]=min(L,R) where max(L,R) represents the maximum element of D in the range [L,R] (similarly for min(L,R)). To compute gap(L,R) efficiently,we can manage the max and min for each segment while iterating over R for a given value of L.

Then the profit can be found for each segment in O(1) time and iterating over all segments, we can find the maximum profit in O(n^2) time.

4 Likes

@la_flame
i have used exactly the same approach but getting TLE.
could you tell me where am i going wrong.
https://www.codechef.com/viewsolution/30703849

link to my solution.

Solution Code: Solution: 47337317 | CodeChef

can this problem be solved in 0(n) time complexity?