信息论在 ACM Online Judge 中的应用

可惜不是解题的作用,是信息论在获取用于 Online Judge 的 test data (只包括输入部分)的作用,如果你不介意这一过程中无数的 WA 和反复的提交的话。

从系统角度看,信源是 Online Judge 的 test data;信道是从提交程序的运行,到 Online Judge 的判断,最后判断结果通过网络到达本机的整个信息通道。

首先,看下一次提交能获得的信息量。从 Online Judge 的返回数据中,拥有最大信息量的是哪些呢?是 run time 和 run memory!前者一般可以提供大约 6bit 的信息量(10ms ~ 1s,10ms 的分辨率,可以通过空循环控制),而后者提供的信息量超过 20bit (数百kB ~ 32MB,4B 的分辨率,可以通过内存分配控制)。不过需要注意的是这两者都不是完全精确的。
接下来,看下作为信源的 test data 的信息量。一般情况下,输入的字符大概是 0 ~ 9 的数字,加上空格,每个字符约 3.5bit。
这样看来,即使是保守估计,一次提交也能获得 8 个字符的 test data。

从上面看到了,从 Online Judge 获得 test data 是可能的。接下去,就是把信息论的信源信道编码用上这个系统了。不过要注意,编码处理同时会影响 run time 和 run memory 的准确性。既是说,相当有趣的,在这一应用中,信道编码会影响信道质量
作为信源的 test data 一般有冗余。用来压缩 test data 的信源编码可以用最简单的 Huffman 编码,也可以用经典的自适应的 LZW 算法,或者是针对该题的输入模式定制的编码方案。
刚才提到了,run time 和 run memory 不一定是精确的。换句话说,信道有噪声。假设我们能估算出噪声的分布(比如说 run time 的误差小于 20ms,或者,信源编码会使 run memory 增加约 100kB 左右,等等),那么我们就可以应用信道编码了,从最无趣的重复冗余,到复杂的卷积码或 LDPC,都能无损解码出信源数据。

好了,上文纯属EP,与一切组织及个人无关。。。

Advertisements
This entry was posted in Science. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s