On Arithmetic Coding

Hi Friends. Long ago I wished to add some task on this algorithm, but had difficulty inventing something "ingestable". You'll see idea is simple, but implementation needs care and may be bit difficult to debug. However algorithm leds to further interesting ideas (like PPM - perhaps we'll add such variations later) so it is a pity not to have it.

The algorithm was not very popular for most part of XX century because arithmetics worked much slower in comparison with logic and data-moving operations, while benefit is not very large. But nowadays such obstacles are not important as 64-bit long values are multiplied in few clocks of CPU.

Now it is live, after about a week of struggling :) regretfully looking over the problem statement which tries to provide algorithm explanation, I see it is quite lengthy.

So let's regard it as a "work in progress" yet and if you would like to give any advices on making it more user-friendly (or perhaps you'll find some nasty bugs) - let's polish it.

Mathias, Hi and thanks a lot for report! Just a bit confused - which newline characters do you mean? those in the input?

Hm-m-m, it may be I confused something in the problem description, but there shoud be no line breaks in the output (as in most "good old style" problems), they are separated with spaces. I looked into your solution:

aac = AdaptiveArithmeticCoding()
for _ in range(int(input())):
    print(aac.decode(input()))

Unless I'm mistaken print(...) adds linebreaks...