Problem 328

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 328

Post by harryh »

@sivakd : But, as I can see, now you've managed to solve it (and make the fastest-20 list too !). Well done :D

A couple of days ago, you asked "if the solutions so far are meeting the 1 minute rule".
How do you feel now that your own solution is "under 2 sec" ? :)

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 328

Post by sivakd »

Thanks harryh. It was a long journey of optimizations. I wasn't expecting it to be that fast, was almost ready to submit it even if the solution took a few minutes.
Image
puzzle is a euphemism for lack of clarity

sarang
Posts: 1
Joined: Fri Mar 18, 2011 6:04 am

Re: Problem 328

Post by sarang »

shachark wrote:It seems like my code underestimates the real value... for C(100) I get 396 instead of 400
I think I was making a similar error. What helped me was walking through my algorithm while trying to guess the number 68.

sarang

User avatar
Richard61
Posts: 3
Joined: Sat Apr 30, 2011 7:59 am
Location: Queensland Australia

Re: Problem 328

Post by Richard61 »

carkiller wrote:I also think Sivakd helped a lot, and with his 200-solution one can find the mistake in the simple model (which fits the 100).
Yes sivakd's post for n = 1 to 200 did help me considerably: it changed my focus. Thank you!
That post made me rethink my whole approach and now I have a solution for n = 1 to 200,000 that does the entire calculation in under 1ms. I feel very good. :D

fibberts
Posts: 1
Joined: Mon May 16, 2011 5:55 am

Re: Problem 328

Post by fibberts »

This might be the wrong place to put this or just an inappropriate question but....
Who's the author of this problem?

I've seen references to the authors as though who authored what was common knowledge, but I don't know where they're getting this information. (Has it been hidden to protect the authors from answers-related harassment?)

I'm asking because I really like this problem and I'd like to know what kind of background it came from. Specifically, I'd like to know what work has been done on this and other problems like it. I'm amazed how much more chaotic a simple binary search becomes when a cost function is assigned to each query. Everyone I've described this problem to (other CS grad students) are equally dumbfounded.

sivakd
Posts: 217
Joined: Fri Jul 17, 2009 9:37 am
Location: California, USA
Contact:

Re: Problem 328

Post by sivakd »

fibberts wrote:This might be the wrong place to put this or just an inappropriate question but....
Who's the author of this problem?
Once you solve the problem, you can see in the private forum who the author of this problem is.
Image
puzzle is a euphemism for lack of clarity

golfguy37
Posts: 4
Joined: Tue Jul 23, 2013 11:45 pm

Re: Problem 328

Post by golfguy37 »

Can someone tell me if the answer will fit into a signed 32 bit int? My current code uses a good amount of memory so I'm looking for ways to reduce the memory footprint.
Image

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 5:40 pm
Location: Montréal, Canada

Re: Problem 328

Post by mpiotte »

golfguy37 wrote:Can someone tell me if the answer will fit into a signed 32 bit int? My current code uses a good amount of memory so I'm looking for ways to reduce the memory footprint.
It does not. It should be fairly easy to guess, given that typically C(n) > n (except for a few small values of 'n').
Image

Post Reply