DP approach for BIT3D

Hey everyone…:raising_hand_man:

Here is a simple question I got stuck with:
https://www.codechef.com/BIT32020/problems/BIT3D

Can you please share your ideas for this question with DP approach…
I tried it but i am getting WA…
Here is my submission link:
https://www.codechef.com/viewsolution/34736840

I used simple N^2 DP approach as we do in very basic DP problems…
In short, I took “minimum of all possible paths”.
Can anyone tell me what mistake i did?

Thanks in advance for your valuable time :raised_hands:

1 Like

I solved it without using DP. If you want, I can explain.

1 Like

Yes…why not :smiley:

Is my approach correct? Or i messed up completely :sweat_smile:

Can anybody explain the dp transitions of this problem of the same contest (https://www.codechef.com/BIT32020/problems/BIT3C)

Approach :

for p in {odd,even} :

  1. while index < (n-k+1) {since, after that you can directly jump to n+1)
    1. traverse backward from index+k to index+1, if you find any element having parity as p, break immediately and set index as break_element_index.
      Look at my code, it will be clear.

In short, you are jumping to the last place having same parity in a group of range k.

2 Likes

Nice implementation :raised_hands:
Got it at once :smiley:

This is almost same approach which i used…
The only difference is that i traversed in forward direction, and stored minimum for each position…
But i dont know where am i going wrong :roll_eyes:
Any advice?
Thanks in advance

Actually I have calculated the minimum of all possible paths in O(N^2).

Can you please provide me a valid test case for this?

First of all, your code does not fit the time limit.
Secondly, the line if(a[i]&1==a[j]&1) is not working, replace it with if((a[i]&1)==(a[j]&1)) [Just put it in bracket].
Test case :
1
5 2
948 28 1 238 94
After putting brackets, it shows correct output. You can verify.

1 Like
        vector<int> dp(n+1,INT_MAX);  //it'll store the minimum values as you require
        //thes two multisets will store the dp values of the range [i-k,i)  according to there parity of values so that you can get the minimum in the range as per the parity of current i
        multiset<int> evens,odds;   

        //just setting up the initial values where we can reach without considering parity and inserting them in multiset as per parity 
        for(int i=1;i<=k;i++){
            dp[i]=1;
            if(v[i]%2==0) evens.insert(dp[i]);
            else odds.insert(dp[i]);
        }

       //now the final transitions begin we find the minimum in range [i-k,i) as per the parity in the multiset
        for(int i=k+1;i<=n;i++){
            //if v[i] is even well look in even multiset and after querying and doing necessary transition will add it to multiset
            if(v[i]%2==0){
                if(!evens.empty()) dp[i]=(*evens.begin()+1);
                evens.insert(dp[i]);
            }
            //similarly for odd
            else{
                if(!odds.empty()) dp[i]=(*odds.begin()+1);
                odds.insert(dp[i]);
            }

            //now the (i-k)th index won't be available for transition anymore so remove it from its respective set
            if(v[i-k]%2==0){evens.erase(evens.find(dp[i-k]));}
            else {odds.erase(odds.find(dp[i-k]));}
        }

Some things to care during implementation

Remember it’ll have minimum moves for N and we need to find for N+1 to which we can make transition from any of the last k positions so query for the minimum is the last k dp values and return min+1 as ans.
(If min is greater than or equal to INT_MAX return -1

2 Likes

Oh great… thanks for all your tips and recommendations :slightly_smiling_face:

Thanks sir for adding those comments.

Actually I saw your code just after the contest ended :grin:
~Your 1st year junior from same college :sweat_smile:

1 Like

Can you please elaborate your approach

Can you please find error in my approach
https://www.codechef.com/viewsolution/34739668
@aquantis

Nice approach!!

Actually during contest its more about getting it right so there are many conditions at the end of my code to this problem which might not be necessary as well but i didn’t want to miss out any of them so the code at end becomes confusing.Thus I added the main part with comments instead of complete code.
Hope its clear from the comments added, feel free to ask.
Its good to see juniors working hard and doing great in programming competitions.
Keep up the good work :slight_smile:

1 Like

There is an unnecessary cout<< statement in line 54
You are storing indices in the set and querying for upperbound of current index .I’m not sure if it is a correct way of transition.Do revisit your intution for using this.

1 Like

ohhh yes thank you , i got AC there was mistake in storing the index (i-k)

Here is the link to solution for problem E (DP)

1 Like

Thanks for your help… :raised_hands: