3 ms·
AFAIK, information theory requires the _Expected_ size of a 'compressed' file be at least as large as the original. So we could create an encoding that compres
by thomasahle 12y ago
AFAIK, information theory requires the _Expected_ size of a 'compressed' file be at least as large as the original.
So we could create an encoding that compressed N/50 of the strings with lg(N/50)=lg(N)-lg(50) bits. That would save us lg(50) > 5 bits with 2% chance. In this game we have 50 tries (5000$/100$) so we'd be pretty sure to win.
The correct price for this game is probably closer to 200$.
- Dylan16807 12y agoThe problem is that even the most trivial linux-compatible decompressor will add a few bytes, and there's almost no chance of saving that many bytes. But sure it wouldn't hurt to require it be 100+ bytes smaller.