Send the pairs in smallest output Write two programs A and B. 


Program A (the encoder) takes 1024 pairs of integers \$(k,v)\$, where \$0≤k&lt;2^{32}\$ and \$0≤v&lt;1024\$, and all \$k\$ will be different. It will output a single positive integer (likely a few thousand digits long).
Program B (the decoder) takes two inputs: the output-integer of program A, and one \$k\$ from the input pairs we've used as input for program A. It will output the \$v\$ corresponding with the given \$k\$.


In other words, Program A compresses 1024 key-value pairs to the smallest size possible, and Program B must use the data provided by A to recover each value given its corresponding key.

Your score is the average value of the output of program A for the test data. Hardcoding for a given test case is forbidden, so this should be essentially the same as the score on the pretest data. Pretest data and test data are drawn from the same (uniform) distribution.

Random pretest data is available here.

Random.txt
MD5: 6FA62A283282F5CFBC6E089B2369C9B9
SHA1: 0BF7FB62A8566575D4A948DD34A559BAAAC422FC
CRC32: 2675DAB3

Testdata.txt
MD5: 6C8F90F126C8F3C55A9FC9F22733CE55
SHA1: F7D11AAB54393DE8CC4E75565950D8C6D9CFE42A
CRC32: B3DB1479


Actual test cases:

https://www.mediafire.com/folder/i6hmn9zzk73ig/174035

A stupid program A that work but totally didn't optimize is here. Its program B is easily written.
Python 3, pretest ≈ 3.198 · 103085

from hashlib import sha512
import sys

def encode(pairs):  # program A
    elim = [[] for i in range(10)]
    done = set()
    code = 0
    i = 0
    while len(done) &lt; 10 * len(pairs):
        e = 1 &lt;&lt; i
        for a, e1 in elim[i % 10]:
            if decode(e, a) &amp; 1 &lt;&lt; i % 10:
                e ^= e1
        for a, b in pairs:
            if (a, i % 10) not in done and decode(e, a) &amp; 1 &lt;&lt; i % 10:
                elim[i % 10].append((a, e))
                done.add((a, i % 10))
                if (decode(code, a) ^ b) &amp; 1 &lt;&lt; i % 10:
                    code ^= e
                print("progress:", len(done), "of", 10 * len(pairs))
                break
        i += 1
    return code

def decode(code, a):  # program B
    k = -(-code.bit_length() // 8)
    a_bytes = a.to_bytes(4, "little")
    s = b"".join(
        sha512(a_bytes + i.to_bytes(4, "little")).digest() for i in range(-(-k // 64))
    )
    b = 0
    for i, (x, y) in enumerate(zip(code.to_bytes(k, "little"), s)):
        b ^= (x &amp; y) &lt;&lt; i * 8 % 10
    return b &amp; 1023 ^ b &gt;&gt; 10

def read_pairs():
    return [tuple(map(int, line.split())) for line in sys.stdin]

def test(pairs):
    code = encode(pairs)
    for a, b in pairs:
        assert decode(code, a) == b
    print(code)

test(read_pairs())


Pretest output

The encoder (program A) takes about 6 minutes to run in PyPy.  Its output for the pretest is:

31983609135966228809777741024866634396367955850954563312910243722966419655757435319862170247982609333805811315728884450895580799383047152743378820273077053884539894357668608677003723034054150072472679319590110643492810118920515801395958239291576592748237372467748241886558720871264342908155191777359585845696600370935487361341785211913110481040589139281898484188938846817560295768498881287225642023856190028544427590648046456036574330957328066402924125404073006144179946215625958643494081212962075340324684130280414625483652805036566339457267551141894682726365505972133784971174734160698976154775811488656096461968463830423074194023690503590590775033695214423998615444187716064686144001451215863398975347419967640878071667106313050954800893007781291647431510389526738768573353015452189679155051541561231146940706328809607485776138460159591319080343284358448724370020894125934538601889550086934233091980254236012141359542061770911092807766526451019824031548581065916355093797436687555279312288875998494044065641530299531661256941700326425163573657004343895103496724901715610405315696830871086538183435694121760474073023458471744226820280782007502797691083190318324487197753443963571848733746071847847503077912802000091614327968964141450181973360651625471354587026290724846906554164924720066533282988840115094797514460217879380690461261835733295861803705394151420199059533051945944829244868440580371672125590557347324783817602474773801825029895884776404639198926793779867410515553784121435319134307253638568331529787781235084628432871984360992875472633958491882569077293145250495277979952525973740358428525766027507530317692602517027217679810063987302625422496799748842451355136627998296037177558122844929449377522984595368107136303866235523533278732324181522202203636626264487517560120680389621562028772569157498411869721766672498939022664474767985892820170334179252554511620260319259569593256276255895000364202791049913505972232782566530566341223654980901733905002516092163056581626593518077383131036496001950185439305868415290006860241666136700655660075381115903744293277973930796274779653647714016073922883203769217980038066409200998466193202329090278491648479911508276027286548829602558975386937067679077276971208214625876007703346632539055994199462748282900998214486645162277623073498410220953186861172886747394992230973314265902007187446129816157393697305312624793190210450979525381906198852578619071224265649145441460469662250448218764499047348362548750003370944772956154662554023857705149861774126960045122299555516709305181620013892453158471100545618056605123335183465355868672237737792628988379889459029444873409805140995088383991356246685699313569301017907549835057806089472106637383136584875471496123974387658318450782138871582131161643221907721116143710024435066884630344739171885220542678102635637192667329306874983507141585026570891055701250722003923329858567937864129882737742073320064153568198296932909448928951903564049064190959836027425436414766746048788435990514173396582362591284614310722316033029018983309186148295917238363165751109139219360789557442877663768774219


which you can use to verify the much faster decoder (program B) if you don’t want to wait for the encoder.

How it works

The decoder expands \$a\$ into a deterministic pseudorandom stream using SHA-512, bitwise ANDs the stream with the code (output of program A), and bitwise XORs all the base 1024 digits of the result.

It has the important property that the decoder is a linear function of the code: decode(code1 ^ code2, a) == decode(code1, a) ^ decode(code2, a).  Therefore, the encoder can compute the needed code using Gaussian elimination.

Scoring note

For official scoring, please make the thoroughly negligible “output formatting” adjustment of adding 1 to the code value, since otherwise a theoretically possible output is 0, which is not a positive integer.  As of this writing, the other answer has the same property.