## 251 - Nondeterministic Trellis Automata

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### 251 - Nondeterministic Trellis Automata

Hey,

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

Thank a lot.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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
Guru
Posts: 832
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
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)

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
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 ...
if u can think of it .. u can do it in software.

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
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?

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?
If only I had as much free time as I did in college...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You can't go from "aca" to "ac", since the transition table does _not_ allow reducing "ac" to "a".

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
could someone that got AC please explain how to avoid TLE properly?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Thanks, I got AC