Array Walk || Educational Codeforces Round 92 || CODEFORCES || DYNAMIC PROGRAMMING

question link : codeforces.com/...
Telegram channel link : t.me/joinchat/...
Instagram link : www.instagram....
solution link : codeforces.com/...

[@sangraampatwardhan1573]

Hey I have a doubt, it was mentioned in the question that we can't do two or more consecutive left moves, how did you take care of that condition?

[@ramanmanocha4800]

Exactly I have the same doubt

[@av1shekps]

Me too same doubt

[@codeExplainer]

For two consecutive back condition, I think that case will not occur because it will go back only when it has encountered a large number. Like in 1,3,5,4,2 it will go back after 5 but when it goes back it will move forward because that large number can be added again.

[@sangraampatwardhan1573]

@@codeExplainer so the condition was redundant 😂

[@crossover7460]

@@codeExplainer God level thinking

[@ayushagrawal258]

For two consecutive back condition, I think that case will not occur because it will go back only when it has encountered a large number. Like in 1,3,5,4,2 it will go back after 5 but when it goes back it will move forward because that large number can be added again.

[@codeExplainer]

yes true , you are right , because dp do it optimally and thus it will never happen it will back in LL fashion.

[@priyanshigarg9254]

If the array is 1,6,5,4,2 ,, then will it go from 4 to 5 and then from 5 to 6 ?

[@ayushagrawal258]

@@priyanshigarg9254 nope. It will go like 1 then 6 -> 5 -> 6 -> 5 -> 6. It will give a sum of 29 in 5 moves including 2 backwards moves.

[@priyanshigarg9254]

@@ayushagrawal258 Thanks for clarifying 😊

[@prijwalrajavat5811]

Also, you can't perform two or more moves to the left in a row. , how this code is handling this line ?

[@gauravkasat4467]

exactly

[@vamsia5543]

It does handle that case becoz first we are moving towards right, when that recursive call is exhausted then we move towards left .If we were to move that left recursive call first then it means you are moving >=2 steps towrds left which is wrong

[@rbiswas876]

@@vamsia5543 suppose recursion goes as follows : LLLL LLLR LLRL LLRR so here two LL moves can occurs

[@gauravkasat4467]

@@vamsia5543 didn't get your logic

[@prijwalrajavat5811]

@@vamsia5543 got that, thanks !!

[@tushargupta764]

Can you show tell me an example where we move left two times or will it never happen ? Thanks nice explanation

[@codeExplainer]

Yes we can. For two consecutive back condition, I think that case will not occur because it will go back only when it has encountered a large number. Like in 1,3,5,4,2 it will go back after 5 but when it goes back it will move forward because that large number can be added again.

[@ishaankaustav727]

it should be k-1 in ok function because we had already made one move while coming from 0th index to 1st index ?

[@dineshbs6635]

Wow, the approach is clean. I got the recursive solution and got tle same as you. But i failed to realise that it is a dp.

[@codeExplainer]

hahahah , no problem , keep practicing and u will also learn new things daily.

[@rushisatani3170]

Thanks for the solution buddy Much appreciated 🙌

[@codeExplainer]

No problem 👍 . keep coding , and I am there for your help.

[@Abhishek-Jain]

Bhai memoization ka best resource kya hai?

[@codeExplainer]

u can view my dp series , or code n code videos are also good. and go to gfg dp problem page , and there are a lot of prob there, solve them and learn along the way..

[@MdZeeshan-gd1nw]

The dimension of dp should be [n][m][z] ie 3. bcoz the ans will depend on what moves was taken previously ie.( right/left)

[@codeExplainer]

i have explained in the video , in every step k is decreased and we only have to see the variables , which defines a state , but k is decreases in every case , and thus it cannot be used . u can also understand that dp[n][m][z] , cannot occur because the size of n and m are 10^5 and thus u cannot make a array 2 values , which are that much large .

[@MdZeeshan-gd1nw]

@@codeExplainer sry ,we need to make dp[n][z][2]. where 2 is used for left and right.

[@VishalYadav-gk1kg]

Very nice explanation sir, Thank you!

[@codeExplainer]

Most welcome!

[@chinmaym7479]

What about 2 consecutive left moves...I think there should be another Boolean state of last move

[@codeExplainer]

More than 2 consecutive left move will not occur in such case. and that case will be taken care by dp approach . also as we can move total of z back , whenever i move left , i decrease the total z.

[@rashmiagarwal7312]

Very nice... Good luck shivam 👍🏼👏👏

[@codeExplainer]

Thank you so much 😄

[@IzIGaMerTube]

i >= 0. If youre i = 0, then arent you supposed to get a segmentation fault since the ok method will go to the left (i will become -1)?

[@codeExplainer]

but i-1 will not be processed . it will just be returned , to do any processing in ok function u have to undergo some base base. and that base handle this cond of yours.

[@girishgarg2816]

I thought of a greedy approach. We will find the maximum adjacent pair sum from the first k+1 numbers (Since numbers after the k+1 th position are useless). Then we will iterate through the array to our maximum adj pair sum position and try to exhaust all our backward moves there. If k is exhausted before z, then we get our ans. Otherwise if z is exhausted first then we shall move forward until k permits. How is it? I tried implementing it but it showed WA

