10040 - Ouroboros Snake

[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.

[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.

[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.

[Red Scorpion]

Thanks, Andrey.

[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...

[Julien Cornebise]

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]

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]

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]

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]

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

[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

[Julien Cornebise]

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

mmmm... very interesting ! Thank you Larry !

[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....

[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

[L I M O N]

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

L I M O N