2014-05-06

UVa 10040 - Ouroboros Snake

1. Background
2. Problem
3. Input
4. Output
5. Sample Input
6. Sample Output

Solution

Background

Ouroboros was a mythical snake in Ancient Egypt. It has its tail inside its mouth and continuously devours itself.

Problem

Ouroboros numbers are binary numbers of 2n bits that have the property of generating the whole set of numbers from 0 to 2n-1 as follows: To produce all of them we place the 2n bits wrapped in a circle so that the last bit goes before the first one. Then we can denote all 2n different strings with n bits starting each time with the next bit in the circle.

For example, for n=2 there are only four Ouroboros numbers. These are 0011, 0110, 1100 and 1001. For 0011, the following diagram and table depicts the process of finding all the bitstrings:

k 	00110011... 	o(n=2,k)
0 	00 	0
1 	 01 	1
2 	  11 	3
3 	   10 	2

Your program will compute the function o(n,k), where n > 0 and $0 \leq k < 2^n$. This function calculates the k-th number inside the smallest Ouroboros number of size n-bits.

Input

The input starts with a line containing the number of test cases. For each test case you will be given a line with two integers n (0 < n <22) and k ( 0 <= k < 2^n).

Output

For every test case your output must evaluate the function o(n,k) and print the result on a line by itself.

Sample Input

Sample Output

Solution

題目描述：

有一個 2^n 個 bits 的環，而這個環恰好任取連續 n 個會湊滿 [0, 2^n - 1]，現在找一個字典順序最小的環，接著詢問這個環的某一個位置開始的數值。

題目解法：

當詢問 n bits 的結果時，可以把圖建成 2^(n-1) 個節點，每一個節點有兩條邊，邊上分別為 0, 1，也就是說只要繞過所有的邊，相當於產生所有 2^n 個數字。

由於每一個點的 indegree = outdegree 一定存在尤拉迴路，接著在有向圖中找到一條尤拉迴路即可。

至於找字典順序最小環，使用 周源最小表示法 來找，如果可以的話希望能在搜尋時順便找到字典順序最小的。這裡就沒有系不去探究了。

以下是一個最簡單的版本，但這個版本在生成尤拉迴路時會遭遇到 stackoverflow。

TLE version because of stack overflow

#include <stdio.h>
#include <string.h>
char g[1<<21][2] = {};
int n, mask, highbit;
char order[2][1<<21], *p;
void dfs(int node) {
    int prefix = node;
    prefix <<= 1;
    for(int i = 0; i < 2; i++) {
        if(g[node][i]) {
            g[node][i]--;
            dfs((prefix|i)&mask);
    		*p = (i) +'0', p++;
        }
    }
}
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
int main() {
    int testcase, K;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &K);
        mask = (1<<(n-1)) - 1;
        for(int i = (1<<(n-1)) - 1; i >= 0; i--) {
            g[i][0]++;
            g[i][1]++;
        }
        p = order[0];
        dfs(0);
        *p = '\0', p++;
        int len = strlen(order[0]);
        for(int i = len - 1, j = 0; i >= 0; i--, j++)
            order[1][i] = order[0][j];
        order[1][len] = '\0';
        int o1 = MinExp(order[0], len);
        int o2 = MinExp(order[1], len);
        int f = 0;
        for(int i = 0; i < len; i++) {
            if(order[0][(o1 + i)%len] != order[1][(o2 + i)%len]) {
                f = order[0][(o1 + i)%len] > order[1][(o2 + i)%len];
                break;
            }
        }
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret = ret << 1;
            if(f == 0) {
                ret |= order[0][(o1 + i + K)%len] - '0';
            } else {
                ret |= order[1][(o2 + i + K)%len] - '0';
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

由於上述程式在走訪尤拉迴路時，由於深度過深而造成 stackoverflow 因此需要局部改寫成手動的 stack。通常主機只支持 10 萬到 20 萬之間的深度，這題最慘會到 100 萬。

並且將答案預建出來，如果沒有預建表會導致 Time limit，我以為只有少數幾筆，真是大錯特錯了。

#include <stdio.h>
#include <string.h>
#include <stack>
#include <algorithm>
using namespace std;
char g[1<<21][2] = {};
int n, mask;
char order[2][1<<21], *p;
char ouroboros[22][1<<21];
int olen[22];
void dfs(int node) {
    stack< pair<int, int> > stk;
    pair<int, int> state;
    int line;	
    stk.push(make_pair(node, 0));
    while(!stk.empty()) {
        state = stk.top(), stk.pop();
        node = state.first, line = state.second&3;
        if(line == 0) {
            int prefix = node << 1;
            if(g[node][0]) {
                g[node][0]--;
                stk.push(make_pair(node, 1|8));
                stk.push(make_pair((prefix|0)&mask, 0));
            } else {
                stk.push(make_pair(node, 1));
            }
        } else if(line == 1) {
            if(state.second&8) {
    			*p = (0) +'0', p++;
            }
            int prefix = node << 1;
            if(g[node][1]) {
                g[node][1]--;
                stk.push(make_pair(node, 2|8));
                stk.push(make_pair((prefix|1)&mask, 0));
            } else {
                stk.push(make_pair(node, 2));
            }
        } else {
            if(state.second&8) {
    			*p = (1) +'0', p++;
            }
        }
    }
}
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
void build() {
    for(int n = 1; n < 22; n++) {
        mask = (1<<(n-1)) - 1;
        for(int i = (1<<(n-1)) - 1; i >= 0; i--) {
            g[i][0]++;
            g[i][1]++;
        }
        p = order[0];
        dfs(0);
        *p = '\0', p++;
        int len = strlen(order[0]);
        for(int i = len - 1, j = 0; i >= 0; i--, j++)
            order[1][i] = order[0][j];
        order[1][len] = '\0';
        int o1 = MinExp(order[0], len);
        int o2 = MinExp(order[1], len);
        int f = 0;
        for(int i = 0; i < len; i++) {
            if(order[0][(o1 + i)%len] != order[1][(o2 + i)%len]) {
                f = order[0][(o1 + i)%len] > order[1][(o2 + i)%len];
                break;
            }
        }
        for(int i = 0; i < len; i++) {
            if(f == 0) {
                ouroboros[n][i] = order[0][(o1 + i)%len];
            } else {
                ouroboros[n][i] = order[1][(o2 + i)%len];
            }
        }
        olen[n] = len;
    }
}
int main() {
    int testcase, K;
    build();
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &K);
        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret = ret << 1;
            ret |= ouroboros[n][(i + K)%olen[n]] - '0';
        }
        printf("%d\n", ret);
    }
    return 0;
}

Morris' Blog

UVa 10040 - Ouroboros Snake

contents

Background

Problem

Input

Output

Sample Input

Sample Output

Solution