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 1002. Phone Numbers

Do you know a faster algorithm?
Posted by Artur Mazgarov 25 Jan 2008 18:42
If I try to check every way of placing words, I get 'Time limit exceeded' on test 5, and if I just first sort the words by lengths, and then try to find the first way of placing words and give it as answer, I get 'Wrong answer' on test 3. Could you please help me?
Re: Do you know a faster algorithm?
Posted by Aram Shatakhtsyan 26 Jan 2008 13:34
Dynamic programming
Re: Do you know a faster algorithm?
Posted by omsu_lime 10 Apr 2008 10:55
Try to create determinated finite automaton in graph realization. Use binary search to find the words in dictionary.
Re: Do you know a faster algorithm?
Posted by CP GS 23 Sep 2008 00:58
The Aho-Corasick algorithm will do it with linear time.
Re: Do you know a faster algorithm?
Posted by Artur Mazgarov 5 Dec 2008 19:33
Thank you. I'll try :)
Re: Do you know a faster algorithm?
Posted by yzthz 15 Mar 2009 20:57
Unfortunately, I got TLE on the 8th input even if I implemented DP.

Oh I know the reason. When two or more strings map to one series of number, since any solutions are qualified, it is possible to choose only one. Also, a compartmentalization to which position(0-s.length()) the string can fit in is recommended.

Edited by author 16.03.2009 10:20
Re: Do you know a faster algorithm?
Posted by Prabhjot Singh 21 Sep 2009 12:51
can you please give me one test case where you sort the words by length and you get wrong answer? (i used similar technique and got wrong ans for test 3 as well)