データ構造と入力の順列

最近コードフォーセズの問いにかなり悩んだ。The problem was, given a00, a01, a10, and a11, the number of 00, 01, 10, and 11 subsequences in a binary string, find a feasible string or output "Impossible". The first insight was that the number of 00 or 11 sequences must be k choose 2, where k is the number of zeroes or ones. The second was that the product of the number of zeroes and ones must equal a01+a10. Lastly, if all "a" values or 0, the string "0" or "1" could be the source. If the a01 or a10 value is non-zero (and the conditions above hold), the string can be laid out as 000...1111 (a01>=a10) or 1111...000 (a10>a01). The, 0's (first case) or 1's (second case) are shifted right, starting with the rightmost of them, until the number of shifts accounts for a10 (first) or a01 (second).
The check that the number of 00 or 11 pairs is a valid "choose 2" is done by caching the k choose 2 values up to where the number of choices is 10^9.