Subscribed. This is brutal! I can barely understand and follow the algorithm, even with chatgpt, the solution and a video explanation I'm still having difficulties understanding how to apply this approach to another problem like counting all occurrences of lowercase characters (a-z) in a given string. Masking is extremely powerful and is a must-have tool, so thank you for the video!
Gonna take a break from doing videos for those and easy problems I think. Easies don't really need a video and contests is just too many weekly problems with the work I currently have.
I had an interesting problem where I accidentally derived this algorithm. The question was to place each number of an input array into one of 2 arrays as you go, depending on which of the 2 arrays had more elements strictly greater than the current number at the time. I tracked a sorted version of each array, comparing the bisect.bisect_right index relative to the size of the array to get the strictly greater than count and then using bisect.insort to insert into the appropriate sorted array. The funny thing is I did that recently and didn't see the application it had to this problem haha
Arriving at that intuition is key. I started with a subset based solution, got TLE, did early pruning and returns with memoisation if we already have a result. Still got TLE. I guess this is more like a math observation question
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.
I created a if-else hell for directions it works just as the simulation says, but I wonder how what can we do if the inputs were large ? Binary search or something ?
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.
12:15 for this subproblem shouldn't the result of this be 3 (just write e's then replace with T and D)? If you remove the first e then split it into TE and DE woudln't that return 2 + 2 which is 4? please correct me if i am wrong
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.
What if do something like this : We convert all -1 nodes into 1 and we try to save the shortes path. When we get the shortes path, we will travers it backwards and check if any of the edges is -1. We can add the difference between the shortest path and target to the first edge that was originally -1 For the rest we can update them with the MAX
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 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.
Just my intuition from what you have explained so far correct me if I am wrong. So for printer(i, j) it returns the minimal number of operations needed to print characters from [i, j]. In the for loop you are splitting whenever we see a matching character with our start character in the remaining string form [i + 1, j]. In that case we know that we could possibly achieve a lower number of operations for printing the first part [i, k]. The reason why we pass in dp(i, k - 1) is because when we have matching characters we are assuming that at index i we are already printing a sequence of similar character from i until index k inclusive. (i.e. "aba", when 0 == 2, at that instance we assume that we printed 'aaa' already, we actually only really consider the cost of printing 'ab' -> when we print 'a' -> 'aaa' and then when we print 'b' we are actually replacing the middle 'a' -> 'aba'.
I think it would be a good add on to show why a greedy method won't work here. That being just match the first occurrence with the last occurrence of the character trying to cover as many same characters as possible. Apart from that, excellent explanation
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.
Quite a bit of edge cases in this problem, I was able to get to the reversing the first n/2 digits and subtracting and adding 1 to the significant bits but eventually gave up on trying to search for measures that would take care of these 101 and 99 cases. Glad I was able to come across your video! Great explanation, I wish you all the best in everything that you are doing. Thank you tons for posting content that helps people like us!
Thanks! This solution is by far the clearest one I have seen on RU-vid. But is there any way to build the intuition for those kind of problems? Actually by observation, I can see that for most questions that requires counting subarray, sliding window is basically the way to go. My intuition was sliding window too when I attempted this problem, but I have no idea how did you come up with the 3 pointer approach. Any insights on this?
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)
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.
That's a really great explanation! The only part I'm a bit confused about is why this algorithm correctly handles strings where there are groups of letters in the middle of the string that are the same as the first letter. For example, "abaac".
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.
Thanks for the video but actually you start at the end because you recurse to the end of the string with the line 27. I think It would be better if you explain from backwards.
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?
@@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
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.
I really like the way you explain this! You basically did a breakdown and then explained each part of your code that shows the breakdown steps and it all took about 15 min! Thanks man, I hope to see more of this! Edit: Also, not many resources do this in java!
I have doubt in our example when we will return hundred as the Alis score. At that time, we are taking minimum of our result and recursion call at that time. Bob will return minimum of hundred and his score. Can you explain how we are ensuring that Alice will get maximum I am a little bit confused. For bob min(result,100) in his case, we will end up with minimum score of bob
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.
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.
