Video

Yeah, but its like basic math. I can see how going down a dp route would make sense but then you need to keep track of an index and a total which is probably n^2 so would fail.

Would definitely be interesting if that were the case, we would basically have to figure out if we can go from a to b with no obstacle in the path in log(n) or better time. Something I'm thinking of is like maybe have a prefix sum of obstacles in the grid or something row by row and column by column that we can probably bin search with. So if you check obstacles at b vs obstacles at a we should have the same sum if there are none in the path then you can bin search through that space to find first place where it differs maybe. This would work if the obstacle numbers aren't too big but we have a lot of commands and the commands aren't 1-10 but like 1-10^4 or something.

Proof can be thought of in a couple steps: a. If we replace every single -1 with a 1 and we don't achieve this, then it is impossible and we are done. b. provided a is possible, if we replace one edge at a time we will eventually get to a point where the weight of the shortest path <= target. c. when we achieve b, we know for sure the last edge we added was necessary in order to do so (since without it we were not able to) and every edge we have not yet added is not required anymore. d. if we increase the weight of the last edge we added to make the path == target, there can be no shorter path because this edge has to be included in the shortest path from c and every path with this edge will increase equally. e. we can then make every edge not used = infinity to make sure this remains the shortest path.

Yeah ur right should be 3. Splitting the way I showed in the video will be 4 but optimal is 3. Best split is getting rid of the last character right away then you have TEDE which then can split into TED and empty string so we get 3.

@@tanishgotti3659 to know exactly which nodes turned on produce a valid shortest path.

I did something similar in my Python solution. you can do that also. Save all paths during the Djikstra and sort by number of -1's then the path length. Then make one of the -1's in the path the difference and MAX the rest. Since n is only 100 its fine to save entire paths in the heap as you are finding shortest path. Don't need to go backwards just make every -1 into a 1 and add them all to graph and store (#of negative ones, dist, nodes in path) in the heap and use a min heap.

You can't pick the first edge that was originally -1 every time and expect it to satisfy. Picking different edges in the backwards traversal might give a different shortest path because other nodes in that path will be 1 now. See this test case: "edges = [[0,1,-1],[2,0,2],[3,2,6],[2,1,10],[3,0,-1]] source=1 destination =3 target =12" "[[0,1,1],[2,0,2],[3,2,6],[2,1,10],[3,0,11]]" is wrong "[[0,1,11],[2,0,2],[3,2,6],[2,1,10],[3,0,1]]" is correct.

@@tanishgotti3659 I did same mistake in my code

@@hittarthgoyal6689 this was a tricky corner case.

@@tanishgotti3659 that's why you set the last -1 value you turned on to be target - shortest path to make sure it is the same once you get one smaller than target i.imgur.com/lyzG1U3.png and every node outside the path to MAX. Seems fine to me either way, your values were just wrong I think. In your first set of edges you just set the -1's incorrectly.

@@berserk.4121 yup I mentioned that in the video and said I don’t want to modify inputs

@@chrisgu7991 yup sounds right to me

Can use pre sometimes just need to understand the traversal order that you need for a particular problem.

yea, ive seen a few like this before but hard to come up with all the edge cases. I think for some other ones I could build all palindromes and binary search through them or something.

Yeah this one was pretty annoying :)

You have to know what 3 pointer is useful for as opposed to 2 pointer. You can do all sliding window problems with 3 pointers, just usually the third one is redundant and doesn't give any extra information. So once you get how the third one helps, you can start asking yourself do I need it when you do the problems or do 2 give me all the info I need.

@@Alpha-Code Thanks! I will try to delve in into how the third pointer is redundant in most cases but useful in this one. I just have one more question though and this is sth that I have been stuck when dealing with this problem - why is res += (min(lastMin, lastMax) - start + 1)? I don’t quite understand how come sth like (r-l+1) could be the number of subarray to add. How come in this formula we can find the number of subarray that fulfill the condition of the fixed bound? Sorry if this seems a little bit confusing, but I am quite lost about how this formula actually applies. Is there a mathematical way to think about this? And possibly how to apply this in other questions (e.g the scenario)?

