251 - Nondeterministic Trellis Automata

yiuyuho · Post by **yiuyuho** » Wed Apr 07, 2004 7:18 pm

Hey,

Does anyone have an idea for this that is non-enumerative/exchaustive?

Thank a lot.

junbin · Post by **junbin** » Fri Apr 09, 2004 12:27 pm

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.

Dominik Michniewski · Mon Aug 16, 2004 10:28 am

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

jagadish · Post by **jagadish** » Sun Oct 17, 2004 12:17 pm

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 ...

LittleJohn · Post by **LittleJohn** » Thu Aug 04, 2005 6:08 pm

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. : )

Abednego · Post by **Abednego** » Sat Aug 06, 2005 1:37 am

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?

mf · Post by mf » Sat Aug 06, 2005 8:18 am

You can't go from "aca" to "ac", since the transition table does _not_ allow reducing "ac" to "a".

sclo · Post by **sclo** » Sun Mar 26, 2006 4:24 am

could someone that got AC please explain how to avoid TLE properly?

rio · Post by **rio** » Tue Nov 28, 2006 3:25 pm

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.

sclo · Post by **sclo** » Thu Feb 08, 2007 10:36 am

Thanks, I got AC