*n = 8*case listed has a worst case cost of 17 with the binary search method described. Given that you chose

**"4"**as your first guess, though, wouldn't you be able to get the worst case cost down to 16?

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

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.

For Problem 328, the *n = 8* case listed has a worst case cost of 17 with the binary search method described. Given that you chose **"4"** as your first guess, though, wouldn't you be able to get the worst case cost down to 16?

Yes. For n=8, with "4" as the first question, the worst-case has a cost of 16 (questions: "4", "5" and "7").

The "binary search" strategy (first question "4", second question "2" or "6" depending on the first answer etc) has a worst-case cost of 17 as described in**Problem 328** (View Problem).

Neither of those is as good as the optimal strategy (which has a worst-case cost = 12).

The "binary search" strategy (first question "4", second question "2" or "6" depending on the first answer etc) has a worst-case cost of 17 as described in

Neither of those is as good as the optimal strategy (which has a worst-case cost = 12).

If someone (maybe you ) will solve this. Can you confirm my results

Sum 1 to 200 C(n) = 86523

Sum 1 to 10000 C(n) = 461622753

Sum 1 to 200 C(n) = 86523

Sum 1 to 10000 C(n) = 461622753

I get 86342 for 200. It would take a long time to go up to 10000 with my current code. Need to figure out better way to do this.

puzzle is a euphemism for lack of clarity

I get the same values as sivakd for C(200) and C(10000) but apparently C(200000) i am getting with my approach is incorrect.

I also get the same numbers but am making some assumptions which I am struggling to test.

The result posted by sivakd for the sum 1 to 200, seems correct.

However, the result posted by Cifko for the sum 1 to 10000 looks too high.

However, the result posted by Cifko for the sum 1 to 10000 looks too high.

I got the same results as cifko - but they seem to be wrong

(my simple strategy has obviously chances for optimization.)

(my simple strategy has obviously chances for optimization.)

Come on guys.. while I don't mind people asking for hints (which test cases are, they make the solving process much simpler) for older problems, the problem has only been out for a couple of days.. can we at least give it a week or two so people who want to solve it themselves can have the satisfaction of knowing others have solved it by themself too?

Well said TripleM. No further intermediate results should be given (at this stage, anyway). Sorry, kingvash!

Let's not forget that the idea behind this forum is to help with*understanding* the problems (though I plead guilty to occasionally going beyond that).

Let's not forget that the idea behind this forum is to help with

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).

I have no solution and I thought the stored solution at euler must be wrong (or is the Ukrainien internet defect? ,-) ), but now the solutions drop in, i am convinced there is a correct solution.

Marco.

I have no solution and I thought the stored solution at euler must be wrong (or is the Ukrainien internet defect? ,-) ), but now the solutions drop in, i am convinced there is a correct solution.

Marco.

It seems like my code underestimates the real value... for C(100) I get 396 instead of 400, and the sum up to 100 is about 200 short...

My sum up to 25 is: 692, Could I get a confirmation please?

My sum up to 25 is: 692, Could I get a confirmation please?

It seems too me that people are asking for hidden numbers all the time.

If we would have introduced the rule:

You get the answer "too low", "too high", or 'spot on" if you pay in advance a donation in pounds sterling equal to the number you are asking for, Project Euler would have become very rich in just one weekend.

Just seriously now: it shouldn't be too difficult to make a bruteforcer without too many inwarranted assumptions that is able to verify questions like the one you are asking and also somewhat further up to the smaller examples given.

So let's stick at these examples.

If we would have introduced the rule:

You get the answer "too low", "too high", or 'spot on" if you pay in advance a donation in pounds sterling equal to the number you are asking for, Project Euler would have become very rich in just one weekend.

Just seriously now: it shouldn't be too difficult to make a bruteforcer without too many inwarranted assumptions that is able to verify questions like the one you are asking and also somewhat further up to the smaller examples given.

So let's stick at these examples.

I won't post any numbers, but want to know if the solutions so far are meeting the 1 minute rule. It took me 3 hrs (perl) for the 10,000 case and the answer is different from what's given so far. At the current rate it wouldn't make sense for me to go all the way to 200,000.

Last edited by sivakd on Tue Mar 15, 2011 3:38 am, edited 1 time in total.

puzzle is a euphemism for lack of clarity

Yes there are solutions that stick to the one minute rule.

You have it easy. Underestimating C(100) means that you only have to verify the particular guessing strategy that gives that number. Either one of the possibilities has a total score of more than 396, or not all 100 numbers can be distinguished from each other. Either way, it is a direct clue to a bug in your program.shachark wrote:It seems like my code underestimates the real value... for C(100) I get 396 instead of 400

If your program, like mine, had overestimated C(100) then verifying the guessing strategy could well give you nothing, apart from the fact that the optimal strategy has been overlooked.

Well, so far I have a program that's too slow to compute the 200000 case, but that does find the optimal solution for C(100) (and I get the same sum up to 100 as the problem statement)shachark wrote:It seems like my code underestimates the real value... for C(100) I get 396 instead of 400, and the sum up to 100 is about 200 short...

My sum up to 25 is: 692, Could I get a confirmation please?

I can confirm your sum up to 25, it is 692.

As for overestimating, I'm in the same fix as jaap for the time being, any faster solution I come up with does not find the optimal strategy and tends to overestimate the result.

Btw: C(10000) is bruteforceable in under 10 mins.

So just write a Brute-Force-Algorithm to verify the Solutions of the "real" Algorithm.

Another interesting Problem would be to find the Number with the most optimal solutions under a specified limit.

So just write a Brute-Force-Algorithm to verify the Solutions of the "real" Algorithm.

Another interesting Problem would be to find the Number with the most optimal solutions under a specified limit.

Some more optimizations and I can sum up 1 to 10000 in less than a second. But now the issue is with memory. This problem seems to be way more difficult than when I first read it.

puzzle is a euphemism for lack of clarity