10040 - Ouroboros Snake

[Emilio]

Hello there!

I'm trying this problem but I get WA. I have solved problem 10506 and use the same backtracking algorithm. Maybe I don't understand the problem specification or something. By this reason if anyone can say me the output for these test cases maybe I will realize my trouble.

Input:

Code: Select all

47
1 0
1 1
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
3 4
3 5
3 6
3 7
4 0
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
21 100
12 234
21 234523
21 234
20 3454
10 1023
21 2097151
21 0
21 123
10 1023
10 323
10 1022
10 1021
10 1020
10 1019
10 1018
10 1000

Thanks !

[vinay]

I really don't understand what to do with this problem

how is eulerian circuit applicable here???

can anyone tell how to visualize the problem in that way??

[chrismoh]

Read up on de bruijn sequences.

The simple way to think about it as an Eulerian circuit is for an n-bit number, think of all 2^(n-1) bit numbers as nodes and each node has two edges to represent the next bit - 0 and 1.

So, for example, for n = 3, we have four nodes:

00 01 10 11

00 has edge 0 to itself, 1 to 01
01 has edge 0 to 10, 1 to 11
10 has edge 0 to 00, 1 to 01
11 has edge 0 to 10, 1 to itself

And an eulerian cycle in this graph corresponds to a de bruijn sequence, by starting with a starting vertex and taking the edge labels as following the sequence.

So if I start with node 00, I could end up with

0001011100 which is a possible sequence. And note that the last (n-1) (in this case n-1 = 2) labels are redundant and therefore we end up with

00010111 which is a 2^3 = length 8 required sequence.

[pineapple]

First I always get MLE,then I modified my code for several times,now always WA.Who can help me?Give me some cases or point out my mistake,thanks very much.

The following is my code:

Code: Select all

Cut after AC

[red_apricot]

I can construct the parts of the Euler cycle, but my problem comes when those individual simple cycles have to be glued together to produce the lexicographically smallest bitstring... Short of the FKM algorithm, any ideas on how the cycles can be combined?

[red_apricot]

OK, here is my solution so far -- based solely on Euler cycles. Thanks to Per's post somewhere here I did figure out the way to generate lex-smallest Euler cycl.e The only problem is that this code works for n <= 20, and for n=21 stack overflows. Any ideas how to improve the code?

Code: Select all

/*
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 21
#define Q (1UL<<N)
#define BIT(k) (1UL << (k))
#define MASK(k) (BIT(k)-1UL)
#define TST(u,k) ((u) & BIT(k))
#define CLR(u,k) ((u)&=~BIT(k))
#define SET(u,k) ((u)|=BIT(k))
#define E(u,t) ((t) | ((u)<<1))
#define adj(u,t) ( (t) | (((u)<<1)&MASK(n-1)) )
#define USED(u) (TST(a[(u)>>3],(u)&7UL))
#define SET_USED(u) (SET(a[(u)>>3],(u)&7UL))
#define UNSET(u) (CLR(a[(u)>>3],(u)&7UL))
#define HAS_EDGES(u) (!USED(E(u,0))||!USED(E(u,1)))
enum { L, R };

typedef struct cell {
    struct cell *nx[2];
    unsigned int u;
} cell;
cell pool[Q+8],*next;

cell *init( unsigned int u ) {
    cell *x = next++;
    x->u = u, x->nx[L] = x->nx[R] = NULL;
    return x;
}

typedef struct {
    cell *head,*tail;
    size_t cnt;
} deque;

deque *dinit() {
    deque *q = (deque *)malloc(sizeof *q);
    q->head = q->tail = NULL, q->cnt = 0;
    return q;
}

void add_after( cell **item, unsigned int u ) {
    cell *p = init(u);
    if ( !*item )
        *item = p;
    else {
        if ( p->nx[R] = (*item)->nx[R] )
            (*item)->nx[R]->nx[L] = p;
        (*item)->nx[R] = p, p->nx[L] = *item;
    }
}

void push( deque *q, unsigned int u ) {
    add_after(&q->tail,u);
    (!q->cnt++)?(q->head=q->tail):(q->tail=q->tail->nx[R]);
}

unsigned char a[(Q>>3)+0x400],tr[(Q>>3)+0x400];
int n,K,cnt,SIMPLE_CYCLES;
unsigned int *res[N+1],q[Q+0x400],*ptr,*str,src;
deque *B;

int visit( unsigned int u ) {
    if ( u == src && ptr-q > 0 ) 
        return 1;
    if ( !HAS_EDGES(u) )
        return 0;
        if ( !USED(E(u,0)) ) {
            SET_USED(E(u,0)), *ptr++ = adj(u,0);
            if ( visit(adj(u,0)) )
                return 1;
            UNSET(E(u,0)), --ptr;
        }
        if ( !USED(E(u,1)) ) {
            SET_USED(E(u,1)), *ptr++ = adj(u,1);
            if ( visit(adj(u,1)) )
                return 1;
            UNSET(E(u,1)), --ptr;
        }

    return 0;
}

void euler_cycle() {
    unsigned int u,v,i,j,k,l;
    cell *qtr;

    memset(a,0,sizeof(a)), memset(tr,0,sizeof(tr)), cnt = 0;
    B = dinit(), next = pool;
    ptr = q, src = 0, visit(0);
    for ( push(B,0), i = 0; i < ptr-q; ++i ) {
        if ( !TST(tr[q[i]>>3],q[i]&7UL) )
            if ( HAS_EDGES(q[i]) )
                SET(tr[q[i]>>3],q[i]&7UL), ++cnt;
        if ( TST(tr[q[i]>>3],q[i]&7UL) )
            if ( !HAS_EDGES(q[i]) )
                CLR(tr[q[i]>>3],q[i]&7UL), --cnt;
        push(B,q[i]);
    }
    for ( qtr = B->tail; cnt; ) {
        for(;qtr && !TST(tr[qtr->u>>3],qtr->u&7UL); qtr = qtr->nx[L] );
        assert( qtr );
        src = u = qtr->u, ptr = q;
        assert( visit(u) );
        for (l=(qtr==B->tail), i = 0; i < ptr-q; ++i ) {
            add_after(&qtr,q[i]);
            if ( !TST(tr[q[i]>>3],q[i]&7UL) )
                if ( HAS_EDGES(q[i]) )
                    SET(tr[q[i]>>3],q[i]&7UL), ++cnt;
            if ( TST(tr[q[i]>>3],q[i]&7UL) )
                if ( !HAS_EDGES(q[i]) )
                    CLR(tr[q[i]>>3],q[i]&7UL), --cnt;
            qtr = qtr->nx[R], ++B->cnt;
        }
        if ( l ) B->tail = qtr;
    }
    0 && printf("[n = %d] bsize %u\n",n,B->cnt);
    assert( B->cnt == BIT(n)+1 );
    res[n] = (unsigned int *)calloc(B->cnt+2,sizeof *res[n]);
    for ( str = res[n], qtr = B->head; qtr; qtr = qtr->nx[R] )
        *str++ = qtr->u;
    for ( i = 0; i+1 < B->cnt; ++i )
        res[n][i] = E(res[n][i],res[n][i+1]&1UL);
}

int main() {
    int m,ts;
    for ( n = 2; n <= N; ++n ) {
        euler_cycle();
    }
    for ( scanf("%d",&ts); ts--; ) {
        scanf("%d %d",&n,&m);
        if ( n == 1 ) {
            printf("%c\n",m+'0');
            continue ;
        }
        printf("%u\n",res[n][m]);
    }
    return 0;
}