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
I had all kinds of precision problems and resolved all of them I think. To rule out the possibility of more precision problems, is it OK if I ask that the expected values are increasing (or remain same) only from 0.04?
Edit: Nevermind. It looks like I had some bug. I still haven't solved it, but getting closer. The program is just too slow though.
Edit 2: I am done. I accidentally overwrote my new code with the old code and so had to redo some of the stuff. That got rid of some bugs without knowing . Very slow code but as usual there are some better ways to solve that I can learn in the private forums.
I just want to throw this hint out there. It's a probability thing that I didn't know (and still don't really have intuition for) that for the longest time (40-some hours) prevented me from solving this one. If you test sheep A ... Z and you get a positive test. Then you test A ... G and they test positive; all-of-a-sudden you know *NOTHING* about H ... Z, even thought you previously believed that they belonged to a group that tested positive. It doesn't sit well with me, but a half-assed prove with Bayes' Theorem says that's the truth. Go figure. Thanks quilan for setting me on the right path.
"Nothing in this world that's worth having comes easy"
Having a rough time with this one. I fully understand the kind of problem this is and the type of probabilities involved (including Bayesian), but I just can't... translate it into something I can calculate.
It has similar elements to the N-dice stopping problem where my goal is to maximize my outcome. If I have one die, my E(X) is 3.5. If I have two dice (where I can either keep what I get first roll or discard it and keep the second), E(X) becomes (1/2)*3.5+(1/2)*((4+5+6)/3) = 4.25, and if we're talking three dice, then it's (4/6)*4.25 + (2/6)*((5+6)/2) = 4.666, and so forth.
Here, in this problem, the idea is to minimize expected number of tests based on the number of sheep we're looking at as well as the rate of healthiness. It's clearly recursive, much like the N-dice problem. I just don't know how to actually set this thing up in order to begin recursing. Minimizing the expected number of tests is ultimately minimizing the expected number of tests for all sub-segments of a given segment, where expected number of tests is based on probability of a sheep being sick and how many tests that brings plus the probability of those sheep being fine and only needing to waste 1 test, but... translating it into math is tough and I have no idea how to go about it.
I guess my issue with this problem is the usefulness of the restriction, which is perhaps a silly gripe to have. Why would you want to have the restriction that every sheep be tested all the way through before moving on? Are we ignoring more intelligent solutions to simply hammer out a more complicated and decidedly less efficient code, for the sake of understanding the problem?
Regardless of probability of disease, it would be sufficient to run 14 tests to tell exactly which of the 10,000 sheep are infected. And only 20 tests to tell which of a million sheep are infected. Unless my grasp on the problem is weaker than I thought and the answer is lower than that. More of a thought-response than a problem-related response.
dwanderson wrote:Regardless of probability of disease, it would be sufficient to run 14 tests to tell exactly which of the 10,000 sheep are infected.
You must have misunderstood the problem, since if the probability is 0.5 you're going to need a lot more than 14 tests (regardless of whether that restriction is applied).
dwanderson wrote:I guess my issue with this problem is the usefulness of the restriction, which is perhaps a silly gripe to have. Why would you want to have the restriction that every sheep be tested all the way through before moving on? Are we ignoring more intelligent solutions to simply hammer out a more complicated and decidedly less efficient code, for the sake of understanding the problem?
Resolves a particular issue.
Last edited by Marcus_Andrews on Sat Nov 12, 2011 4:07 pm, edited 2 times in total.
dwanderson wrote:I guess my issue with this problem is the usefulness of the restriction
The restriction was not in the original text of the problem; it was added to correct a problem-with-the-problem. There are some more details in the solution thread.
I believe I have found a pattern which is better than the optimal pattern described on the problem page. I've checked and rechecked this fifteen ways to Sunday, and I am still convinced that my computations are correct. I've been employed as a software developer for the past 17 years, so while I'm pretty experienced and have done harder work than this problem, I know that it's quite possible there is a flaw in my logic.
In particular, I achieve 3.732977 for T(25, 0.02) rather than 4.155452 and I achieve 11.936653 for T(25, 0.1) rather than 12.702124.
I do not wish to publish my algorithm here, as per the blinking reminder at the top of this forum. What is the proper way to discuss the variation between the solution I've derived and the solution which produced the optimum strategy?
It is known that you can achieve more optimal solutions than the ones mentioned if you violate this constraint:
To simplify the very wide range of possibilities, there is one restriction we place when devising the most cost-efficient testing scheme: whenever we start with a mixed sample, all the sheep contributing to that sample must be fully screened (i.e. a verdict of infected / virus-free must be reached for all of them) before we start examining any other animals.
.
War ruins the life and health of untold numbers of innocent children.
So to be clear, this restriction says if we separate 6 sheep from 25, and these test positive, and subsequently test 3 of those sheep which show up positive, we cannot release the remaining 3 sheep into the "unknown" pool at large. Once the six sheep are separated, they are for all intents and purposes a separate group from the 19 which were not separated originally.
Please confirm! I believe I misunderstood that requirement when I first read it.
So to be clear, this restriction says if we separate 6 sheep from 25, and these test positive, and subsequently test 3 of those sheep which show up positive, we cannot release the remaining 3 sheep into the "unknown" pool at large. Once the six sheep are separated, they are for all intents and purposes a separate group from the 19 which were not separated originally.
Please confirm! I believe I misunderstood that requirement when I first read it.
Right -- once you separate 6 sheep from 25, you have to determine whether or not those specific 6 are infected/not infected before moving onto the next 19.
i've written an algorithm that generates a test plan for problem 352. however, the numbers are slightly below the ones given as example, and i can't figure out why.
can someone give me the correct values for
T(1,0.02), T(2,0.02),T(3,0.02),T(4,0.02),T(4,0.02)?
i am getting 4.12 for T(25,0.02) but there are so many steps in between ;(
what's especially confusing is that my program prints out all the numbers and plans in between, and i don't see a problem there.
what is the place i need to go to discuss the problem/solution before i found the correct answer?
i am stuck very close to the desired number but can't figure out what's wrong.
. Very slow code but as usual there are some better ways to solve that I can learn in the private forums.
