Discussion @ 1044. Lucky Tickets. Easy! @ Timus Online Judge

input = 8, brute force time out ?

Posted by Dr Zhihua Lai 13 Sep 2010 01:31

I am using a brute force, but it gives me time limit exceed on case 4, which is n = 8.

can anyone tell me how to speed up this, thanks!

Re: input = 8, brute force time out ?

Posted by Dr Zhihua Lai 13 Sep 2010 01:51

hehe,, found a good solution to it...
problem solved!

Re: input = 8, brute force time out ?

Posted by Kernel Pwnic 11 Dec 2011 16:21

So Am I - how did you improve the performance ?

Re: input = 8, brute force time out ?

Posted by Bahador Biglari 16 Dec 2011 04:31

How did you speed it up?

Re: input = 8, brute force time out ?

Posted by DR. Zhihua Lai 16 Dec 2011 18:34

1.. try brute force to get the total number of sums of digits within n/2
2.. try DP, I think it will be similar to problem 1036

Edited by author 16.12.2011 18:52

Discussion of Problem 1044. Lucky Tickets. Easy!