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.
10506 - The Ouroboros problem
Moderator: Board moderators
-
- System administrator
- Posts: 1286
- Joined: Sat Oct 13, 2001 2:00 am
- Location: Valladolid, Spain
- Contact:
Nothing stupid - bad test data
Hi!
The test data was wrong, sorry. We've changed it and we're rejudging all submissions.
The test data was wrong, sorry. We've changed it and we're rejudging all submissions.
10506 TLE ouroborous
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
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
-
- New poster
- Posts: 50
- Joined: Wed Nov 06, 2002 1:37 pm
- Location: Planet Earth, Universe
- Contact:
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.
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.
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...)
(Btw, my backtracking solution gets Accepted in 0.008 s. Have some room of optimization still...)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org