for all I know (I have rating of 2194 on cf) for any solution to this problem, we would need to find first x[j] greater than y[i] for all i=1..n and we would either need to sort y, or do n binary searches. We can't do n binary searches in O(n) time, and we can't sort general array in less than O(n log n), but what we can do is use constraint that y[i] < 1e9 and use radix sort(basically 2 count sorts in this case, but for numbers not up to 1e9 but 1e4.5, so linear time since n is up to 2e5), but this feels very unsatisfactory and leaves savory taste in mouth, so I would leave this problem at being O(n log n)
I believe you're correct. I made that challenge after briefly thinking of a solution where we can precompute the j values using 2 pointers. However, I realize that this depends on the Y values being sorted. I've removed that from the description. Nice catch!
You are forgetting that radix sort is linear in the length of the list only if the length of the keys isn't tied to the length of the list. The time complexity of radix sort is O(w n), where w is the length of a key. In this case we have that w = O(log n), thus radix sort has the same complexity as quicksort.
@@naghus_cat according to statement, all numbers are less then 1e9, so w = log(1e9) = 30 = O(1). Then technically radix sort would be linear. If we treat 15 bits as 1 digit, then we will only have 2 iterations of radix sort. Of course all of that works only because of the constraint y < 1e9
@@rwarazor Although I would like to agree with you, that is a trick you can't apply when doing algorithm analysis. Applying the same logic I could sort the list in constant time, because n
Damn I had to read this comment to see that he had only 606 subscriber. His video quality feels like 3b1b, who has a lot more subscribers. He has 607 now :) props to him, I am sure the number of subscribers will explode soon. Amazing how this was his first video
I solved the problem much differently and pure mathematically before watching the video. it is very hard to explain a solution in text form but the main idea was to see the portals as binary numbers. I split the problem into two. evaluating how many times the player has entered a portal (to teleport not passover) and then calculating the total distance traveled. The second problem's solution was easy I just had to calculate the difference in position between the portal and the teleportation target to calculate the "cost" of the teleportation. the total length of the line plus all the costs were equal to the total distance traveled. now for the solution to the first part, look at the first example with 4 portals (red, orange, yellow, green). in the solution of this part ignore all the distances. if you look at the first red portal it teleports the player right behind itself and is thus equivalent to a binary number with one digit. orange also is a one digit number but yellow perfectly encapsulates orange but no other portal so they collectively create two digit binary number. green is encapsulating the entire one digit and two digit numbers. green is not symbolized as 3 digit but (1 + 2)+1 digits. plus operation is not summation in this notation but symbolizes that those two numbers have to be calculated independently. so collectively the table for the puzzle is 1+2+(1+2+1). we have to take the initial positions of the portals into account. the first one digit portal is closed so it has the value of 1. notice 1 is the maximum value a one digit binary number can hold so the next stop over it will pass it. orange and yellow collectively two digit number seems to have the value (0x01=1) but you can observe they act as inverted. so actually they have the value (0x10 = 2) of 2. and lastly green was symbolizing the entire copy of the puzzle plus itself but when the player passes it, all the portals will be open. so the value for green is (0 + 0 + 0) binary digit table = 1+2+(1+2+1) initial value table = 1+2+(0+0+0) we are close to be able to calculate total teleportation count. just remember that one digit binary numbers can hold maximum of 1 and leak for the value of 2. similarly two digit numbers can hold the maximum of 3 and leaks for the value of 4. binary digit table = 1+2+(1+2+1) initial value table = 1+2+(0+0+0) max value table = 1+3+(1+3+1) difference table = 0+1+(1+3+1) when we sum the difference table 1+1+3+1 = 6 you can see that player will teleport 6 times. conveying the idea behind these tables isn't that easy in text form so if they are not clear try to read it again and calculate them by yourself this is the best that I can do. lastls we have to calculate the costs. as I said calculating the cost for a portal is easy we have to calculate the distance between the portal and the target but when we unite two portals into a multi digit number since the two portals creating that multi digit (in this example two) number can have different costs we have to symbolize them independently. for this example in the case of orange and yellow portals, their costs are 1 and 3 so we will notate them as (1+3) for the 2 digit number. this says that if the player enters the first digit the cost is 1 and if it enters the second digit the cost is 3. we need to somehow evaluate how many times which digit will flip while counting in binary. I will calculate that for the general case later but for two digit binary (00 10 01 11) the first digit will flip every time and the second digit will flip every two times. collectively first 4 times and second 2 times. let me write the tables again this time with the cost table too. cost table = 1+(1+3)+1+(1+3)+7 binary digit table = 1 + 2 + (1 + 2 + 1) initial value table = 1 + 2 + (0 + 0 + 0) difference table = 0 + 1 + (1 + 3 + 1) total cost table = 0+(1+0)+1+(1+3+1)+7 = 14 total distance travelled = cost + distance = 14 + 9 = 23 the reason for the cost for the second two digit number to be not (1+3) but (1+3+1) is because while counting 00 10 01 11 first digit is flipped from 0 to 1 twice and second digit once. thus when the binary digit table is constructed total distance traveled can be evaluated mathematically with near zero computational cost. I have spent around 2 hours for the solution and an additional 2 hours watching the video and writing this comment. I'm very happy if you have read it to here and I hope you like the solution. have a nice day.
I'm shocked that this is the first video on this channel, the quality is something I would expect it to take months or even years to achieve. Can't wait for the next one!!!
i'm completely shocked that this is the only video this channel has posted, this is incredible. thank you for putting in the work to make free educational resources
As a green coder (1200-1400 CF) I can say that I understood the 2200 rated problems solution proving that this guy have put a great work into his explanation!
I really liked how you showed how much DP speeds things up at 7:18. I also like how you cut off the music at 6:37 when making your conclusion. One criticism I have is you sometimes show graphics on the screen only while you talk about it, so it's hard to visually digest what you're showing and listen in that short time (ie sometimes it's a bit fast such as at 5:30)
Awesome video. I noticed this is your first on RUclips, I hope you keep it up! Really tough problem but you explained it well. Always wished there was a 3b1b for data structure and algs. Could be you.
The quality of this video is amazing! I really liked how well you made the music sync up to the algorithm at the end with a satisfying ding every time the cost was calculated. The part at 10:30 felt a bit rushed though, I had to rewatch and study your python implementation to realize why exactly you needed to binary search to find the index of the ps array, but other than that it was an excellent video and a delight to watch.
Yeah, I too needed a lot, and I mean, lot of thought to understand why a binary search was needed. It's a good thing though. I don't want to be this failure programmer who watches videos with an off mind but can't code or think anything himself. I like this!
Great video. One thing I liked about this is that it didn't break-down the solution, instead it just introduced the ideas and let the viewer understand it by though. I loved this methodology for this problem is particular, but you may run into issues doing this with much more complicated problems.
So I might have taken your challenge to solve this problem in O(n) a bit too seriously. It took a variant of counting sort to allow building a hash map from each exit to the closest entrance in O(n), so we can skip the binary search and replace it with an access to the hash map in O(1), thus resulting in a total complexity of O(n) (where n is the length of the road rather than the portal count, though).
I did something similar. No hash, just a simple array, with an element for each node, storing the steps needed to go from the start to that node, assuming all portals are open.
@@Palparepa I also thought of doing that at some point, but I wanted to respect the 256MB limit for the challenge, which I believe this solution can't satisfy with roads up to 10^9 in length. Congrats on O(n) time complexity anyways !
3000 subscribers? no way, this is an amazing work. And i want to say that in the bisect method we can specify "Lo" and "hi" parametres(the start and end indices in the array where we want to search our element), so if we're in portal X[i] and go out in Y[i], we don't need to search all over X to find a nearest portal, we need to search in X[from 0 to i], so if we specify bisect(X, Y[i], hi=i) time complexity for all calls will be: log(1)+ log(2) + log(3) + ... + log(n) = log(n!) n / 2 * log(n / 2)
What's the point of "improving" O(nlogn) to another O(nlogn), when the optimal solution is O(n)? Just find a way to avoid bisecting at all, as it's unnecessary
@@Splish_Splash after reading the problem on codeforces i realized the video is slighty imprecise. it gives the impression that there is only one variable n, the number of the portals, and the length of the track is always 2n. instead there are two variables, n = "no. of portals", M = "length of track", with 2n
Hats off for the informative video, good stuff! I can't implement binary search off the top of my head for the life of me, not having actually ever done it. Caught that pattern at 2:14, the movement straight up looked like counting in binary with variable offsets. Fascinating.
Binary Search: Assume array is sorted and you have access to the size. Define lower/upper indices to be 0 and size() - 1, respectively. Sum the indices and divide by 2 (integer division), this is your mid index. Is A[mid] equal to your value? If yes, then we're done. Otherwise, if its smaller, then the upper index becomes mid index - 1. If its larger then the lower index becomes mid index + 1. Loop. Stop the loop if lower > upper (value doesn't exist in array).
I really appreciated this video. I paused at the 2 minute mark, solved it myself in O(n log n), and then saw that I came to the same conclusions you came to in this video. It felt very validating! Thank you for the great visual and description of your terms. I wouldn't have been sure I had actually had the same solution as you if you hadn't. Also yours is much cleaner and easier to understand than mine.
When I saw your video mentioned in 3B1B's SOME2 results video, I was dead sure you were gonna win. Welp, like he said, every video is the best for different demographics of people, and this is the one for me. Fucking incredible video, and thank you for making this!
I've always wanted such content on youtube, and finally here it is. Looking forward for next videos. But personally for me it was very hard to follow the solution, the key part about what we store as dp_i and how we calculate it, is explained too briefly. (although I am 1900 on codeforces).
Hi, sorry about that! dp_i is the time it takes to enter a portal and return back to the same position. It is calculated as dist_i + cost_i: Dist_i is X_i - Y_i, the distance between the entrance and exit. Cost_i is the sum of the return trip times of all the portals we encounter in between i_th exit and the i_th entrance. For some intuition on why this works: consider the path you take when you go into an entrance. 1. X_i, jump to Y_i 2. Walk until u reach an entrance (which is guaranteed to be open) 3. Go into entrance; recurse. 4. Continue past portal, walk until next entrance... Repeat steps 2-4 until you reach entrance i. Each "recurse" has a fixed cost that we've already computed! That's the corresponding dp value.
@@ABitWiser Yeah thanks for explanation, I have totally understood the algorithm. In my original comment I just wanted to say, that I think it would be better, if explanation in video were somewhat smoother (I don't really know how to make it so).
I had to rewatch too, not because I misunderstood the concept, but because the variables were not named. In the final solution I had to rewind to where the arrays X, Y, and S were defined 7 minutes earlier in the video at 5:23. Please name your variables appropriately if presenting to an audience (be they viewers, other developers working on the code base, or most likely future you that forgot what you were thinking when you initially wrote it). Let the compiler get rid of the extra characters. Hard drives are a lot cheaper than salaries.
Incredible video and excellent teaching. Like many others, I’m amazed this is your first video! You earned a sub - can’t wait to see what else you have for the future!
Incredible video! When I first studied dynamic programing I had lots of troubles wrapping my head around it and seeing it explained so clearly was really nice! I wish your video came out earlier 🤣
Thank you for explaining this so nicely, I gave this problem a try before looking at the solution and when I saw my solution matched up with the one you presented I was very happy, this is a great explanation of dynamic programming, great video!!
I'm a beginner EASY coder and this video popped up in my feed, my Feedback :- Good Work 👍🏻, nicely explained, with little bit of pace management, even beginner's like me can understand the Problem Solving aspect. Thank You.
This is a great video! But the part near 6:40, explaining how dp was calculated was paced a bit too quick, and I had to rewatch that part to understand it. Otherwise, a great explanation of a hard problem.
Great video, subbed from here. I could follow right up until 8:50 then it started getting over my head, I think I'll have to watch the last part a couple of times before I start to get it.
The binary search can be avoided, by using a stack and a linear scan of the entire line (merge X and Y). The indexes you are trying to find using bisect can be precomputed and stored in a separate array in linear time.
We can't, since the Y's are not given to us in sorted order. So either we need to sort y's and remember their indices and then merge, or use binary search over x.
Very Video, much good, such wow. First video, and despite some audio that's clearly form different recording sessions its mostly flawless. Keep on rocking dude.
I came up with the following solution, it may be a bit easier to understand: we need to go from right to left once and keep track of the current coverage (number of paths covering this region). We start with coverage = 1 (on the far right). Let's use four terms: c_si, c_so: number of ingoing (left) and outgoing (right) paths of a portal Start; and c_ei, c_eo: number of ingoing and outgoing paths of a portal End. We use dynamic programming from the right to the left, so we just update c_si given c_so: c_si = 2 * c_so + a - 1, where a = 1 iff the portal is active at the very beginning. Basically, if we know that there are c_eo outgoing paths after the portal start, there must (c_so + a - 1) teleportations from that portal. Similarly, we update c_ei given c_eo and c_so (both known already): c_ei = c_eo - (c_so + a - 1). Here we just reduce coverage by the number of jumps. Because we need to have a sorted list of positions, this solution seem to require O(n logn), but easier to implement and has smaller constant.
Nice problem! I've come up with a O(n) solution that's actually pretty straightforward, though: I start at the end of the line and count how many times has the ant crossed every path segment between the portal exits and entrances (I'll call it the number of crossings for a given segment). Coming from the end, we start with a 1, because that's the last segment after the last portal entrance. Whenever we encounter a portal entrance, the segment to the left of it will have twice as many crossings as the segment to the right, because for every time the ant has traveled over the closed entrance, it must have come once through the entrance before, in order to close it. That means we now know how many times the ant has gone through the entrance, and therefore how many times it has emerged out of its corresponding exit. So whenever we encounter that exit as we go from the right, we'll know that the segment to the left of it will have exactly that number *less* crossings than the segment to the right. And because every portal exit is to the left of its entrance, we'll never encounter an exit without having first encountered its corresponding entrance, thus we'll always know which number to subtract. Now that we know the number of crossings for every segment, it's easy to multiply the number by the segment length and sum them all together. This requires O(n) computations and O(n) memory, because we need to either store the numbers of crossings for every segment, or keep only a running total (always adding the number of crossings multiplied by the segment length) but store how many times has each portal been used, so that we know which number to subtract when we come across a portal exit. In either case, this array will grow linearly with the number of portals. Incidentally, this algorithm is easy to follow even with a pencil and paper, which is how I've come up with it, after plotting the ant's path in time. Had a lot of fun with this! :)
In case of portal entrances that have a closed initial state, we'll need to subtract 1 after doubling the number of crossings, and it's corresponding exit will subtract 1 less crossings, once we encounter it.
Great animation and explanation. But finding patterns can be tricky. And even tricky is finding how to use these patterns to solve the problem. More tricky is to make the solution optimal by using tricks like prefix sums, etc like you mentioned in the video. For experts this is easy because of practice and wide variety and number of problems they solve each day.
this is fqntastic start to a youtube channel, great job! i would make sure to balance your music a little softer tho, its almost overpowering your voice. keep up the good work bro, you have a new subscriber
i had a very different idea to solve this fast. from a mathematician's perspective. every portal has a length (distance from exit to entry) and a number (how often it teleports the ant). both are calculated easily: 1) distance is trivial 2) give a value of 0 to all closed, and a value of 1 to all open entries. now start from the rightmost entry and add its number (0 or 1) to all portal entries enclosed between its entry and exit. do the same for the second entry from the right (add the updated numbers of course, not the starting value!). and so on. 3) just calculate number*distance for each portal, add everything to the base distance. ready. this works out to give the correct numbers of teleportations. each portal can only affect the numbers to their left, so for the rightmost portal it is trivially true. now thinking it through from right to left, you can see that the 2nd portal is visitied again if and only if the 1st teleports the ant somewhere behind it. all the other portals don't matter. the 3rd is visited again as often as the 2nd or 1st teleports the ant behind it. and so on.
Didn’t watch the full video yet, but here are my initial thoughts about the approach. Time = length of line + for each portal i: number of times it got ENTERED times xi - yi To find the nimber of times a portal is entered, work backwards. The last portal can only be entered 0 or 1 times. The number of times the second last portal is entered depends on the number of times the last portal is entered if the last portal has an exit to the left of the second last portal’s entrance. Be mindful about initial states. Continue this general logic for the rest of the portals. To speed things up from quadratic, sort portals also by exit positions and do binary search.
before watching, just looking at the problem here is my idea: the portals will be in some configuration with at least some portals open, to win, you need to get into the state where all portals in front of you are closed, this means you will have to close the open ones, and by passing through a portal you will always leave the one behind you open. this makes the state predictable and so now you can use memoization to cache bigger and bigger numbers of intertwined loops, counting the steps of each one by one at first, then turning would be recursive calls into lookups, not sure if this is the best you can do and i dont ever do these programming challenges sites because they rarely teach how to solve real problems, but this one seemed interesting enough to at least try.
Great video! It took me some time to figure out some claims when you tell us to convince ourselves. A brief explanation or key idea would make it more digestable.
For a true 𝒪(n) implementation, it is best to loop over all fields, not just the portals, since then the running total automatically contains which portal exits are left or right. A quick implementation of this which explicitly avoids any use of any operator that could be non-linear would be: entrances = ( 3, 6, 7, 10, 11, 12 ) exits = ( 2, 5, 4, 8, 9, 1 ) starts_open = ( 0, 1, 0, 1, 0, 1 ) length = entrances[-1] done = 0 runningtotal = [0] portalno = 0 for pos in range(1,length+1): costs = 0 if pos == entrances[portalno]: exit = exits[portalno] costs = runningtotal[pos-1]+1 - runningtotal[exit] if not starts_open[portalno]: done += costs portalno += 1 runningtotal.append( runningtotal[-1]+1 + costs ) print( runningtotal[length]+1 - done )
for all I know (I have rating of 2194 on cf) for any solution to this problem, we would need to find first x[j] greater than y[i] for all i=1..n and we would either need to sort y, or do n binary searches. We can't do n binary searches in O(n) time, and we can't sort general array in less than O(n log n), but what we can do is use constraint that y[i] < 1e9 and use radix sort(basically 2 count sorts in this case, but for numbers not up to 1e9 but 1e4.5, so linear time since n is up to 2e5), but this feels very unsatisfactory and leaves savory taste in mouth, so I would leave this problem at being O(n log n)
I believe you're correct. I made that challenge after briefly thinking of a solution where we can precompute the j values using 2 pointers. However, I realize that this depends on the Y values being sorted. I've removed that from the description. Nice catch!
I am newbie in competitive programming and will try that problem now and every piece of info here is helping, thanks a lot sir.
You are forgetting that radix sort is linear in the length of the list only if the length of the keys isn't tied to the length of the list. The time complexity of radix sort is O(w n), where w is the length of a key. In this case we have that w = O(log n), thus radix sort has the same complexity as quicksort.
@@naghus_cat according to statement, all numbers are less then 1e9, so w = log(1e9) = 30 = O(1). Then technically radix sort would be linear. If we treat 15 bits as 1 digit, then we will only have 2 iterations of radix sort. Of course all of that works only because of the constraint y < 1e9
@@rwarazor Although I would like to agree with you, that is a trick you can't apply when doing algorithm analysis. Applying the same logic I could sort the list in constant time, because n
No one can explain a 2200-rated problem better than this... definitely made me a bit wiser.
I was just thinking about how damn difficult that might have been. At least 1900 (similar to chess problems).
is this chess or am i lost
@@Gabriel_JudgeofHell difficulty rating on a coding competitions platform, it's supposed to be similar to elo
@@amirnuriev9092 oh ok where website
@@Gabriel_JudgeofHell codeforces
This video actually looks like one of those 4m subscriber channels, great job man!
Damn I had to read this comment to see that he had only 606 subscriber. His video quality feels like 3b1b, who has a lot more subscribers.
He has 607 now :) props to him, I am sure the number of subscribers will explode soon. Amazing how this was his first video
@@shadowpenguin3482 978 NOW
That's what #Some2 was meant for
@@TypicWhisper what does that mean
I am a Class 12 passout , Thoda upar se gya chalega na?
The sum on contiguous elements idea was genius, I never would have thought of that but it's so obvious in hindsight
I solved the problem much differently and pure mathematically before watching the video. it is very hard to explain a solution in text form but the main idea was to see the portals as binary numbers. I split the problem into two. evaluating how many times the player has entered a portal (to teleport not passover) and then calculating the total distance traveled. The second problem's solution was easy I just had to calculate the difference in position between the portal and the teleportation target to calculate the "cost" of the teleportation. the total length of the line plus all the costs were equal to the total distance traveled. now for the solution to the first part, look at the first example with 4 portals (red, orange, yellow, green). in the solution of this part ignore all the distances. if you look at the first red portal it teleports the player right behind itself and is thus equivalent to a binary number with one digit. orange also is a one digit number but yellow perfectly encapsulates orange but no other portal so they collectively create two digit binary number. green is encapsulating the entire one digit and two digit numbers. green is not symbolized as 3 digit but (1 + 2)+1 digits. plus operation is not summation in this notation but symbolizes that those two numbers have to be calculated independently.
so collectively the table for the puzzle is 1+2+(1+2+1).
we have to take the initial positions of the portals into account. the first one digit portal is closed so it has the value of 1. notice 1 is the maximum value a one digit binary number can hold so the next stop over it will pass it.
orange and yellow collectively two digit number seems to have the value (0x01=1) but you can observe they act as inverted. so actually they have the value (0x10 = 2) of 2.
and lastly green was symbolizing the entire copy of the puzzle plus itself but when the player passes it, all the portals will be open. so the value for green is (0 + 0 + 0)
binary digit table = 1+2+(1+2+1)
initial value table = 1+2+(0+0+0)
we are close to be able to calculate total teleportation count. just remember that one digit binary numbers can hold maximum of 1 and leak for the value of 2. similarly two digit numbers can hold the maximum of 3 and leaks for the value of 4.
binary digit table = 1+2+(1+2+1)
initial value table = 1+2+(0+0+0)
max value table = 1+3+(1+3+1)
difference table = 0+1+(1+3+1)
when we sum the difference table 1+1+3+1 = 6 you can see that player will teleport 6 times.
conveying the idea behind these tables isn't that easy in text form so if they are not clear try to read it again and calculate them by yourself this is the best that I can do.
lastls we have to calculate the costs. as I said calculating the cost for a portal is easy we have to calculate the distance between the portal and the target but when we unite two portals into a multi digit number since the two portals creating that multi digit (in this example two) number can have different costs we have to symbolize them independently. for this example in the case of orange and yellow portals, their costs are 1 and 3 so we will notate them as (1+3) for the 2 digit number. this says that if the player enters the first digit the cost is 1 and if it enters the second digit the cost is 3. we need to somehow evaluate how many times which digit will flip while counting in binary. I will calculate that for the general case later but for two digit binary (00 10 01 11) the first digit will flip every time and the second digit will flip every two times. collectively first 4 times and second 2 times.
let me write the tables again this time with the cost table too.
cost table = 1+(1+3)+1+(1+3)+7
binary digit table = 1 + 2 + (1 + 2 + 1)
initial value table = 1 + 2 + (0 + 0 + 0)
difference table = 0 + 1 + (1 + 3 + 1)
total cost table = 0+(1+0)+1+(1+3+1)+7 = 14
total distance travelled = cost + distance = 14 + 9 = 23
the reason for the cost for the second two digit number to be not (1+3) but (1+3+1) is because while counting 00 10 01 11 first digit is flipped from 0 to 1 twice and second digit once.
thus when the binary digit table is constructed total distance traveled can be evaluated mathematically with near zero computational cost.
I have spent around 2 hours for the solution and an additional 2 hours watching the video and writing this comment. I'm very happy if you have read it to here and I hope you like the solution. have a nice day.
nerd!
@@illuminatelair8084 haha! this is my job tho.
Yeah at the beginning of teh vid I was expecting a binary related explanation similar to this lol
I had a similar idea. I wonder whether we can actually view the idea in the video as a variant of yours. I think they might be related.
Yup, this makes sense! Thanks for the long answer, much needed.
Probably the best explanation to a problem I've ever seen
I'm shocked that this is the first video on this channel, the quality is something I would expect it to take months or even years to achieve. Can't wait for the next one!!!
i'm completely shocked that this is the only video this channel has posted, this is incredible. thank you for putting in the work to make free educational resources
As a green coder (1200-1400 CF) I can say that I understood the 2200 rated problems solution proving that this guy have put a great work into his explanation!
Thanks! We hoped to guide viewers through the solution while letting you all make a few leaps of your own. Happy to hear you followed along!
I really liked how you showed how much DP speeds things up at 7:18. I also like how you cut off the music at 6:37 when making your conclusion. One criticism I have is you sometimes show graphics on the screen only while you talk about it, so it's hard to visually digest what you're showing and listen in that short time (ie sometimes it's a bit fast such as at 5:30)
Thanks for your feedback!
Awesome video. I noticed this is your first on RUclips, I hope you keep it up! Really tough problem but you explained it well. Always wished there was a 3b1b for data structure and algs. Could be you.
Banger video
Banger commenter (call me)
this feels like protagonist in a anime figuring things out
An academic epiphany of many proportions
the motion graphics illustrating the algorithm are absolutely delightful!
i really liked the animations, especially the last part where the lines of code are highlighted each step and you can see where the results move to.
You are an awesome storyteller and a talented movie maker, and not to mention an excellent teacher whatsoever.
This is the best video on the internet, until you upload the next one
Fantastic visuals. I wonder how many followed it all while watching the video without pausing it. I sure didn't. But still I'm impressed.
The animations were really nice, particularly for the DP graph visualization. Very creative.
The quality of this video is amazing! I really liked how well you made the music sync up to the algorithm at the end with a satisfying ding every time the cost was calculated.
The part at 10:30 felt a bit rushed though, I had to rewatch and study your python implementation to realize why exactly you needed to binary search to find the index of the ps array, but other than that it was an excellent video and a delight to watch.
Thanks for the helpful notes and kind words
Yeah, I too needed a lot, and I mean, lot of thought to understand why a binary search was needed. It's a good thing though. I don't want to be this failure programmer who watches videos with an off mind but can't code or think anything himself. I like this!
The interesting thing is that one does not NEED to to binary search, and actually avoiding it lowers the time complexity from O(n logn) to O(n).
Great video. One thing I liked about this is that it didn't break-down the solution, instead it just introduced the ideas and let the viewer understand it by though. I loved this methodology for this problem is particular, but you may run into issues doing this with much more complicated problems.
Just great! Can’t wait for the next video.
And any video made using manim have to be great:)
wow such a high quality video for a competitive programming problem. Great explanation and visualization. I just love it.
Absolute gold. Keep it up. Wish to see several algorithm implementations and problems in this format.
So I might have taken your challenge to solve this problem in O(n) a bit too seriously.
It took a variant of counting sort to allow building a hash map from each exit to the closest entrance in O(n), so we can skip the binary search and replace it with an access to the hash map in O(1), thus resulting in a total complexity of O(n) (where n is the length of the road rather than the portal count, though).
I did something similar. No hash, just a simple array, with an element for each node, storing the steps needed to go from the start to that node, assuming all portals are open.
@@Palparepa I also thought of doing that at some point, but I wanted to respect the 256MB limit for the challenge, which I believe this solution can't satisfy with roads up to 10^9 in length. Congrats on O(n) time complexity anyways !
Great video! We definitely need more of that. Keep it up man
3000 subscribers? no way, this is an amazing work.
And i want to say that in the bisect method we can specify "Lo" and "hi" parametres(the start and end indices in the array where we want to search our element), so if we're in portal X[i] and go out in Y[i], we don't need to search all over X to find a nearest portal, we need to search in X[from 0 to i], so if we specify bisect(X, Y[i], hi=i) time complexity for all calls will be:
log(1)+ log(2) + log(3) + ... + log(n) = log(n!)
n / 2 * log(n / 2)
What's the point of "improving" O(nlogn) to another O(nlogn), when the optimal solution is O(n)? Just find a way to avoid bisecting at all, as it's unnecessary
@@itellyouforfree7238 there's no O(n) solution
@@Splish_Splash after reading the problem on codeforces i realized the video is slighty imprecise. it gives the impression that there is only one variable n, the number of the portals, and the length of the track is always 2n. instead there are two variables, n = "no. of portals", M = "length of track", with 2n
Hats off for the informative video, good stuff!
I can't implement binary search off the top of my head for the life of me, not having actually ever done it.
Caught that pattern at 2:14, the movement straight up looked like counting in binary with variable offsets.
Fascinating.
Binary Search: Assume array is sorted and you have access to the size.
Define lower/upper indices to be 0 and size() - 1, respectively.
Sum the indices and divide by 2 (integer division), this is your mid index.
Is A[mid] equal to your value?
If yes, then we're done.
Otherwise, if its smaller, then the upper index becomes mid index - 1. If its larger then the lower index becomes mid index + 1. Loop.
Stop the loop if lower > upper (value doesn't exist in array).
Absolutely incredible. Amazing content right out the gate! Keep making awesome vids
Checked out your channel to see more vids and realised thats the only one. The music/animation was honestly amazing
This is so high quality! I thought I was watching a 3blue1brown video
I really appreciated this video. I paused at the 2 minute mark, solved it myself in O(n log n), and then saw that I came to the same conclusions you came to in this video. It felt very validating! Thank you for the great visual and description of your terms. I wouldn't have been sure I had actually had the same solution as you if you hadn't. Also yours is much cleaner and easier to understand than mine.
When I saw your video mentioned in 3B1B's SOME2 results video, I was dead sure you were gonna win.
Welp, like he said, every video is the best for different demographics of people, and this is the one for me. Fucking incredible video, and thank you for making this!
Love this video and the animations. Keep making more of these videos please
Fantastic video! Use of prefix sums is pretty genius.
I've always wanted such content on youtube, and finally here it is. Looking forward for next videos.
But personally for me it was very hard to follow the solution, the key part about what we store as dp_i and how we calculate it, is explained too briefly. (although I am 1900 on codeforces).
And maybe music is a little loud
Hi, sorry about that!
dp_i is the time it takes to enter a portal and return back to the same position.
It is calculated as dist_i + cost_i:
Dist_i is X_i - Y_i, the distance between the entrance and exit.
Cost_i is the sum of the return trip times of all the portals we encounter in between i_th exit and the i_th entrance.
For some intuition on why this works: consider the path you take when you go into an entrance.
1. X_i, jump to Y_i
2. Walk until u reach an entrance (which is guaranteed to be open)
3. Go into entrance; recurse.
4. Continue past portal, walk until next entrance...
Repeat steps 2-4 until you reach entrance i.
Each "recurse" has a fixed cost that we've already computed! That's the corresponding dp value.
@@ABitWiser Yeah thanks for explanation, I have totally understood the algorithm. In my original comment I just wanted to say, that I think it would be better, if explanation in video were somewhat smoother (I don't really know how to make it so).
I think the music volume is great
I had to rewatch too, not because I misunderstood the concept, but because the variables were not named. In the final solution I had to rewind to where the arrays X, Y, and S were defined 7 minutes earlier in the video at 5:23. Please name your variables appropriately if presenting to an audience (be they viewers, other developers working on the code base, or most likely future you that forgot what you were thinking when you initially wrote it). Let the compiler get rid of the extra characters. Hard drives are a lot cheaper than salaries.
Loved it! Thank you for this and all upcoming videos, orz
Amazing effort for a video about one dp problem! Hope to see another entry this year for some3!
Damn thats some quality work! Your Channel needs to blow up. You have my subscription at least :)
Excellent video, this is 3b1b-quality explaining!
Incredible video and excellent teaching. Like many others, I’m amazed this is your first video! You earned a sub - can’t wait to see what else you have for the future!
Incredible video! When I first studied dynamic programing I had lots of troubles wrapping my head around it and seeing it explained so clearly was really nice! I wish your video came out earlier 🤣
The production value, explanation, pacing, audio, visuals, everything about this screams top-notch quality. Can't wait to see more!
This is unbelievably good explanation, please keep up and post more!
you probably are the best teacher ever for dsa. I have never seen a better explanation
Thank you for explaining this so nicely, I gave this problem a try before looking at the solution and when I saw my solution matched up with the one you presented I was very happy, this is a great explanation of dynamic programming, great video!!
I'm a beginner EASY coder and this video popped up in my feed, my Feedback :- Good Work 👍🏻, nicely explained, with little bit of pace management, even beginner's like me can understand the Problem Solving aspect. Thank You.
Loving the animations. Really made the video so much more understandable. Really great job!
Great explanation, felt really absorbed during whole video
This is a great video! But the part near 6:40, explaining how dp was calculated was paced a bit too quick, and I had to rewatch that part to understand it. Otherwise, a great explanation of a hard problem.
Thanks, we appreciate your feedback!
@@ABitWiser it’s a we!?
@@someonlinevideos Yeah! It's two of us, credits in the description :)
Great video, subbed from here. I could follow right up until 8:50 then it started getting over my head, I think I'll have to watch the last part a couple of times before I start to get it.
Please make more videos, the wonderful quality and entertainment value this has is beautiful, thank you.
This is amazing! Calling now that this will be in the winners video :D
The binary search can be avoided, by using a stack and a linear scan of the entire line (merge X and Y). The indexes you are trying to find using bisect can be precomputed and stored in a separate array in linear time.
We can't, since the Y's are not given to us in sorted order. So either we need to sort y's and remember their indices and then merge, or use binary search over x.
Very Video, much good, such wow.
First video, and despite some audio that's clearly form different recording sessions its mostly flawless. Keep on rocking dude.
that was incredible man, please keep on going :)
Beautifully done. Simply awesome
Great first video. Loved it. Subscribed.
Excellent video. Very well-explained and demonstrated. I hope you post more.
I don't see 84 subscribers, I see 84M!
Just soo good. Please, never stop making these ❤❤
GOAT explanation skills, amazing work! Hoping for a lot more great videos in the near future.
I came up with the following solution, it may be a bit easier to understand: we need to go from right to left once and keep track of the current coverage (number of paths covering this region). We start with coverage = 1 (on the far right).
Let's use four terms: c_si, c_so: number of ingoing (left) and outgoing (right) paths of a portal Start; and c_ei, c_eo: number of ingoing and outgoing paths of a portal End.
We use dynamic programming from the right to the left, so we just update c_si given c_so: c_si = 2 * c_so + a - 1, where a = 1 iff the portal is active at the very beginning. Basically, if we know that there are c_eo outgoing paths after the portal start, there must (c_so + a - 1) teleportations from that portal.
Similarly, we update c_ei given c_eo and c_so (both known already): c_ei = c_eo - (c_so + a - 1). Here we just reduce coverage by the number of jumps.
Because we need to have a sorted list of positions, this solution seem to require O(n logn), but easier to implement and has smaller constant.
Nice problem! I've come up with a O(n) solution that's actually pretty straightforward, though: I start at the end of the line and count how many times has the ant crossed every path segment between the portal exits and entrances (I'll call it the number of crossings for a given segment). Coming from the end, we start with a 1, because that's the last segment after the last portal entrance. Whenever we encounter a portal entrance, the segment to the left of it will have twice as many crossings as the segment to the right, because for every time the ant has traveled over the closed entrance, it must have come once through the entrance before, in order to close it. That means we now know how many times the ant has gone through the entrance, and therefore how many times it has emerged out of its corresponding exit. So whenever we encounter that exit as we go from the right, we'll know that the segment to the left of it will have exactly that number *less* crossings than the segment to the right. And because every portal exit is to the left of its entrance, we'll never encounter an exit without having first encountered its corresponding entrance, thus we'll always know which number to subtract. Now that we know the number of crossings for every segment, it's easy to multiply the number by the segment length and sum them all together.
This requires O(n) computations and O(n) memory, because we need to either store the numbers of crossings for every segment, or keep only a running total (always adding the number of crossings multiplied by the segment length) but store how many times has each portal been used, so that we know which number to subtract when we come across a portal exit. In either case, this array will grow linearly with the number of portals.
Incidentally, this algorithm is easy to follow even with a pencil and paper, which is how I've come up with it, after plotting the ant's path in time. Had a lot of fun with this! :)
In case of portal entrances that have a closed initial state, we'll need to subtract 1 after doubling the number of crossings, and it's corresponding exit will subtract 1 less crossings, once we encounter it.
Oh man.. you took it to the next level. Also how many hours did you spend making this?
I just subscribed, I love competitive programming and I think this channel will help me on my journey.
Fantastic. What a superb first video. I hope there will be more, but even if not, wow.
this video is really impressive, please make more!
Great animation and explanation. But finding patterns can be tricky. And even tricky is finding how to use these patterns to solve the problem. More tricky is to make the solution optimal by using tricks like prefix sums, etc like you mentioned in the video. For experts this is easy because of practice and wide variety and number of problems they solve each day.
This Channel is going to explode in terms of sub count.
Thank you for the hard work and for sharing it!
this is fqntastic start to a youtube channel, great job!
i would make sure to balance your music a little softer tho, its almost overpowering your voice. keep up the good work bro, you have a new subscriber
Thank you for making such a great video!
i had a very different idea to solve this fast. from a mathematician's perspective.
every portal has a length (distance from exit to entry) and a number (how often it teleports the ant).
both are calculated easily:
1) distance is trivial
2) give a value of 0 to all closed, and a value of 1 to all open entries.
now start from the rightmost entry and add its number (0 or 1) to all portal entries enclosed between its entry and exit. do the same for the second entry from the right (add the updated numbers of course, not the starting value!). and so on.
3) just calculate number*distance for each portal, add everything to the base distance. ready.
this works out to give the correct numbers of teleportations. each portal can only affect the numbers to their left, so for the rightmost portal it is trivially true. now thinking it through from right to left, you can see that the 2nd portal is visitied again if and only if the 1st teleports the ant somewhere behind it. all the other portals don't matter. the 3rd is visited again as often as the 2nd or 1st teleports the ant behind it. and so on.
Very promising video. Looking forward to more!
10:10 the fundemental theorom of discrete calculus
Every math or CS student should subscribe!
Great work man, cant wait to see more of DP or Machine Learning ect ...
Please make more videos
This was very well explained
I feel like I'm going to love this channel....
amazing video!!! Please continue to create similar video.
This is so well done !!
amazing work man, keep it up!!!
Didn’t watch the full video yet, but here are my initial thoughts about the approach. Time = length of line + for each portal i: number of times it got ENTERED times xi - yi
To find the nimber of times a portal is entered, work backwards. The last portal can only be entered 0 or 1 times. The number of times the second last portal is entered depends on the number of times the last portal is entered if the last portal has an exit to the left of the second last portal’s entrance. Be mindful about initial states. Continue this general logic for the rest of the portals. To speed things up from quadratic, sort portals also by exit positions and do binary search.
This is a really awesome video with great production❤
Wow amazing visualization! Good job!
my left ear has been enlightened by this information
before watching, just looking at the problem here is my idea: the portals will be in some configuration with at least some portals open, to win, you need to get into the state where all portals in front of you are closed, this means you will have to close the open ones, and by passing through a portal you will always leave the one behind you open.
this makes the state predictable and so now you can use memoization to cache bigger and bigger numbers of intertwined loops, counting the steps of each one by one at first, then turning would be recursive calls into lookups, not sure if this is the best you can do and i dont ever do these programming challenges sites because they rarely teach how to solve real problems, but this one seemed interesting enough to at least try.
Fantastic video. Great job!
11:50 when you finally finish a zachthronics game and you're watching a replay of your creation
Keep making videos, one day this channel would be huge
Amazing work, you earned a subscriber!
Great video! It took me some time to figure out some claims when you tell us to convince ourselves. A brief explanation or key idea would make it more digestable.
Amazing content, great animations. Really hope you still have plans of making more videos!
that was smooth, well done!!
Nice first video, My left Ear enjoyed it.
Fantastic video. Keep up the great work.
Wow I really liked this explanation, I want more!
For a true 𝒪(n) implementation, it is best to loop over all fields, not just the portals, since then the running total automatically contains which portal exits are left or right. A quick implementation of this which explicitly avoids any use of any operator that could be non-linear would be:
entrances = ( 3, 6, 7, 10, 11, 12 )
exits = ( 2, 5, 4, 8, 9, 1 )
starts_open = ( 0, 1, 0, 1, 0, 1 )
length = entrances[-1]
done = 0
runningtotal = [0]
portalno = 0
for pos in range(1,length+1):
costs = 0
if pos == entrances[portalno]:
exit = exits[portalno]
costs = runningtotal[pos-1]+1 - runningtotal[exit]
if not starts_open[portalno]:
done += costs
portalno += 1
runningtotal.append( runningtotal[-1]+1 + costs )
print( runningtotal[length]+1 - done )
n = num of portals
dynamic programming is a weak spot I need to work on for coding interviews. Always good to get more exposure on the subject