Блог пользователя aryan0707as

Автор aryan0707as, история, 18 месяцев назад, По-английски

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

}

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
18 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

i have solved by recursive 3d dp do chek code

  • »
    »
    18 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +4 Проголосовать: не нравится

    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?

    • »
      »
      »
      18 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится

      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 ? )

    • »
      »
      »
      18 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится

      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