problem -> https://www.codechef.com/problems/ANTISM?tab=statement
In this problem, I know that a prefix and suffix approach can solve it, but I am struggling with the dynamic programming (DP) approach. I have tried to understand many solutions that use 4D or 5D DP, but I still haven’t been able to grasp them. Can anyone explain how to approach this using DP?
My recursive DP gives a TLE because it involves the sum of the subarray. Here's the structure of my recursive function:
f( i , picked_first_element , left_one_element_in_middle_after_picking , pick_one_ele_after_leaving_one_in_middle , sum_of_ele_picked_right_now , picked_anyone_ele_such_that_its_b[i]==1 ) {
// code accordingly // gives TLE due to "sum" variable
}
Auto comment: topic has been updated by aryan0707as (previous revision, new revision, compare).
i have solved by recursive 3d dp do chek code
Your approach is :
You need to pick some elements from the array a, but with a specific constraint — once you start picking elements, you must leave at least one element i.e unpicked in the middle before transitioning to the final segment.
In other words, your selection should follow this pattern:
[start picking] ... [leave at least one element] ... [start picking again]
gap 0 -> gap 1 ( when picked the st ele ) -> gap 2 ( when left 1 ele ) -> gap 3 ( when picked one ele after leaving )
These conditions must be strictly followed throughout the selection process.
The same logic applies to the fun1 function as well, with one additional requirement: among the selected elements, at least one element must have chek[i] == 1. This is necessary because it allows you to increase the total sum and possibly reach or exceed the target value X.
Am I correctly understanding your approach?
is it possible to have only one recursive function for this
f ( i , gap , picked_any_one_b[i] = 1 ) and do the same task ?
and to remove " sum " variable in order to avoid TLE u made a dp to have maximum sum , rather than dp on min operation required and then calculated the operation needed with maximum sum
so the dp approach is changed from " min operation " to " max sum " and then calculate the operation needed explicity ?? ( and that is how this majority of dp problem r being solved ? )
solve in a single fun1() just need to call it two time for the first case i already assuming we have taken atleast one 1 . chek the code code
Yeah, now it's more clear and intuitive since fun1() can handle both the cases
while solving for first time i didn't realized that it can be do simply by making one = (1 already take it during calling fun())
yes i just wrote separately for fun() it just check we can get a sum val >= x which result 0 change (no one needed) and the fun1() for taking at least one 1 to able to change that number
ok , Thanks for ur efforts !