How to solve this problem(1158)? It's too hard....
I have been working on it for a week....
DP of extreme difficulty. Can not be easily explained (-)
Re: DP of extreme difficulty. Can not be easily explained (-)
Why extreme difficulty? My DP is about 30 lines. Idea is very simple. But it's hard to discover as well :)
For instance, Ural-1342 is 8-lines DP... (+)
I mean no true DP solution is really large, but this very DP is rather difficult to find and understand.
Re: DP of extreme difficulty. Can not be easily explained (-)
would you please tell me your method? I think only a big-number code will use more than 30 lines...
Re: DP of extreme difficulty. Can not be easily explained (-)
I think Aho-Korasick+DP
This seems pretty interesting.. Could you give me a link where I can read more about this algo?
I solved it with a dfa + dp, but my source is very big (180 lines).. How to do it in 30 lines?
Re: I solved it with a dfa + dp, but my source is very big (180 lines).. How to do it in 30 lines?
ALGO IS HERE:
1. Remove all words which contain some other word as a substring. They do not affect anything, but make further things more difficult.
2. Build characters tree from forbidden words. E.g. for set "aabc, abd, bcd" it will be like that:
root(a(a(b(c)),b(d)),b(c(d)))
positions in this tree will represent history (recent placed letters) and its size will be <= 100 (total amount of letters in all forbidden words)
A path from root to node is safe if it does not end in a leaf (otherwise you're in jail for 10 years). Any sub-paths of a safe path are also safe because we removed all words which could lead to such paths. So, we have a good test for path safety - it shouldn't be a leaf, and that's enough.
While we place letters, we are allowed to make only safe steps - we can't step into a leaf.
If we attempt to perform a step outside of the tree, we should apply 1st postfix of history to that tree to find where will we get after forgetting that least recent placed letter. For example, if the string 'aabce' falls out from the tree after 'aab' (i.e. there is no forbidden word starting with 'aabc'), then we will search for 'abce' (1st postfix of 'aabce') in the same manner, recursively. All this information can be precalculated (which state leads where after adding some particular letter). It's like prebuilding automaton for multi-substring search and then calculate number of programs which do not lead to terminal states.
This gave me AC in 0.031 sec and final understanding of KMP which I used blindly before :)
Edited by author 05.08.2008 04:24
Re: I solved it with a dfa + dp, but my source is very big (180 lines).. How to do it in 30 lines?
The limits are not very strict. I did not perform precalculation and did not build automata.
