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. :oops:

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. :roll:

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. :lol:

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