Rules
Let's play a game. In this game, there are several wallets in front of you. Each wallet contains bills of differing values. You have to pick one wallet to hand to your enemy. Your enemy, in turn, has to pick one of that wallet's bills to hand back to you.
Strategy
Your enemy will always hand you the smallest bill that she can, so you should hand her the wallet with the largest smallest bill. In fact, to you, each wallet is worth only as much as its smallest bill. The question is: to find the wallet with the largest smallest bill, do you have to look through every wallet, at every single bill?
The answer is: no. Look at each of the first wallet's bills. Remember the value of the smallest bill - call this value alpha. Alpha represents the value of the largest smallest bill that you've seen so far. Put the first wallet in your pocket.
Start looking through the second wallet. If you see a bill valued less than alpha: immediately throw that second wallet in the trash. Otherwise: throw the first wallet in the trash, set alpha to the value of the second wallet's smallest bill, and put the second wallet in your pocket. Repeat this paragraph for each remaining wallet.
At the end of this process, the best wallet is in your pocket and the rest of the wallets are in the trash. Take the wallet out of your pocket and hand it to your enemy. Be sure that she'll hand the bill valued alpha back to you.
Author Note
After wrecking my brains for HOURS and HOURS, I was finally ENLIGHTENED by these few simple paragraphs! Hold My Dog!
Let's play a game. In this game, there are several wallets in front of you. Each wallet contains bills of differing values. You have to pick one wallet to hand to your enemy. Your enemy, in turn, has to pick one of that wallet's bills to hand back to you.
Strategy
Your enemy will always hand you the smallest bill that she can, so you should hand her the wallet with the largest smallest bill. In fact, to you, each wallet is worth only as much as its smallest bill. The question is: to find the wallet with the largest smallest bill, do you have to look through every wallet, at every single bill?
The answer is: no. Look at each of the first wallet's bills. Remember the value of the smallest bill - call this value alpha. Alpha represents the value of the largest smallest bill that you've seen so far. Put the first wallet in your pocket.
Start looking through the second wallet. If you see a bill valued less than alpha: immediately throw that second wallet in the trash. Otherwise: throw the first wallet in the trash, set alpha to the value of the second wallet's smallest bill, and put the second wallet in your pocket. Repeat this paragraph for each remaining wallet.
At the end of this process, the best wallet is in your pocket and the rest of the wallets are in the trash. Take the wallet out of your pocket and hand it to your enemy. Be sure that she'll hand the bill valued alpha back to you.
Author Note
After wrecking my brains for HOURS and HOURS, I was finally ENLIGHTENED by these few simple paragraphs! Hold My Dog!
2 comments:
sounds like some java comparison code logic
wah how come you so smart!
Post a Comment