## Romanian Informatics Olympiad - Modified Huffman Encoding

Posted on: January 1st, 2013 by

A telegraph machine can transmit only lines and dots; it takes 2 seconds to transmit a line, but only 1 second to transmit a dot. We generally want to transmit texts containing letters of the English alphabet, and digits so we have N<=36 symbols in total. Therefore, a prefix-free encoding using lines and dots is needed. Given the frequencies of the N symbols in a large text, find the minimum time it takes to transmit the text using a suitable encoding. The solution should run in ON^4 time, and use ON^3 space.

Posted on: January 1st, 2013 by

The king of the universe has decided to play a game. To start, he selects 1 person. He then flips two fair coins - if they both come up heads, the person gets a free pizza and the game is over. For any other result, he sends the person home and selects 2 new people, where he does the same 2-coin flip to decide if they each get a pizza. If they don’t, he picks 4 people at random, then 8, and so on, doubling each round. If you are selected but don’t win, you can’t be selected again – and you can assume the population is extremely large so there’s no chance of running out of contestants.

You are sitting at home when you get a call – you have been selected to play the game. What is the chance that you will get a free pizza?

You don't know which round number it is, but if you ask, the king will tell you. Does it matter?

## CRIMINAL CUPBEARERS

Posted on: December 28th, 2012 by