ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1455. Freedom of Speech

How to solve it? Need DP?
Posted by panyong0202 9 Aug 2007 10:30
Re: How to solve it? Need DP?
Posted by Chmel_Tolstiy 9 Aug 2007 12:37
There many ways:
1) hash
2) suffix array
3) suffix tree
4) suffix automation
Re: How to solve it? Need DP?
Posted by panyong0202 11 Aug 2007 08:50
Thank you, I've got AC
Re: How to solve it? Need DP?
Posted by svr 15 Oct 2007 19:57
10000 suffices,graph of they. Suffix s1 connected with
suffix s2 if exist word s, adjusting which to s1 we will have s2 as a rest. BFS in graph to find when rest will be equal empty:1) s=s1+s2; s=s3+s1+s4;s2=s1+s4.
Ac at last with above approach.
It imortant to right work with 20000.

Edited by author 22.11.2008 14:52
Re: How to solve it? Need DP?
Posted by Denis Koshman 20 Aug 2008 11:11
Create characters tree for all words (allowing direct per-character steps at O(1) and enumeration of all children also at O(1)). DP over IxJ, I - word number, J - suffix length. Cover these suffixes with other words till length delta become zero. I used Dijkstra for that because length can change arbitrarily. Start in words which contain some other word as a prefix.

Edited by author 20.08.2008 11:11
Re: How to solve it? Need DP?
Posted by Alex Tolstov 3 Jul 2009 14:13
I used DP on trie.