## 10447 - Sum-up the Primes (II)

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

### 10447 - Sum-up 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???

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

### Re: 10447: sum up the primes (II)

Okay, I optimized it a little, and
now I get wrong anwser.
Help!!!!!!!

ChristopherH
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.

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada
Okay, I'm AC now and ready to stop hyperventilating.

Neither the cheap trick nor the underspecified case seem to be used in the judging data; I had a legitimate error.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
Tell me what was your bug.
Maybe I've got the same bug?

ChristopherH
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 special-case '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!)

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
My program works perfectly for every kind of data that I can think of. This is really annoying!

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada
Check your upper bounds -- are your arrays sized correctly (ie for a[800] to be valid a must be defined a[801]).

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
My arrays are big enough.
I don't make *such* mistakes.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm

### Re: 10447: sum up the primes (II)

makbet wrote:Okay, I optimized it a little, and
now I get wrong anwser.
Help!!!!!!!
Please give me the optimization.
My complexity:
Memory: 62*800*12*2
Time: 62*800*12*2*4 //maximum frequency 4.
Mak
Help me PLZ!!

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10447 - Sum-up 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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman