🦜 Parrots

Intro

One of my favorite competitive programming tasks (IOI 2011). You don’t have to actually write any code — just come up with a way to do the task. Suitable for a) people familiar with binary, or b) programmers, or c) people who kinda liked math in school.

Problem statement for non-programmers (rephrased)

  1. Jaxon has an N byte file, which he wants to send to Lachlan. They both know how big the file is.

  2. They don’t have internet (b/c Australia) so they are going to use parrots. Each parrot can memorize a single byte. Bytes are just whole numbers from 0 to 255.

  3. However, parrots don’t necessarily arrive in the same order they departed. So if the file is [1,2,3], Jaxon can’t just take three parrots and teach them the numbers 1, 2, 3 — because the parrots might arrive in the opposite order 3, 2, 1 (or in any other order). He’ll need to be cleverer.

  4. Naturally Jaxon will have to use more parrots than N. It’s alright. We love you anyway, Jaxon. Would be nice to use as few parrots as possible though. Are you listening, Jaxon. Listen to me.

If it’s unclear, you can read the full original statement here. I got rid of some extra cases because I don’t like them.

Problem statement for programmers

Write an encoder and decoder for messages (arrays of bytes). Your decoder will be given the length of the original message.

  • encode(msg: uint8[]): uint8[]
  • decode(n: int, data: uint8[]): uint8[]

The decoder must be able to correctly decode the message even if the data is randomly shuffled after encoding. That is, decode(length(msg), random_shuffle(encode(msg))) == msg for all msg.

Levels of difficulty

  • ONE BROWNIE POINT: the file is N \leq 16 bytes long, and Jaxon can use at most 10 \times N parrots. Doesn’t have to be optimal.

  • TWO BROWNIE POINTS: the file is N \leq 32 bytes long, and Jaxon can use at most 10 \times N parrots. Also doesn’t have to be optimal.

  • RED VELVET CAKE: come up with the optimal solution that works for any N. Optimal means “minimize the maximum number of parrots you’d possibly need”.

Solution for N = 2 (read if you didn’t get the task)

You can always use three parrots to send a two-byte file. Here’s how:

If the file is [A, B], you just teach two parrots A and one parrot B. This works because:

Even if the parrots get shuffled on their way to Lachlan, he can look at which byte is more common and he’ll know it was the first byte of the file.

4 Likes

I don’t have a solution specifically for the second level, but the first and the third both seem pretty simple to brute force. (And if you can solve the third, I guess that also solves the second, if not as elegantly.)

For the first:

Use the first 7 bits of each byte for a sequence number, with the actual information only in the last bit of each byte. Using only one bit per byte means that you need 8 \times N parrots, and using a seven bit sequence number allows you to send a message requiring up to 2^7 = 128 pieces (parrots). If each parrot carries one bit, that’s \frac{128}{8} = 16 bytes, precisely what we need for the first level of the problem.

For the third:

With k parrots, you can distinguish between exactly \binom{k + 256 - 1}{k} possible message encodings, a la the classic “balls and urns” combinatorics problem. Each parrot is a “ball” and you’re putting it into one of 256 “urns”, each labeled by an 8-bit integer, based on which byte the parrot carries. Decide on an order for these encodings, these 256-tuples of integers, say the lexicographical order. (The first element of such a tuple is the number of parrots carrying the byte 000000, the second the number of parrots carrying 000001, the third the number of parrots carrying 000010, etc.) Now you have a bijection between the \binom{k + 255}{k} possible message encodings and the natural numbers from 0 to \binom{k + 255}{k} - 1 — which will be the decoded message. (You’re given N when decoding the message, so you can, say, sort the set of length-N arrays of eight-bit integers lexicographically and use that number as an index into that ordering to recover the original array.)

To encode a message of length N, you need to choose a k such that 8^N = 2^{3N} is less than or equal to \binom{k + 255}{k}, so choose the least k such that \frac{log_{2}\binom{k + 255}{k}}{3} \geq N.

1 Like

@zzq Excellent job on both.

