Problem 351

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.
Post Reply
elr
Posts: 69
Joined: Thu Apr 09, 2009 8:47 am

Problem 351

Post by elr » Sun Sep 18, 2011 6:45 pm

how exactly "hidden from the center" is defined ?
why the points that are circled in red in this picture:
Image
are not hidden from the center ?
Image

User avatar
jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 351

Post by jaap » Sun Sep 18, 2011 7:01 pm

elr wrote:how exactly "hidden from the center" is defined ?
why the points that are circled in red in this picture:
Image
are not hidden from the center ?
Because there is a straight line from the centre to any of those points which does not hit any of the other points of the grid.
Attachments
p351hexorchard.png
p351hexorchard.png (6.54 KiB) Viewed 7786 times

User avatar
Marcus_Andrews
Administrator
Posts: 1455
Joined: Wed Nov 09, 2011 5:23 pm

Re: Problem 351

Post by Marcus_Andrews » Fri Feb 14, 2014 2:53 pm

There is a new PDF for this problem, which should come in handy for certain types of problems that solvers may be having difficulty with lately.
Image

pimspelier
Posts: 41
Joined: Tue Jan 21, 2014 2:06 pm
Location: The Netherlands

Re: Problem 351

Post by pimspelier » Sat Mar 01, 2014 7:03 pm

Argh... I've spent hours working on this problem, and finally I've got a good, fast algorithm: it gives the answer for 100000 in 0.13 seconds (while doing nothing takes 0.08 seconds).
But when I try 1000000, the program completely stops working and it gives an error: ProjectEuler.exe (the name) has stopped working. It returns -1073741571 (0xC00000FD). I've tried using unsigned long long ints instead of long long ints, but to no prevail. Does anyone know what the problem might be?

EDIT: Thanks mdean and Marcus, solved :D.
Last edited by pimspelier on Sun Mar 02, 2014 11:26 am, edited 1 time in total.
Image

mdean
Posts: 143
Joined: Tue Aug 02, 2011 1:05 am

Re: Problem 351

Post by mdean » Sat Mar 01, 2014 7:30 pm

pimspelier wrote:Argh... I've spent hours working on this problem, and finally I've got a good, fast algorithm: it gives the answer for 100000 in 0.13 seconds (while doing nothing takes 0.08 seconds).
But when I try 1000000, the program completely stops working and it gives an error: ProjectEuler.exe (the name) has stopped working. It returns -1073741571 (0xC00000FD). I've tried using unsigned long long ints instead of long long ints, but to no prevail. Does anyone know what the problem might be?
Impossible to guess without seeing the code (don't post that here, I have solved the problem so you can pm me if it's C/C++ and you want me to take a peek) . First figure out where the program is crashing, then figure out why the program is crashing.
Image

User avatar
Marcus_Andrews
Administrator
Posts: 1455
Joined: Wed Nov 09, 2011 5:23 pm

Re: Problem 351

Post by Marcus_Andrews » Sun Mar 02, 2014 1:19 am

Sounds like it may be a stack overflow, based on the error code (in this case, possibly a recursive algorithm that is trying to nest too deeply).
Image

dchaudh
Posts: 4
Joined: Mon Dec 15, 2014 7:57 am

Re: Problem 351

Post by dchaudh » Fri Dec 19, 2014 5:23 am

Hmm, I was confident I had the right answer, based on (i) a proof and (ii) the fact that my answers for small values of n matched those in the problem text...but the little man gave me a red cross!

Any chance someone could let me know if I have the correct values for H(million) and H(ten million)?
[(5,30),(10,138),(1000,1177848),(1000000,1176221685648),(10000000,117621891442704)]

Thanks!

dchaudh
Posts: 4
Joined: Mon Dec 15, 2014 7:57 am

Re: Problem 351

Post by dchaudh » Fri Dec 19, 2014 5:53 am

Silly me, I was using Float when I should have been using Double. Sometimes, it's easy to get lulled into complacency when using a language with native big integers...

DeKlod
Posts: 14
Joined: Tue Aug 21, 2018 7:55 am

Re: Problem 351

Post by DeKlod » Fri Nov 16, 2018 7:54 am

