Discussion @ 1002. Phone Numbers @ Timus Online Judge

I was trying to it in an clever way

Posted by Mahilewets 6 Jul 2017 09:43

I was trying to write TRIE for mnemonic words and DFS that tree with phone number.
And I have failed.
After that, I wrote just 2-D dimensional dynamic programming solution. DP[i] [j] is minimal number of words to memorize substring [i;j]. And I got success. Used Python. Just input, not stdin from sys.

Re: I was trying to it in an clever way

Posted by Grandmaster 8 Nov 2017 04:09

i think you only need 1 array instead of dp[i,j]

Re: I was trying to it in an clever way

Posted by Mahilewets Nikita 8 Nov 2017 22:28

So probably there is jury solution available on the internet

Re: I was trying to it in an clever way

Posted by Mahilewets Nikita 8 Nov 2017 22:32

So I have examined jury solution
Looks too simple
Can't believe it is able to solve the problem

Re: I was trying to it in an clever way

Posted by Grandmaster 11 Nov 2017 05:21

where do you find the jury solution?

Re: I was trying to it in an clever way

Posted by Mahilewets Nikita 11 Nov 2017 22:14

https://www.fi.muni.cz/ceoi1999/

Discussion of Problem 1002. Phone Numbers