10447  Sumup the Primes (II)
Moderator: Board moderators
10447  Sumup the Primes (II)
Can anyone who solved this problem give me a hint on how to not get TLE? I do it dynamically by filling a table 800x61x12 which tells me how many times a prime has been used to make a sum of t primes. I use recursion to come up with the lexicographically least solution first. Is there a faster way???
Re: 10447: sum up the primes (II)
Okay, I optimized it a little, and
now I get wrong anwser.
Help!!!!!!!
now I get wrong anwser.
Help!!!!!!!

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada
I'm in exactly the same boat. It was annoying to optimize (time bound too tight, still no O flag), and now I'm down to tedious iteration to find out the judge's intention for the unspecified corner cases.
I've found one cheap trick in the specification, but at least it is clearly defined.
However, it's unclear to me what to do for the case N = 0, t = 0. (Note that the problem does not set a lower bound for t. One would hope that 'several' implies a positive number, but hopes are often in vain.) I've tried outputting a blank line, "No solution.", or no line at all (notice the curious language about "a maximum of two lines" being output per query).
I'm also going out on a limb and assuming there's no (divinely inspired?) way to solve this problem for negative t.
If an AC could clarify these issues, it would be most helpful.
I've found one cheap trick in the specification, but at least it is clearly defined.
However, it's unclear to me what to do for the case N = 0, t = 0. (Note that the problem does not set a lower bound for t. One would hope that 'several' implies a positive number, but hopes are often in vain.) I've tried outputting a blank line, "No solution.", or no line at all (notice the curious language about "a maximum of two lines" being output per query).
I'm also going out on a limb and assuming there's no (divinely inspired?) way to solve this problem for negative t.
If an AC could clarify these issues, it would be most helpful.

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada
Check your boundary cases, with low N and low t. There are so many little mistakes to make, so make sure you handle all combinations of N and t in {0,1,2} correctly. If you have specialcase '2'handling code, make sure it doesn't break the logic for N, t. If you do that, you'll catch mistakes similar to the one I had.
Good luck! At least you've got it under 10 s, that's the majority of the battle. (although it would have been nice to know about the WA before optimizing the heck out of it!)
Good luck! At least you've got it under 10 s, that's the majority of the battle. (although it would have been nice to know about the WA before optimizing the heck out of it!)

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada

 Learning poster
 Posts: 72
 Joined: Tue May 30, 2006 5:57 pm
 Location: bangladesh
Re: 10447: sum up the primes (II)
Please give me the optimization.makbet wrote:Okay, I optimized it a little, and
now I get wrong anwser.
Help!!!!!!!
My complexity:
Memory: 62*800*12*2
Time: 62*800*12*2*4 //maximum frequency 4.
Mak
Help me PLZ!!
Help me PLZ!!
Re: 10447  Sumup the Primes (II)
Solved with dp. My previous dp approaches gave me TLE.
Memory : 244*800*12, where 244 = 61 * 4 (4 is maximum frequency).
Time___: 244*800*12, for each block of input.
Memory : 244*800*12, where 244 = 61 * 4 (4 is maximum frequency).
Time___: 244*800*12, for each block of input.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman