10040 - Ouroboros Snake

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sat Dec 10, 2005 5:26 am

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 :wink: !
SoMe pRoBlEmS ChAnGe mY MiNd

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

help !!!

Post by vinay » Sat Jul 29, 2006 2:17 pm

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

how is eulerian circuit applicable here???

can anyone tell how to visualize the problem in that way?? :cry:
If I will myself do hashing, then who will do coding !!!

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh » Wed Aug 23, 2006 4:43 am

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
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

10040 - MLE -> WA please help!

Post by pineapple » Fri Feb 09, 2007 7:49 am

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
Last edited by pineapple on Fri Aug 24, 2007 5:23 pm, edited 1 time in total.

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10040 - Ouroboros Snake

Post by red_apricot » Wed Jul 23, 2014 9:33 am

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
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 10040 - Ouroboros Snake

Post by red_apricot » Fri Jul 25, 2014 5:15 am

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;
}

Post Reply

Return to “Volume 100 (10000-10099)”