10447 - Sum-up the Primes (II)

makbet · Post by **makbet** » Sun Feb 16, 2003 10:33 pm

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 · Post by **makbet** » Mon Feb 17, 2003 10:04 pm

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

ChristopherH · Post by **ChristopherH** » Mon Feb 24, 2003 2:39 am

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 · Post by **ChristopherH** » Mon Feb 24, 2003 2:57 am

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 · Post by **makbet** » Mon Feb 24, 2003 8:42 pm

Tell me what was your bug.
Maybe I've got the same bug?

ChristopherH · Post by **ChristopherH** » Mon Feb 24, 2003 11:39 pm

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 · Post by **makbet** » Thu Feb 27, 2003 1:18 pm

My program works perfectly for every kind of data that I can think of. This is really annoying!

ChristopherH · Post by **ChristopherH** » Thu Feb 27, 2003 7:48 pm

Check your upper bounds -- are your arrays sized correctly (ie for a[800] to be valid a must be defined a[801]).

makbet · Post by **makbet** » Thu Feb 27, 2003 9:20 pm

My arrays are big enough.
I don't make *such* mistakes.

mak(cse_DU) · Post by **mak(cse_DU)** » Sat Apr 24, 2010 6:42 pm

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.

lighted · Post by **lighted** » Wed Jun 28, 2017 4:23 pm

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.

OJ Board

10447 - Sum-up the Primes (II)

10447 - Sum-up the Primes (II)

Re: 10447: sum up the primes (II)

Re: 10447: sum up the primes (II)

Re: 10447 - Sum-up the Primes (II)