251  Nondeterministic Trellis Automata
Moderator: Board moderators
251  Nondeterministic Trellis Automata
Hey,
Does anyone have an idea for this that is nonenumerative/exchaustive?
Thank a lot.
Does anyone have an idea for this that is nonenumerative/exchaustive?
Thank a lot.
I used exhaustive search and my timing was 0.00s so it should be good enough...
anyway, if I'm not wrong, this problem is NPcomplete and cannot be solved in polynomial time.. so exhaustive search is more or less the only way to go.
the difference between TLE and AC is that you have to order your recursion correctly and to add in correct pruning.
anyway, if I'm not wrong, this problem is NPcomplete and cannot be solved in polynomial time.. so exhaustive search is more or less the only way to go.
the difference between TLE and AC is that you have to order your recursion correctly and to add in correct pruning.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Could you junbin, give me more hints ?
I try to use map or vector to memorize states, which my program computs earlier, but I got TLE all the time
My algorithm use resursion to generate states.
Best regards
DM
I try to use map or vector to memorize states, which my program computs earlier, but I got TLE all the time
My algorithm use resursion to generate states.
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
i keep getting tle for this problem despite implementing all pruning methods i could think of. can someone tell me how to exactly order the states and do you keep changing it depending on the input?
my program runs in O(4^n) time.
please help...i am losing sleep coz of this ...
my program runs in O(4^n) time.
please help...i am losing sleep coz of this ...
if u can think of it .. u can do it in software.

 Learning poster
 Posts: 83
 Joined: Wed Feb 27, 2002 2:00 am
 Location: Taiwan
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Could somebody please explain to me why in the first example NTA, the string "abab" is rejected? What is wrong with this computation?
Since c is an accepting state, abab should be accepted. No?
Code: Select all
Row 4: abab
Row 3: aca
Row 2: ac
Row 1: c
If only I had as much free time as I did in college...
I solved this problem with Backtrack + pruning.
Here's a hint of pruning to avoid TLE:
You can calculate a set of pairs (like {ab, cd, ad}) from the transition table.
When you are givin a string and it includes a pair which is not in the set,
you could immediately say it will be "rejected".
[example] If the set is {ab, bc, cd, ad, db}.
abcd > might be accpeted
abdc > never accepted (bd is not in set )
I hope this helps.

Sory for my poor English.
Here's a hint of pruning to avoid TLE:
You can calculate a set of pairs (like {ab, cd, ad}) from the transition table.
When you are givin a string and it includes a pair which is not in the set,
you could immediately say it will be "rejected".
[example] If the set is {ab, bc, cd, ad, db}.
abcd > might be accpeted
abdc > never accepted (bd is not in set )
I hope this helps.

Sory for my poor English.