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

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

10040 - Ouroboros Snake

Post by Andrey Mokhov » Fri Feb 07, 2003 10:54 am

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.

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

Post by Red Scorpion » Fri Feb 14, 2003 6:43 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. :roll:

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

Post by Andrey Mokhov » Fri Feb 14, 2003 12:27 pm

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

Post by Red Scorpion » Sat Feb 15, 2003 5:46 am

Thanks, Andrey. :lol:

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sun Apr 27, 2003 6:46 pm

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:

Post by Julien Cornebise » Sun Jul 11, 2004 6:08 pm

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:

Post by Julien Cornebise » Sun Jul 11, 2004 6:13 pm

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:

Post by Larry » Mon Jul 12, 2004 6:11 pm

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:

Post by Julien Cornebise » Thu Jul 15, 2004 9:35 am

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:

Post by Larry » Thu Jul 15, 2004 10:11 pm

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

Post by Ivor » Sun Jul 18, 2004 2:45 pm

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:

Post by Julien Cornebise » Tue Jul 20, 2004 11:48 pm

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

Post by Maniac » Thu Sep 16, 2004 5:45 pm

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

Post by kronenthaler » Thu Apr 07, 2005 11:35 pm

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
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Tue Apr 12, 2005 8:44 pm

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

L I M O N

Post Reply

Return to “Volume 100 (10000-10099)”