Subsequence and Substring State ideas | Day 4 Part 2 | Dynamic Programming workshop | Vivek Gupta

In this DP workshop, we are going to learn many DP formulations that are going to make solving DP problems easy for you. Register today if you haven’t.

✨ Hashtags ✨
#7daysofDP #VivekGupta #dpworkshop #CPStreams #codechef #codeforces #engineering #internship #DSA
-------------------------------------------------------------------------------------------------------------

If you are a beginner, here are some resources to start with :

If you are looking to train in a commado like regime for acing DSA (with DEV and System Design covered for placement too), do checkout :

[priyanshsinghal]

Hell yeah. I seen automata theory as a waste for timeline we are living in. But that trick make the concept of FA and minimizing the FA to be alive at the present. Glad to know this way. Thanks ❤️

[amandixit]

Bhaiya umeed karta hoon trees and graph ka b aisa hi pyara sa workshop aayegi aur mein intezaar karunga please jaldi laayega kyuki mein wait karunga, khi aur se nhi padunga, , isse hum jese gareeb logo ki help ho jayegi jokes apart lagta form and variation agar pata chal jaye ki aise aise type ke mein Aisa sochna padta phir thodi journey asan ho jati, umeed karta hoon ap jald hi layege, teaching style just awesome :), mein kush naseeb jo right time pe apse dp pad liya, mene abhi tak dp kbi nhi padi mujhe itni tough nh lgi jitna log bolte the because of you bhaiya :)

[swastikjain]

I never thought of FA in this way IDK why, Thanks for the video...

[subhashchandra]

5C4=5
for subsequence the answer will be 5(5C4) for every 4 length subsequence
To create a subsequence of length 4, there are 5 positions, and we need to pick any 4 out of these 5:

The possible valid subsequences of length 4 (from the sequence of positions) would be:

Choosing positions 0, 1, 2, 3.
Choosing positions 0, 1, 2, 4.
Choosing positions 0, 1, 3, 4.
Choosing positions 0, 2, 3, 4.
Choosing positions 1, 2, 3, 4.

[peddivarunkumar]

one definitely needs a mentor like you :)

[charann]

This vedio made it - Really Thanks brother for the content, the way you generalize things is just awesome!!

[shayanpaul]

This is a great video with lot of unique techniques. Thank you bhaiya for teaching such things really grateful and enjoying this workshop, please keep making contents like this💯🙏✨

[swaruppadhi]

Thanks a lot for this idea again.Learnt another new idea.

[dank]

That subtring ideas seemed considerably harder and unthinkable than anything else. Would want to know if the bitmask and the automata way are reusable in other problems?

[zee_desai]

Is the number of strings of length n not containing a subsequence of length k= 2^n-(2^n-k)^nCk?

[redeye]

Guys this one is goes over my head. Can you suggest any reference videos for it. I don't understand that how he generate answer without matching it to string t.

[priyanshsinghal]

Can you add day 1 part 2 last problem, minimize the area of square, tearing sheet atmost k number of times at platform. I dont see to find the question on internet. Or can you share the link to that question. I want to try to code that

[lakshsachdeva]

2^n - (summation running from k=len of t till n ( nCk)) where t is the string to be matched Am i right

[devendrasinghnegi]

Hey vivek!!I was thinking that what if we have pattern of length~100 in that substring wala question then do we have to hardcode all the states?

[adityagaur]

i am struggling with atcoder-f-knapsack for all segments. what state to formulate for it

[Sandeep-zddq]

Instead of maintaining last 3 in substring can’t we go with previous idea to keep the length of matched substring and the transition would be : for same -> level+1, len+1 and if number differ then level-len+1, 0. Will it work? 🤔

[prathamjain]

Can anyone share the solution when how maths is used to solve is explained

[thekumarpriyansh]

Find the number of binary string of length N with atleast 3 consecutive 1. Iss type ka kaise hoga.

[itz_me_imraan]

I coded the problem not containing 0100 as substring in the Practice problem as u mentioned here (not as automata)..but the test cases range upto 10 power 6...how to optimize it??
The code gives correct ans only when i memset the dp everytime... But due to test case the memset should be done only once but it gives wrong answer..

[factos]

By maths it is
0 match + 1 match + 2 match + 3 match = nc0 + nc1 + nc2 + nc3.