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

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

251 - Nondeterministic Trellis Automata

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

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by 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
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

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

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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?
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:

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

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

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

Thanks, I got AC

Post Reply

Return to “Volume 2 (200-299)”