## 10040 - Ouroboros Snake

Moderator: Board moderators

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

### 10040 - Ouroboros Snake

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?

Andrey.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
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.

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
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.

Andrey.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Thanks, Andrey.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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...

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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..)

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Try reading up a little on de Bruijn Sequences/Graphs..

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
Larry wrote:Try reading up a little on de Bruijn Sequences/Graphs..
mmmm... very interesting ! Thank you Larry !

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
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....

kronenthaler
New poster
Posts: 3
Joined: Tue Oct 26, 2004 9:09 pm

### 10040 what's wrong

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;
int i;
for(i=0;i<n;i++){
}

for(i=0;i<k;i++){
ret=ret<<1;
last=last>>((n<<1)-1);
ret|=last;
}

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

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am