Page **1** of **2**

### 10040 - Ouroboros Snake

Posted: **Fri Feb 07, 2003 10:54 am**

by **Andrey Mokhov**

I got AC on this problem but I'm not satisfied with my solution.

I used Eulerian curcuits to precompute all the answers - as a result I used about 30 Mb memory and my program ran 1.3 seconds. And it gave me Time Limit without precomputing. But I saw in the ranklist people who got AC in less than 0.1 seconds.

Will anyone tell me the right way of solving the problem?

Thanks in advance.

Andrey.

Posted: **Fri Feb 14, 2003 6:43 am**

by **Red Scorpion**

Hi, Andrey I try to solve this problem too, but don't have any idea. You say used Eulerian circuits can break that problem, Can you tell me a bit what is "eulerian circuits" ?

Thanks.

Posted: **Fri Feb 14, 2003 12:27 pm**

by **Andrey Mokhov**

Eulerian curcuit in a graph is such a curcuit that uses each edge in it exactly once.

There is a lot of literature on the algorithm of building Eulerian curcuit in graphs but unfortunately I don't know any link.

Buy.

Andrey.

Posted: **Sat Feb 15, 2003 5:46 am**

by **Red Scorpion**

Thanks, Andrey.

Posted: **Sun Apr 27, 2003 6:46 pm**

by **yiuyuho**

Is there something wrong with the sample input?

it says the first line is the number of test cases, it's a 6, but only 4 pairs is followed...

Posted: **Sun Jul 11, 2004 6:08 pm**

by **Julien Cornebise**

yiuyuho wrote:Is there something wrong with the sample input?

it says the first line is the number of test cases, it's a 6, but only 4 pairs is followed...

Read the subject and remember what's ouroboros : you can loop.

Posted: **Sun Jul 11, 2004 6:13 pm**

by **Julien Cornebise**

yiuyuho wrote:Is there something wrong with the sample input?

it says the first line is the number of test cases, it's a 6, but only 4 pairs is followed...

Read the subject and remember what's ouroboros : you can loop.

Posted: **Mon Jul 12, 2004 6:11 pm**

by **Larry**

I don't know about the *really really* quick times, but I'm ranked 12th or so, and I used the FKM algorithm.. (without precalcing..)

Posted: **Thu Jul 15, 2004 9:35 am**

by **Julien Cornebise**

Larry wrote:I don't know about the *really really* quick times, but I'm ranked 12th or so, and I used the FKM algorithm.. (without precalcing..)

Hi

I'm really stuck on this problem : I found a solution using ... hamiltonian cycle

(edges : numbers, connected to their possible followers, ie n << 1 | 1 and n<<1)

I don't see wich is the graph for eulerian cycle solution, and I don't know the FKM algorithm

Could you please give me a hint ? (not the solution !! only a hint).

Thank you

Posted: **Thu Jul 15, 2004 10:11 pm**

by **Larry**

Try reading up a little on de Bruijn Sequences/Graphs..

Posted: **Sun Jul 18, 2004 2:45 pm**

by **Ivor**

The first three times -- 0.000 and 0.002 are probably nothing more than simple io solutions, ie one of them told me he had io somewhere and sent it. I think there might be a really easy solution to this problem but I didn't find one. The solution I have is DeBrujn cycles algorithm. Wish I could remember it's essence as it's almost two years since I got my time. I found an algorithm on one site, I might even find a link. I studied it not that much alogorith-wise as code-wise. That is I discarded any code not necessary to compute a solution and did a hell of optimization. Basicly that's it. Adapting reasonably you'll get a time at 0.1 seconds. To get my time you have to go through spikes.

At least I did. The idea is the same but the implementation was awkward, hard and painful but fast.

Ivor

Posted: **Tue Jul 20, 2004 11:48 pm**

by **Julien Cornebise**

Larry wrote:Try reading up a little on de Bruijn Sequences/Graphs..

mmmm... very interesting ! Thank you Larry !

Posted: **Thu Sep 16, 2004 5:45 pm**

by **Maniac**

I got AC with an Euler-circuit-algorithm in Java in 1.8 sec, but I also got AC with a backtrack-algorithm in C++ in 1.0 sec. So less intelligent solutions can also work very well here

Both first compute all ouro-strings and then start handling test cases by the way....

### 10040 what's wrong

Posted: **Thu Apr 07, 2005 11:35 pm**

by **kronenthaler**

hi it's the problem ourboros snake,

i saw as a simple bit manipulation problem but uva don't thing equal.

this is my code :

#include <stdio.h>

#include <stdlib.h>

#define ulong unsigned long long

/* 10040 */

ulong doit(int n,int k){

ulong ret=0;

ulong mask=0x01;

ulong masks=0x00;

ulong maskw=0x00;

int i;

for(i=0;i<n;i++){

ret|=(mask<<i);

maskw|=(mask<<(i+n));

//maskw|=(mask<<i);

}

masks=ret|maskw;

for(i=0;i<k;i++){

ulong last=ret&(mask<<((n<<1)-1));

ret=ret<<1;

last=last>>((n<<1)-1);

ret|=last;

ret&=masks;

}

return (ret>>n);

}

int main(){

int cases,n,k;

scanf("%d",&cases);

for(int i=0;i<cases;i++){

scanf("%d%d",&n,&k);

printf("%ld\n",doit(n,k%(2*n)));

}

return 0;

}

some idea?

PD: sorry my english

Posted: **Tue Apr 12, 2005 8:44 pm**

by **L I M O N**

to Maniac,

do u pls explain ur backtracking approach? i got TLE using backt.

L I M O N