Log In

Romanian Informatics Olympiad - Modified Huffman Encoding

Posted on: January 1st, 2013 by
Comments Disabled

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.

via CSE Blog - quant, math, cse puzzles.

Comments are closed.

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}