Today's studying involved "Dynamic Programming" and "Backtracking", which really turned out to be different names for little tricks I've used before in recursion. I'm going to have to look at them again, just to make sure I've got it straight, in case I get asked. I don't want to look like an idiot because I don't know something's name.
Especially if I use it all the time.
Anyway. I know why you're really here: today I tried a brainteaser from techinterview about pirates. It ARRRR-ta be a lot of fun.
Five pirates have captured a booty of 100 gold pieces. As you know, pirates use a seniority system when it comes to making decisions; in this case, the most senior pirate is pirate #5 and the least senior is pirate #1 (n00b).
You also know, of course, that pirates are greedy. And bloodthirsty. What sets this group of pirates apart, though, is how intelligent they are.
By which I mean that they're really smart (not noteworthy in the opposite direction).
Their method of dividing the 100 coins will be in keeping with pirate greed, violence, and seniority. The most senior pirate will propose a division of booty. All the pirates will vote to accept or reject the proposal. If at least 50% approve, the booty is divided according to the proposal. Otherwise, the propose-er walks the plank, and the new most senior pirate makes a new proposal.
Of course, having such massive brainpower, the most senior pirate makes a proposal that is automatically accepted. What was it?
When I told my kids about this one, they immediately got hung up on the seniority numbers. They wanted the #1 pirate to be the Pirate King. I told them that the numbers are how many days they've been on the job, and that helped sort them out.
I originally expected this would degenerate into even shares. Then I started thinking: pirate #5 needs to make a better proposal than pirate #4 would, if he ever got the chance. That means more to #4 than he would get if he was splitting it up. And since #4 would have to make a better proposal to #3 than if he was doing the splitting... it suddenly looked like the n00b was going to get a lot of GP.
But that was wrong way to think about it. After all, #5 doesn't really need #4's vote. He just needs three votes, and one of them can be his own. He just needs to convince 2 more pirates to accept his proposal.
Let's think about backwards.
If there were only one pirate, he's the Captain. He gets it all. Yawn.
If there were only two pirates, the Captain gets it all, because he's guaranteed one vote, and that's all that's required for 50% with two pirates. Being greedy, he'll propose 100 gold for himself, none for the new guy. It's good to be the King.
But if there are three pirates, the Captain can't get it all. He needs to win over at least one other pirate. He can't win over pirate #2: that black-hearted swaggart wants him dead, so he can take all the gold. But pirate #1 knows that if he doesn't accept pirate #3's proposal, he'll get nothing, because pirate #2 will be the Captain and take it all.
So all pirate #3 has to do is offer one doubloon to pirate #1. He can take 99 for himself. That gets him the necessary two votes.
But what if there are four pirates? The Captain still only needs two votes, so he still only needs to win over one other pirate. Pirate #3 wants him dead, so that's not going to work. Pirate #1 wants him dead, because he knows he'll get at least one gold from pirate #3.
He could offer pirate #1 two GP, and take 98 for himself. But can he do any better?
Sure he can. His greedy guts realize that if he walks the plank, pirate #2 gets nothing when pirate #3 divvies up the loot. So he can offer just one piece of eight to pirate #2 and secure his vote. That leaves 99 for him.
Now we come to pirate #5. Can he get away with 99 gold for himself? He needs two more votes, as mentioned earlier. That's going to mean at least two shiny coins. And who should he give them to? Obviously not pirate #4: that traitorous dog would like nothing better than to see him swimming with the sharks, so he can have it all to himself. And pirate #2 is no better: he'll at least get one coin from pirate #4, so he'll need too much convincing.
But pirates #1 and #3 know that, if the Captain goes down, they'll get nothing from the first mate. So one gold apiece will buy their votes.
Putting it all into a nice chart, we see the pattern pretty obviously.
1 2 3 4 5 100 0 100 1 0 99 0 1 0 99 1 0 1 0 98
Odd-numbered Captains have to give 1 coin to every other odd-numbered pirate, and get to keep the rest. Even-numbered captains have to give 1 coin to every even-numbered pirate, and get to keep the rest.
So it's easy to see what proposal a Captain should make, regardless of how many pirates there are. Also, somebody better propose a new method of splitting the booty, or there's gonna be mutiny!