I managed to find a recursive solution which gives tle for last test case of second subtask and first test case of last. This is because I couldn't find a way to cache the computed value so there was repitition of calculation.
My process included finding all possible negatives in pairs and then taking triplets to find all cases that produce negative sum . I take the negatives only in a seperate array and all I now have to do is find all combinations in which no two negatives are adjacent .
Here is the link to my solution(20pts) : www.codechef.com/viewsolution/18569209
I do understand all I have to do is store the best possible sum from index i to n-1 for every index i and also the array traversal which has to be stored in a 2d array for every i in every row. I do not understand how to do it. Please help.
Asked by: Liman_Rahman on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
hello, liman
first, the below test case give tle for your code.
1
200
1 2 1 2 1 ...
DP SOLUTION :)
I am going to explain you the top-down approach. we need two dp arrays like dp1 and dp2 in which we can store the best answer for a prefix of an array. in dp1[i], we store the best result of prefix up to index i if the element at index i is going to be negative in answer and in dp2[i], we store the best result of prefix up to index i if the element at index i is going to be positive in answer.
first, you have to initialize both the dp array with INF and then define a base condition and then write the recurrence relation. you also need two cnt arrays to store the sign so you can backtrack your solution.
base case:)
if(a[0] >= a[1]) dp1[0] = -a[0];
dp2[0] = a[0];
recurrence relation:)
dp2[i] = min(dp1[i-1],dp2[i-1])+a[i]
dp1[i] = min(dp1[i-2],dp2[i-2])+a[i-1]-a[i] // as two consecutive numbers are can't be negative.
for dp1 you have to check two coniditions:
1. a[i] is strictly smaller from both it's neighbours.
2. the consecutive sum of three elents should be positive.
ok, that's all you need for implementation of this question. I hope you will understand.