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)

No one can explain a 2200-rated problem better than this... definitely made me a bit wiser.

This video actually looks like one of those 4m subscriber channels, great job man!

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.

The sum on contiguous elements idea was genius, I never would have thought of that but it's so obvious in hindsight

Probably the best explanation to a problem I've ever seen

Awesome video. I noticed this is your first on KZfaq, 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.

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!!!

Banger video

An academic epiphany of many proportions

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.

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!

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)

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!

Oh man.. you took it to the next level. Also how many hours did you spend making this?

Checked out your channel to see more vids and realised thats the only one. The music/animation was honestly amazing

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).

Loving the animations. Really made the video so much more understandable. Really great job!

Absolutely incredible. Amazing content right out the gate! Keep making awesome vids

Just great! Can’t wait for the next video. And any video made using manim have to be great:)

This is the best video on the internet, until you upload the next one

the motion graphics illustrating the algorithm are absolutely delightful!

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.

This is unbelievably good explanation, please keep up and post more!

The animations were really nice, particularly for the DP graph visualization. Very creative.

Great video! We definitely need more of that. Keep it up man

Love this video and the animations. Keep making more of these videos please

wow such a high quality video for a competitive programming problem. Great explanation and visualization. I just love it.

The production value, explanation, pacing, audio, visuals, everything about this screams top-notch quality. Can't wait to see more!

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!!

Just soo good. Please, never stop making these ❤❤

Please make more videos, the wonderful quality and entertainment value this has is beautiful, thank you.

I don't see 84 subscribers, I see 84M!

GOAT explanation skills, amazing work! Hoping for a lot more great videos in the near future.

Beautifully done. Simply awesome

Fantastic video! Use of prefix sums is pretty genius.

Loved it! Thank you for this and all upcoming videos, orz

Excellent video. Very well-explained and demonstrated. I hope you post more.

Amazing effort for a video about one dp problem! Hope to see another entry this year for some3!

you probably are the best teacher ever for dsa. I have never seen a better explanation

This is a really awesome video with great production❤

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.

Thank you for the hard work and for sharing it!

Thank you for making such a great video!

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 🤣

Damn thats some quality work! Your Channel needs to blow up. You have my subscription at least :)

this video is really impressive, please make more!

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).

This is so high quality! I thought I was watching a 3blue1brown video

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.

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.

This is amazing! Calling now that this will be in the winners video :D

Amazing content, great animations. Really hope you still have plans of making more videos!

that was incredible man, please keep on going :)

Excellent video, this is 3b1b-quality explaining!

Fantastic. What a superb first video. I hope there will be more, but even if not, wow.

Great first video. Loved it. Subscribed.

Wow amazing visualization! Good job!

This is so well done !!

Great video ! But I have a question about the audio : the changes in panning of your voice intended ? It sounded a bit weird with headphones.

Wow I really liked this explanation, I want more!

I just subscribed, I love competitive programming and I think this channel will help me on my journey.

Very promising video. Looking forward to more!

Please make more videos This was very well explained

We need more! More videos!

Fantastic video. Great job!

Amazing work, you earned a subscriber!

amazing video!!! Please continue to create similar video.

Fantastic video. Keep up the great work.

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.

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.

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.

Looking forward to more of these!

I feel like I'm going to love this channel....

that was smooth, well done!!

amazing work man, keep it up!!!

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!

Looking forward to the next one! ❤️

Great video. Good start. Keep up the good work.

Every math or CS student should subscribe! Great work man, cant wait to see more of DP or Machine Learning ect ...

Great work man... Hat's off

Please keep making these!

I really liked this video. My only problem with it: you left pieces out of the setup. For example, you started talking about "this solution doesn't meet our constraints" without mentioning what those constraints were. And you didn't mention that the line always ends 1 unit after the last portal. Also, you didn't explain the bisect function of python in your solution. So in order to understand 100% of the context, I had to check out the original problem and google the bisect function. That's more legwork than I think you'd want your viewers to do.

Great explanation, felt really absorbed during whole video

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.

Super nice video! Although one thing is not nice, please process your mic's sounds so both audio channels would have equal volume 🙏

Nice first video, My left Ear enjoyed it.

Keep making videos, one day this channel would be huge

this was superbly presented!

Great Explanation. You sure must upload more

dynamic programming is a weak spot I need to work on for coding interviews. Always good to get more exposure on the subject

superb work man!

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

When you said the portals to the left are always open, I was wondering why you didn't talk about the possibility of a portal teleporting the ant forwards. I had to go back to the beginning to rewatch the part where you described the setup because I totally missed you said the portals exit could only be to the left. Totally my mistake, not blaming you, but just a suggestion to an educational video-maker, that would have been a very useful time to include a reminder like "remembering that all portal exits are to the left of their entrance" for people like me who either missed or forgot that part of the problem statement.

Fantastic. More please!

I learned so much!!!

Literally amazing..

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.