这是翻译成中文的题目描述:
一个区块是TON区块链中的基本数据结构,包含一组交易、消息以及前后区块链状态之间的差异。
为了减少网络负载,区块的高效压缩至关重要。在本次比赛中,你的任务是实现一个压缩算法,该算法将在来自真实TON区块链的区块上进行评估。
在TON中,所有内容都由单元(cell)组成。如果你参与过FunC比赛,可能已经熟悉这个概念。单元是一种数据结构,包含最多1023位的二进制数据,以及最多4个对其他单元的引用。一个根单元及其可达的所有单元组成一个单元包(bag of cells)。区块被表示为一个单元包,其结构可以通过TL-B模式形式化描述(参见备注部分中的链接)。
区块使用单元包的序列化算法被序列化为一个字节串。这个字节串是本问题中作为输入数据的区块表示形式。
交互方式
对于每个测试,你的程序会被执行两次:一次用于压缩,一次用于解压缩。
第一次运行(压缩)
输入的第一行包含一个单词:“compress”。第二行包含一个经过Base64编码的区块。
输出为Base64编码的压缩区块。
第二次运行(解压缩)
输入的第一行包含一个单词:“decompress”。第二行包含第一次运行输出的Base64编码压缩区块。
输出为Base64编码的解压缩区块。
限制条件
区块的最大大小为 2 \cdot 2^{20} 字节。压缩后的区块大小不得超过 2 \cdot 2^{20} 字节。
注意:这些限制指的是解码后的数据大小,而不是Base64编码后的表示形式。
评分规则
对于每个测试,基于压缩效率对你的解决方案进行评分。
解压缩后的区块必须与原始区块相同,否则该测试将被标记为错误(WA)并得0分。
如果原始区块和压缩区块的大小分别为 x 和 y,那么该测试的得分为 1000 \cdot \frac{2 \cdot x}{x + y}。
测试集
比赛期间,你的解决方案将在一个封闭的初步测试集上进行评估。该测试集由TON主网上的各种最近区块组成,结果将显示在公共排行榜上。
初步测试集中的前25个测试是公开可用的,可以通过ton-sample-tests.zip下载。你也可以从TON区块链下载更多区块进行本地测试。
比赛结束后,你的解决方案将在一个不同的最终测试集上进行评估。该测试集将由比赛结束后TON主网上生成的区块组成。在最终测试中,将采用初步测试中你得分非零的最新提交。
备注
你的解决方案将链接到C++库ton_crypto_lib。该库基于TON主库,包含用于操作单元、解析区块以及使用LZ4压缩算法的工具。在提交解决方案时,选择语言为 “C++17 (clang 18-64 + ton_crypto_lib)”。可在此处找到下载和链接库的说明。
以下是解决方案示例,展示了如何使用ton_crypto_lib进行Base64解码和编码、单元序列化和反序列化以及LZ4压缩和解压缩。
本地构建与ton_crypto_lib示例
下载ton-compress-contest-examples.zip,其中包含解释TON概念和展示如何使用库的代码示例,以及为Linux和MacOS构建解决方案的脚本。使用方法如下:
Linux: 解压ton_crypto_lib-x86_64-linux.zip,运行 ./run-linux.sh solution.cpp
MacOS: 解压ton_crypto_lib-x86_64-macos.zip,运行 ./run-macos.sh solution.cpp
Windows: 下载ton-compress-contest-windows.zip,其中包含已配置的MSVC++项目。
可在此处找到手动配置的说明。
本地测试
你可以使用ton-local-tester.zip中的Docker镜像测试你的解决方案:
将你的解决方案放入solution.cpp
tests目录包含25个公开可用的测试,你可以向该目录添加自定义测试。
安装Docker并运行:
参考文档
TON区块链白皮书:包含区块链结构和区块格式的详细描述。
block.tlb:TON数据结构的正式规范。TL-B格式概览。
单元:关于单元的文档。
主网浏览器:区块链浏览器。