Page 1 of 1
251 - Nondeterministic Trellis Automata
Posted: Wed Apr 07, 2004 7:18 pm
by yiuyuho
Hey,
Does anyone have an idea for this that is non-enumerative/exchaustive?
Thank a lot.
Posted: Fri Apr 09, 2004 12:27 pm
by junbin
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 NP-complete 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.
Posted: Mon Aug 16, 2004 10:28 am
by Dominik Michniewski
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
Posted: Sun Oct 17, 2004 12:17 pm
by jagadish
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 ...
Posted: Thu Aug 04, 2005 6:08 pm
by LittleJohn
My method is based on exhasted search (level by level) with some cuts.
But not surprisedly, it got TLE.
the difference between TLE and AC is that you have to order your recursion correctly and to add in correct pruning.
I think it's the key of this problem.
Any more hint is appreciated. : )
Posted: Sat Aug 06, 2005 1:37 am
by Abednego
Could somebody please explain to me why in the first example NTA, the string "abab" is rejected? What is wrong with this computation?
Code: Select all
Row 4: abab
Row 3: aca
Row 2: ac
Row 1: c
Since c is an accepting state, abab should be accepted. No?
Posted: Sat Aug 06, 2005 8:18 am
by mf
You can't go from "aca" to "ac", since the transition table does _not_ allow reducing "ac" to "a".
Posted: Sun Mar 26, 2006 4:24 am
by sclo
could someone that got AC please explain how to avoid TLE properly?
Posted: Tue Nov 28, 2006 3:25 pm
by rio
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.
Posted: Thu Feb 08, 2007 10:36 am
by sclo
Thanks, I got AC