[@avikmallick9037]

I thought of exactly same, but stuck on implementation

[@shivamgurjar8979]

Thank you very much .

[@nisarggogate8952]

I think you forgot the condn that there cant be more than two consiquitve moves to the left

[@nisarggogate8952]

Got it my bad

[@tushargupta764]

@@nisarggogate8952 Can u explain a little

[@shubhampokhriyal8491]

Can you explain how his function is taking care of two consecutive left move??

[@siddharthmagadum16]

Can you explain???

[@kongzilla2897]

@@nisarggogate8952 can u explain?

[@shethnisarg3049]

please keep making such videos..helps a lot

[@codeExplainer]

Thank you, I will.

[@mayankverma3690]

brother can u please make a video on recursion? like how the values are stored in stack ?please make a video on recursion

[@codeExplainer]

ok noted , i will upload it soon , thank u for the suggestion.

[@visnunathan2153]

is it not necessary to check for the multiple backward traversal bro? like we cant move backward twice from a particular index will that be satisfied in your approach?

[@codeExplainer]

we cannot go more than k back and as u can see in the recursive function , if i go back , my "zz" is decreased , and thus it will keep on decreasing , also this is trick thing in the question , that we should not move more than 2 back, but that case wont happen actually , in real u will only not go back more than 2 times consecutive . u can get this if u write it on paper.

[@visnunathan2153]

@@codeExplainer For example if I am at index 4 and still my z value is 3 then I can move to index 3 or index 5 from index 3 i will again have the possibility to move front or back as my zz value will be 2 if i choose the path of moving backwards will it not move backwards twice?

[@girishgarg2816]

against the question. Once we move back, our next move has to be forward

[@visnunathan2153]

Girish Garg will this approach satisfy what u said bro?

[@girishgarg2816]

@@visnunathan2153 "In a row" means "in succession", i. e. "you can't perform two or more moves to the left in a row" means that if your last action was "move to the left", you cannot move to the left right now (you can move to the left only after moving to the right).

[@cyrusthapa4149]

Bhai maza aagya 🔥

[@codeExplainer]

welcome..

[@nileshkumar9679]

Thank you bro nice explanation please make video yesterday div-2 problem

[@codeExplainer]

sure , i Will make on it also soon , stay tuned.

[@TahsinAhmed-yj9ns]

Awesome approach!

[@codeExplainer]

Glad you think so! tc . keep coding.

[@ANUPKUMAR-cn7vq]

bro please explain bottom up approach as this is easy to think but bottom up is very tricky

[@codeExplainer]

u can watch secondThread video for bottom up approach . u will understand more from there.

[@ANUPKUMAR-cn7vq]

@@codeExplainer link ? of second thread plz

[@Page_Turners_Hub]

Do you stammer ? Anyways, your videos are helpful..🙂🙂

[@codeExplainer]

i m trying to be good in english speaking.

[@nikhilkumar-ot9rn]

awesome bro !!!!!!!!!!!!!1 keep up the good work!!!!!!!!!!!!

[@codeExplainer]

Thanks! I will try my best. keep practing

[@ajinkyakharosekar8580]

Good explanation..Thanks...

[@codeExplainer]

You are welcome . keep coding and keep learning.

[@aj-zv1zk]

Bro if i= n-1 how will u make right move?

[@vamsia5543]

if i is n-1 then you will add the value and make rec call to right then u notice that you've reached i==n which is the base case handled above then you return to previous state. So youre not making any further step to right

[@aj-zv1zk]

@@vamsia5543 thanks

[@codeExplainer]

True , Vamsi A has explained it well .

[@madhavnagpal1860]

you have not understood the problem , you can't move consective lefts

[@codeExplainer]

i understood your point , but by the dp approach , that case wont happen , because it will take care of that case. also u can see even if u go back my zz does not become new again , it is decreased with every left move and thus if u move back my zz decrease by 1 every time and thus in total i can move a total of k back max.

[@harshitagarwal9026]

Thanks bro

[@codeExplainer]

Welcome.

[@mohamednasser3249]

the solution gives me MLE on test 3

[@mohamednasser3249]

got accepted after making the array globally

[@codeExplainer]

I always provide solution which is working.

[@prabhusubramanian1205]

Waiting for prob C solution bro!!

[@codeExplainer]

Sure , it will be uploaded soon.

[@av1shekps]

@@codeExplainer you missed to tell which condition will take care that we can not move two times left continuously.

[@harshgarg7025]

Bro, you are just a pupil on codeforces and you have teaching. That's doesn't make any sense. P.S. - But you are explaining concept very nicely.

[@siddharthmagadum16]

Might be he is learning the concepts by teaching others. Bcoz if you teach a concept to someone, you will remember it for a longer period time.

[@codeExplainer]

Wow , I know but surely I will improve my rating , no worries i want the best for you . keep practicing . Ranking is just a number before the placement . I love to participate and post solutions.