@@victor-fo9zf (min(lastMin, lastMax) - l + 1) is used cause you have to include lastMin and lastMax in all valid arrays so you take the min as this is the smallest array that includes both. Then anything that starts from there to start is a valid subarray if they end with r. And r - l + 1 is cause the number of arrays between 2 indices is r - l + 1.

@@Alpha-Code I think an example may help with what I am trying to understand here: Suppose we have like nums = [1,5,5,1] and minK = 1 and maxK = 5. We initially know that boundary is at index 0, and it is all good from the first three index. We have res = 2 and the respective subarray are [1,5], [1,5,5]. However, I get a little bit confused when we are iterating at the last index. Now, minK reached to index 3 and maxK is on index 2. We do the calculation (2-0)+1=3 and res += 3. I know this is valid because in my observation, the corresponding subarray are [5,1], [5,5,1], [1,5,5,1]. How come the math kind of “knows” that there are three subarray for this case?

@@victor-fo9zf min of last min and max is 2 so that means that for all arrays that end at r, they have to include index 2. So any array from l onward that includes index 2 that goes to r is valid. So 0-r 1-r and 2-r is valid. Math works out cause we updated bounds of valid arrays and can calculate how many end at r in O(1)

You're supposed to combine (add or subtract) fractions. Ex: 1/3 + 1/3 = 2/3

Yeah I can spend more time on that sure. Thought this one was pretty clear just add fractions and simplify answer. But I'll spend more time on problem descriptions in the future no worries.

for that one you look for all characters that match starting one so abaa matches which would go down to aba then that goes down to ab for 0 cost. I explained something similar in the updated video for this problem.

@@Alpha-Code You're absolutely right! Thank you. The reason I couldn't figure it out was that I was building the decision tree incorrectly. If anyone else has the same question I did, try building a decision tree using a simple example.

in line 27, it's recursing to the next character from the front. From i, j to i+1, j where i is front and j is end. Can do backwards or forwards should be the same so forwards just seems more intuitive if it doesn't matter.

@@Alpha-Code I meant, the line 27 will be executed to the end of the string when i and j are same so you actually split the string from at the end of it. Am I wrong?

@@MehmetDemir-xi3yy You can split from front or end but in this case it splits from front, you can log i and j and see for yourself though.

@@Alpha-Code for input "abcabc" when you add this line below to line 30, "System.out.println(s.substring(i, k+1));" you will get output as cabc bcab abca so you are doing from backward to forward

@@MehmetDemir-xi3yy Put that line at the top of the dp and just print i and j. Here's what I got for "abcabc" but either way result should be same imgur.com/IBOM5hR

@@vishaalkumaranandan2894 czcams.com/video/uAraW9iGmRQ/video.htmlsi=ML0XFaIiQeUmB7jf new one with dark mode

Yeah I mostly write the code live. This one wasn't too long so probably could have done it. For the long ones, I prefer to write it ahead of time so the videos aren't like 30+ min.

The idea is in our function we are never calculating Bob's score. On Bob's turn we are simply returning the minimum for Alice given all the moves Bob can make. And on Alice's turn we are returning the maximum for Alice given all the moves that she can make. The function returns Alice's score given they both play optimally without calculating Bob's score at all, because the less points Alice gets the more Bob gets. So we can just focus on 1 score. So for example 2 you are referring to, the optimal play is Alice takes pile 1, Bob takes pile 2, Alice takes pile 3, Bob takes piles 4 and 5, and Alice takes pile 6. Alice's score is 1 + 3 + 100 from that = 104.

@@Alpha-Code thank bro got it

You should do easier dp problems until you can create your own solutions then once you can do easier ones yourself consistently try slowly increasing difficulty. Start with some really basic ones where you have some basic choices to make like go down or right or something. Then go to mediums then go to hards.

excalidraw

@@Alpha-Code Thank you!

Haven't done contests this week. If I do them later on during the week, I'll post them.