2014-07-23

UVa 11632 - Elias gamma coding

1. Problem
2. Input Specification
3. Sample Input
4. Sample Output
5. Solution

Problem

The Elias gamma code is a simple code which can be used to encode a sequence of positive integers. We will use a modified code which is also able to encode zeros. To encode an integer n, do the following:

Let k be the number of bits of n
Write k-1 zeros followed by a 1
Write n in binary

Examples

Number     Binary     Number of bits     Prefix     Code
0     0     1     1     10
1     1     1     1     11
2     10     2     01     0110
3     11     2     01     0111
4     100     3     001     001100
5     101     3     001     001101
6     110     3     001     001110
7     111     3     001     001111
8     1000     4     0001     00011000

A sequence of integers is encoded by writing the codes of the individual integers of the sequence in the same order as the integers appear in the sequence. The prefix of k additional bits before the binary representation of each integer is needed to be able to decode the encoded integers. So when reading the encoding of a sequence of integers, if we read k-1 zeros followed by a one, it means that there are k bits following which are the binary representation of the next encoded integer.

If we want to shorten the length of the encoding of a sequence of integers, there may be still some room for improvement; we will consider the following two optimizations:

If there is a prefix which indicates that k bits are following, but there is no integer in the sequence with k bits, we can use this prefix to indicate that k+1 bits are following. If there already was a prefix which indicates that k+1 bits are following, this prefix is not needed anymore, and it can be used to indicate that k+2 bits are following, and so on.
We can add a leading zero to the binary representation of all integers in the sequence with k bits, which then become integers with k+1 bits, and then the first optimization can be used. This optimization seems especially useful if there are few integers with k bits, but many integers with more than k bits.

When we are minimizing the length of the encoding of a sequence of integers, we only care about how many integers in the sequence have a certain number of bits. Let ci denote the number of integers in a sequence with i bits.

Let us look at the following example: c1 = 2, c2 = 4, c3 = 0, c4 = 1 (which, for example, could correspond to a sequence 2, 1, 3, 8, 0, 2, 3). With the original elias gamma coding, the encoding of the sequence would have length 2 × (1 + 1) + 4 × (2 + 2) + 0 × (3 + 3) + 1 × (4 + 4) = 28. By using optimization 1 we can save 1 bit by using prefix 001 for the integer with 4 bits. Then, we could use optimization 2 and add leading zeros to the integers with 1 bit, making them use 2 bits. Then, we use optimization 1 and use prefix 1 for the integers with 2 bits, prefix 01 for the integer with 4 bits, and we get the new length of 6 × (1 + 2) + 1 × (2 + 4) = 24.

Both optimizations can possibly be used several times. Note that for the second optimization, it is not easy to decide when and how to use it. The goal is to combine these two optimizations in the best possible way, that means we want to find an encoding of a given sequence of integers that has minimum length among all encodings using elias gamma coding with any combination of these two optimizations.

Input Specification

The input file contains several test cases. Each test case starts with a line containing an integer n, (1 ≤ n ≤ 128). The next line contains the values c1, …, cn (0 ≤ ci ≤ 10000). Input is terminated by n=0.
Output Specification

For each test case print one line with the minimum length of an encoding of the given input sequence.

Sample Input

4
2 4 0 1
5
9 4 2 4 3
11
44 56 96 26 73 80 77 50 33 16 78
0

Sample Output

1
2
3

24
99
5494

Solution

題目描述：

對於一個編碼而言，假使全部存放數字，採用固定長度的方式儲存，就類似全部使用 32 bit 形式，但這樣會浪費相當多的首位 0，因此題目給定多一個欄位表示接下來會有多少 bits，這樣方式有可能會增加編碼長度，因此會有以下優化。

將一個原本使用 k bits 表示的數字，使用多於 k bits 表示，也就是多補給個 0。
對於欄位表示，將使用映射的方式進行，由於前一條規則，將會有無用的欄位格式，因此可以將比較短的表示法給更多 bits 的數字使用。

題目解法：

題目相當冗長，其實就相當於將 3 bit 數字弄成 4 bit，並且讓 3 bits 和 4 bits 共用同一種欄位表示法 (001 之類的，原本 4 bit 必須使用 0001，現在反而能用更少。)。

使用 dp[i][j] 表示前 i bits 表示法使用最大 j bits 欄位的最小成本。

1 2	dp[j][k] = min(dp[j][k], dp[i-1][k-1] + sum * (k + j)); // sum 表示 [i, j] 之間的 bits 數字總量，k + j 表示單一數字的表示長度。

#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
int main() {
    int n, A[256];
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        int dp[256][256];
        memset(dp, 63, sizeof(dp));
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++) {
            int sum = 0;
            for(int j = i; j <= n; j++) {
                sum += A[j];
                for(int k = 1; k <= n; k++) {
                    dp[j][k] = min(dp[j][k], dp[i-1][k-1] + sum * (k + j));
                }
            }
        }
        int ret = 0x3f3f3f3f;
        for(int i = 0; i <= n; i++)
            ret = min(ret, dp[n][i]);
        printf("%d\n", ret);
    }
    return 0;
}

Morris' Blog