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.
dbatche3
Posts: 4
Joined: Sat Apr 03, 2010 6:20 pm

Problem 328

Post by dbatche3 »

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?
Image

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 328

Post by harryh »

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

Cifko
Posts: 1
Joined: Wed Jan 12, 2011 9:13 am
Location: Bratislava

Re: Problem 328

Post by Cifko »

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
Image

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

Re: Problem 328

Post by sivakd »

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.
Image
puzzle is a euphemism for lack of clarity

mkch
Posts: 3
Joined: Sun Mar 13, 2011 5:30 am

Re: Problem 328

Post by mkch »

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.

ynoth
Posts: 1
Joined: Sun Mar 13, 2011 5:36 am

Re: Problem 328

Post by ynoth »

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

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 328

Post by harryh »

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.

mr66
Posts: 4
Joined: Sun Mar 13, 2011 11:32 pm

Re: Problem 328

Post by mr66 »

I got the same results as cifko - but they seem to be wrong
(my simple strategy has obviously chances for optimization.)

kingvash
Posts: 13
Joined: Sun Nov 22, 2009 2:57 am

Re: Problem 328

Post by kingvash »

maybe 456674529 for 10000?

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 328

Post by TripleM »

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?

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 328

Post by harryh »

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

carkiller
Posts: 5
Joined: Mon Jan 31, 2011 12:19 pm

Re: Problem 328

Post by carkiller »

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.

shachark
Posts: 4
Joined: Sat Mar 12, 2011 9:17 pm

Re: Problem 328

Post by shachark »

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?
Image

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 328

Post by hk »

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. :lol:

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

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

Re: Problem 328

Post by sivakd »

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.
Image
puzzle is a euphemism for lack of clarity

User avatar
hk
Administrator
Posts: 10889
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Problem 328

Post by hk »

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

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

Re: Problem 328

Post by jaap »

shachark wrote:It seems like my code underestimates the real value... for C(100) I get 396 instead of 400
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.

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.

entropy
Posts: 1
Joined: Mon Mar 14, 2011 10:59 pm

Re: Problem 328

Post by entropy »

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

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.

dnosrc
Posts: 8
Joined: Tue Jul 27, 2010 4:58 pm

Re: Problem 328

Post by dnosrc »

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.

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

Re: Problem 328

Post by sivakd »

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.
Image
puzzle is a euphemism for lack of clarity

Post Reply