10506 - The Ouroboros problem

[_evilgeek]

There seem to be issues with the test data (or verifier) for this problem. I say this because I wrote my own verifier, and it returned "YES" for all valid input (besides the cases where n=1, where I verified the "0" output by my program by hand). Following is the verifier code (again, it doesn't work if n=1, and I know why):

[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int m, n;
int ntom;
char blah[200000];

int doit(int st) {
int i, j=0;
for (i = st; i < st+m; i++) {
j *= n;
j += blah-'0';
}
return j;
}

main() {
int seen[131072];
int i;
while(scanf("%i %i %s", &m, &n, blah) != EOF) {
ntom=1;
for (i = 0; i < m; i++) ntom *= n;
if (strlen(blah) != ntom) goto reject;
strncat(blah, blah, ntom);
memset(seen, 0, sizeof(seen));
for (i = 0; i < ntom; i++) {
seen[doit(i)]++;
}
for (i = 0; i < ntom; i++) {
if (seen != 1) goto reject;
}
printf("YES\n");
continue;
reject:
printf("NO %i %i\n", m, n);
}
}
[/c]

When run on every legal input, my program outputs something which this verifier says is a "YES" or a "NO m 1". The "NO m 1" cases are actually correct, since the solution outputs a lone "0."

If I've done something stupid, please let me know.

[Carlos]

Hi!
The test data was wrong, sorry. We've changed it and we're rejudging all submissions.

[abishek]

hi, i have just got the most expected answer TLE from the judge fot this question.
I had done the ouroborous snake problem within 8.00 secs in some other volume. thought i would use the same backtrack stratergy here, but it doesnot seem to work. I use the following idea:

first for each position, try 0--->n-1 and only if the ouroborous constructed so far is valid, i proceed to the next one. could some one help me on this. i use stl sets. is that the reason?

thanks
abi

[sidky]

I just solved it through backtracking, and my solution is not too intelligent. But, it managed to get accepted in 0.004 seconds. My approach is similar to yours.
I have never used Set class. So, i dont know whether it is because STL. But, TLE looks a little too much to me. Look at your prunning too.

[abishek]

that must be very nice
i have solved this problem now with the FKM algorithm.
really your backtrack must be very efficient as the FKM algorithm will give the answer bit by bit.
thanks for your reply
bye
abi

[Observer]

Hi. I've read something about FKM algorithm. However, I don't know how to use it to generate our desired sequence bit by bit, so... any hints?

(Btw, my backtracking solution gets Accepted in 0.008 s. Have some room of optimization still...)

[abishek]

i think you should try to read the new fasicles of Donald Knuth. One of them (Generating all n-tupules) contains the FKM algorithm in a beautiful manner.