Page 2 of 2

Posted: Mon Jul 16, 2007 5:08 am
by hank
Hello rio,

Thanks very much!
I tried something similar to the second idea you proposed and some prune.
My program took about 30 seconds for the testdata you provide above.
It is faster than before, but still slow, and it still got TLE in the onlinejudge.
Can we check whether the expression has solutions or not without calculate all the mappings ?
I also have interest in your first idea. Could you give me some information( or example) on your first idea?

Sorry for my poor English.
I've spent much time on this problem but TLE all the time. :(

Thanks a lot! :)

Posted: Mon Jul 16, 2007 10:13 pm
by rujialiu
hank wrote:Hello rio,

Thanks very much!
I tried something similar to the second idea you proposed and some prune.
My program took about 30 seconds for the testdata you provide above.
It is faster than before, but still slow, and it still got TLE in the onlinejudge.
Can we check whether the expression has solutions or not without calculate all the mappings ?
I also have interest in your first idea. Could you give me some information( or example) on your first idea?

Sorry for my poor English.
I've spent much time on this problem but TLE all the time. :(

Thanks a lot! :)
You don't have to know everything solution. For example, if every letter is already ambiguous, just exit with a "Oops". It's also possible apply this idea to only part of the search tree

Note: this idea is heavily influenced by other techniques, so spend some time to find a practical combination of techniques