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

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

10447 - Sum-up the Primes (II)

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
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Re: 10447: sum up the primes (II)

Post by makbet » Mon Feb 17, 2003 10:04 pm

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

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
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post by ChristopherH » Mon Feb 24, 2003 2:57 am

Okay, I'm AC now and ready to stop hyperventilating. :roll:

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

Post by makbet » Mon Feb 24, 2003 8:42 pm

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

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
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

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
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

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
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

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

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
Location: bangladesh

Re: 10447: sum up the primes (II)

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.
Mak
Help me PLZ!!

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

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

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

Post Reply

Return to “Volume 104 (10400-10499)”