Change signs (CHSIGN)

dp codechef chsign

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.

 

liman98
Liman Rahman
liman98

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

1 Answer

rishup132
rishup132 19:07, May 17
Ritesh Gupta

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.




Please make sure the answer is not too short
1 Upvotes
Comments
liman98 (Liman Rahman) 19:41, May 18

if(a[0] >= a[1]) dp1[0] = -a[0]; Shouldn't it be : if(a[0]< a[1]) dp1[0] = -a[0]; ?