Problem 688

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
KING-OLE
Posts: 15
Joined: Mon Dec 22, 2014 9:33 pm

Problem 688

Post by KING-OLE »

I have problems understanding the exact question.

Do the piles need to have different counts of plates:

1) before the new plates are added,
2) added to each pile,
3) after new plates are added
4) all or some of the above - which? _____________

Thanks.
Image
mdean
Posts: 169
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 688

Post by mdean »

What "new plates"? You take n plates and divide them into k piles. For each calculation of f(n,k), the total number of plates is fixed.
Image
KING-OLE
Posts: 15
Joined: Mon Dec 22, 2014 9:33 pm

Re: Problem 688

Post by KING-OLE »

"We stack n plates into k non-empty piles where each pile is a different size."

So, the new plates are n, and the k piles are NOT empty, therefore old or existing.

EDIT: Or am I reading that wrong? - Does it simply mean that I have to place at least one plate on each pile, leaving none empty, and that the k piles are empty before you place the plates?
Image
DJohn
Posts: 63
Joined: Sat Oct 11, 2008 12:24 pm

Re: Problem 688

Post by DJohn »

You might be reading "We stack n plates into k non-empty piles" as "We stack n plates onto k non-empty piles", which (to me at least) has a quite different meaning. We start with nothing but n plates. Stacking takes place. Then we have k piles, none of which are empty. The question is concerned with this final state: a total of n plates in k piles (with no two piles having the same number of plates). How they got there doesn't matter.

It might be the "non-empty" that's tripping you up. This is describing the piles after the stacking, not before. It's not something you'd say in every-day speech, but in maths a pile could contain zero plates, and that case must be excluded for this problem.

It might be better worded "We divide n plates into k non-empty piles".
KING-OLE
Posts: 15
Joined: Mon Dec 22, 2014 9:33 pm

Re: Problem 688

Post by KING-OLE »

Thank you for clarifying DJohn.

The language had me misunderstanding the task. I would have preferred something like "Stack n plates in k piles. No pile must remain empty."

Anyway, I understand the question now, so I will now see if I can solve it. :-)
Image
vamsikal3
Posts: 113
Joined: Sat Oct 01, 2016 9:25 am

Re: Problem 688

Post by vamsikal3 »

Minor clarification:

The problem text reads: It is impossible to divide 10 into 5 non-empty piles and hence f(10,5)=0.

It is possible to divide 10 into 5 non-empty piles, 10 = 2 + 2 + 2 + 2 + 2. It is impossible to divide 10 into 5 non-empty piles with different number of plates.

Should we clarify this in the problem statement?
my friend key --> 990813_OZPwQtCjkD6KlvxirOoTSZxccMFsuw1L
Image
User avatar
RobertStanforth
Administrator
Posts: 1402
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 688

Post by RobertStanforth »

vamsikal3 wrote: Mon Nov 18, 2019 6:07 am The problem text reads: It is impossible to divide 10 into 5 non-empty piles and hence f(10,5)=0.
Thank you for pointing this out. The wording has now been amended.
TGiordi
Posts: 1
Joined: Sun Jan 05, 2020 2:01 pm

Re: Problem 688

Post by TGiordi »

Hello,

I'm able to compute the exact S(100) value with a simple algorithm and an optimized algorithm. My simple algorithm gives me the same result as the optimized one till 106 or 108. Anyway, the solution for 1016 is wrong. Could you provide S(106) or S(108) in order to be able to trouble shoot my simple & optimized algorithm as I assume there should be a special case that I've not taken into account and that is not visible in S(100).

Thanks
castrate
Posts: 17
Joined: Mon Aug 19, 2019 2:34 pm

Re: Problem 688

Post by castrate »

I came across almost the same problem as @TGiordi. I got the correct answer(12656) for S(100) and I was able to compute S(10^16) in reasonable time, but the answer was wrong. So can I PM someone in order to check my answers for higher results such as S(10^8)? Thanks :D
Post Reply