Video 2-5: Hindsight Capital

0:02 What I want to do for the rest of this unit is on a concrete algorithmic problem show you the power of algorithm design and how much you can get from a stupid first solution to a a much faster slightly more insightful solution. Uh and the way um I want to illustrate this is with this game where you're uh a stock trader but you have a uh a slight advantage namely you know uh the future and so you can place your your uh trades in hindsight.

0:36 You're working for hindsight capital and you can say I'm going to buy my stock here. I'm going to sell it again here and then I get plus five on this day, minus two on this, total profit three.

0:55 So you can work out what is the best choice. You only get one buy, one sell window. And so you can try to um outsmart each other and of course also the time counts if several people get the optimal answer.

1:16 So the link to join this is tiny.cc um /subarray. Uh let's have a let's have a short round of of people playing this. I mean for one um live coding is fun but also I think you get a nice intuition into the problem if you first play with it before I'm throwing the definitions at you. And maybe you appreciate the algorithms a bit more because the final algorithm you can actually use in this game very productively once you think about it. But it's non-trivial enough that maybe you haven't thought about it yet. That's my hope.

2:20 your best solution should come up here. Ooh, it works. >> [snorts] >> Okay, people are starting to speed ahead. I mean, maybe point out a few things that uh somewhat obvious, but of course, you can just slide this over the entire thing. I can pick any start point and then just watch the number here given as profit change.

4:31 And uh when you see the largest number, you know, ah then I'm going to click. Right. So, then in principle, um you can just uh work it out that way.

5:00 Okay, so the first few people get into the slightly bigger inputs now. Like if you two three more minutes, and then uh we'll call the the winners whoever leads the leaderboard at that time. And of course, you can you can play a bit more later. But once you know the algorithm, it's a bit spoiled. So, this game is kind of after a short while rather easy.

6:24 >> Of course, one feature I didn't didn't program in is some way some dramatic countdown and then the announcement of the winners. So, that I'll have to improvise. Five, four, three, two, one.

6:43 Okay, whoever's trader uh but okay, it's close. Either way. So, um thanks for playing along and uh congrats to the first first three who did this rather quick. Um the remaining of the levels get slightly bigger and eventually the sum is no longer shown and then the last one you have to do the math yourself. Um would anyone like to comment on their approach? Have you done anything smarter than what I did with just trying out all start and end points? The first handful of levels you can maybe just look at there's a lot of green and that gets you quite a far distance. Yeah, that was Sure. >> And So, that's a rather like a hone in on the green stuff and then only extended unwillingly like a uh probably not a bad strategy. Uh any other strategies you people want to share? Yeah.

8:38 So, you guys about bridge over bad days, etc. Now, what do you think if if the Okay, the the rendering doesn't scale to that, but if I gave you a thousand days, how would you feel about finding the optimal range? Yeah.

9:10 How about how about this? Like uh um of course, you have right. If there's long stretches of green, clearly good. Long stretches of red, mhm. What do I do in a case like this?

9:25 Sure. Aha. Something like this. Uh Now again, think of this growing a good deal more, then the visual strategies that we would as a human follow tend to get a bit more tricky. Um as things get bigger here, maybe there this is this is suggestive that I have to go somewhere here, right? But, uh you see how there's maybe the need for something more systematic.