Hello all,
Maybe someone could enlighten me on this one: the PDF solution sheet for this problem describes several possible algorithms of varying efficiency, yet they mainly seem to rely on an array containing all the required integer values, i.e. 10^8 numbers in this case.
On my system and using C/C++, defining an array this size immediately causes a 'Segmentation fault' - and the number spaces required only get larger on some of the more difficult problems on PE.
Am I missing something?
Thanks in advance for any input!
Claude

User avatar
jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 351

Post by jaap » Fri Nov 16, 2018 10:31 am

DeKlod wrote:
Fri Nov 16, 2018 7:54 am
On my system and using C/C++, defining an array this size immediately causes a 'Segmentation fault' - and the number spaces required only get larger on some of the more difficult problems on PE.
Am I missing something?
Do you know the difference between the stack and heap memory? Do you know how to use standard library containers such as std::vector?
Last edited by jaap on Fri Nov 16, 2018 1:37 pm, edited 1 time in total.

DeKlod
Posts: 14
Joined: Tue Aug 21, 2018 7:55 am

Re: Problem 351

Post by DeKlod » Fri Nov 16, 2018 12:00 pm

Cheers Jaap,
I'm afraid I'll have to confess my ignorance on the first question (I'll google that though). I do use vectors, yes, but I would have thought it would pose problems of efficiency too as it will take up a lot of memory.
I'll try that approach over the weekend though and see what happens :-)
Claude

User avatar
jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 351

Post by jaap » Fri Nov 16, 2018 2:09 pm

DeKlod wrote:
Fri Nov 16, 2018 12:00 pm
Cheers Jaap,
I'm afraid I'll have to confess my ignorance on the first question (I'll google that though). I do use vectors, yes, but I would have thought it would pose problems of efficiency too as it will take up a lot of memory.
I'll try that approach over the weekend though and see what happens :-)
Claude
I hope that is where your trouble lies. Basically, if you need to use lots of memory (more than the stack provides), you have to allocate it yourself from the heap. You can do it the old-fashioned C way with malloc/free, or the slightly more C++ way with new[]/delete[], or just use containers like std::vector. Use the smallest integer type you need. For example, with 32-bit integers allocating 10^8 of them takes 4*10^8 bytes, or about 400 Mb. This should be fine on any modern PC.

DeKlod
Posts: 14
Joined: Tue Aug 21, 2018 7:55 am

Re: Problem 351

Post by DeKlod » Fri Nov 16, 2018 3:02 pm

Thanks for that, jaap!
Just one last question, if I may: is there any other obvious technique if you really need large quantities of data? Imagine a sieve for primes up to - say - 10^12. Vectors of type bool seem to be fine up to about 10^10 but not further. So I guess that's where you need to change tack and do something completely different, right?
Not asking for hints, as such, just wanting to avoid long barking sessions up the wrong tree... ;-)
Cheers,
Claude

User avatar
jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 351

Post by jaap » Fri Nov 16, 2018 3:47 pm

If you ever need more than, say, 600MB of data, then you are probably doing it wrong. You are either using the wrong solving method, or maybe you just don't need to have all of that data in memory at the same time.

User avatar
RishadanPort
Posts: 41
Joined: Mon Jun 10, 2013 6:31 am

Problem 351 Visibility of extremely far away orchard

Post by RishadanPort » Mon Jul 15, 2019 11:19 pm

Let the middle orchard represent (0, 0).

if I have say an orchard that is on the X-Axis shifted (100 000 000 - 1) away but shifted up or below by 1, -- do I assume I can see this orchard even tho the line is extremely close to just horizontal line?

I am guessing all orchards are points with no width.
Image

Rishada is the gateway to free trade—but the key will cost you.

User avatar
RobertStanforth
Administrator
Posts: 985
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 351 Visibility of extremely far away orchard

Post by RobertStanforth » Tue Jul 16, 2019 6:30 am

RishadanPort wrote:
Mon Jul 15, 2019 11:19 pm
Let the middle orchard represent (0, 0).

if I have say an orchard that is on the X-Axis shifted (100 000 000 - 1) away but shifted up or below by 1, -- do I assume I can see this orchard even tho the line is extremely close to just horizontal line?

I am guessing all orchards are points with no width.
I have moved your post to the existing topic for this problem.
You are correct: we are considering points with no width.

Post Reply