Actually implementing the bijection is slightly non-trivial, especially in 2011 when people mostly didn’t have access to bignums in competitions. But even with bignums it’s still fun to implement. I didn’t participate in IOI but my classmate was a strong competitive programmer and he didn’t manage to come up with the bijection idea at all, IIRC.

1 Like

When viewed as a pure math puzzle (as indeed you presented it) this problem is much easier to tackle than when approached as a competitive programing puzzle.

Viewing it as a math problem, I started by thinking “if I can find the number of possible encodings for any given number of parrots, I can put those encodings in a bijection with the natural numbers less than it.” That’s why I called this solution “brute force”—it enumerates all possible encodings and builds a lookup table matching that list to all possible messages that could be sent. With that as a starting point, all that was left was to identify that this was a combinatorics problem, which made it trivial to calculate that number.

If you start with the notion that you put the possible encodings in a bijection with a subset of the naturals, the rest of the problem is relatively easy. But approaching this from a competitive programing angle, you’d probably start from the opposite direction—and that, I imagine, makes it a lot harder.

Ah, I finally got the third one while sitting in the car park waiting for my wife to give blood! So here’s what I came up with:

For N<=16: use the first 4 bits to encode which word (byte) of the file it represents. Then use the next 2 bits to encode which pair of bits in that word we’re sending. Use the final 2 bits to send those two bits. This uses 4 parrots per byte sent, and works for up to 2^4 words.

For N<=32: write the whole file as a bit string (max length 256 bits). Each parrot is a byte representing an index position in the bit string, 0-255. Send a parrot for each 1 in the bit string. On average you’ll have to send 128 parrots for a 32 byte file, as half the bits will be 1s.

For arbitrary N: extending the previous method, break the file into successive 256 bit strings. Send 1 parrot for each 1 in the first 256 bits, 2 parrots for each 1 in the 2nd 256 bits, 4 for each in the 3rd, 8 for each in the 4th, and so on. So say I receive 23 parrots with the value 27: I know 23 is 10111 in binary, so there is a 1 in the 27th place in the 1st, 2nd, 3rd and 5th sequence of 256 bits. Parrots used is stochastic, depending on message, so I’m sure it’s not optimal!

1 Like

@clivemeister

  • N\le16 – looks correct.

    You are using 6 bits for position. This turns out to be more efficient than using 7 bits for position as @zzq did. In general if you spend X bits on position you can send 2^X things of size (8-X) bits. If you try for all possible X-es, only 6 and 7 bits let you transmit 16 bytes.

  • N\le32 – also looks correct.

    256 parrots in the worst case but it’s still less than 10\times N, so well done. Cleverly uses the fact that the number of parrots doesn’t have to be constant. That’s kinda cool actually.

  • Arbitrary N – even more cleverly uses the same fact (I’m jealous), but yeah, it’s not optimal.

    (Just judging by the fact that it heavily privileges messages with lots of zeroes.)

    If you want a slight (moderate?) hint re/ optimal solution, here’s a hint → the optimal solution is entirely completely different.

Ah, I came up with a path to a solution that’s probably closer to optimal for arbitrary N. It goes something like:

We might be able to use Multisets! I needed to read up in Wikipedia on this, I admit - in programming, I’d think of them as the datatype Bag. Then our message is a Bag of parrots, containing some number of each parrot, where parrots have a value 0-255. So the message is a Multiset, with the cardinality of the Multiset large enough to cover the message space, with the message interpreted as a binary number with all the digits concatenated together. So some number in the range 0-N^2^3, for N digits. We establish a 1-1 mapping from all possible Multisets to the numbers in the range to N^2^3 (just some intuitive ordering of the possible multisets will do), then we can send the Bag of parrots, work out which multiset we’ve got, and map back to the number, i.e. to the message. Seems like this should work!

Wikipedia tells me that I need to use the “multiset number” to work out how many parrots I’d need for any message, and I can write this down on a bit of paper, but my ability to write it onto this forum post is limited by my knowledge of math notation in markup, so this is left as an exercise for the reader :slight_smile:

Right, now I’m going to read your hint, see if it was going in this direction or not…

@clivemeister That’s correct! You get a slice of the red velvet cake.