Mabinogon Sheep presented by Kevin

Thank you Rodion! While I came up with the problem and approach for the solution method, credit to Rodion for figuring out the blazingly-fast efficiency allowing for such large testcases! The first time I ran his updated checker code I thought my computer was going to get a speeding ticket :D

One very small typo - the counsins' names are supposed to be Marc and Haf (pronounced "have"), which is a female given name translating to summer :)

So far, I have no clue how this works - I can't solve the simple 2/2 example. I am now waiting for somebody to solve it to demonstrate that there is indeed an approach ...

Whew! That was a hard one!

Working out the correct strategy was the easy bit. I was then faced with what seemed like the need to solve a large number of linear equations. The large number of equations suggested that the solution would take far too long and would be subject to potential precision problems. Using fractions to avoid the precision problems was not an option because the fractions would quickly become unwieldy. I spent half a day thinking about this problem and finally came up with a method that needed no solutions of sets of equations; just multiplications of probabilities. And it is fast, even in normal python.

I was initially confused when developing the strategy by trying to find out how we can get the value of 2.75 for (2,2). A bit of work with pencil and paper soon showed that such a high value is impossible, whatever strategy is used. I have calculated the answer manually as 2.29166666667. This needs to be changed in the problem description because working out how to get the result for (2,2) is the most likely starting point for anyone trying to solve the problem. I agree with all of the other example answers apart from the last one, which seems to have suffered from a precision error. I think that the answer to (15,100) is 22.6717837561. I was not expecting my solution to pass the checker, assuming that there were precision issues for large sheep numbers. However, my solution did pass, for sheep numbers in excess of 400, so it seems that the checker does not suffer from any precision issues.

This was a good problem but it requires a great deal of careful thought to come up with a solution.

Now I am even more confused for the 2/2 example:

• Moxieman says 2.75.
• CSFPython says 2.29166666667.
• I think I can get to 2.4.

Mathias,

I have proved that you cannot reach 2.75. However, it may be possible that (2,2) is a special case, for such small numbers of sheep. If you have demonstrated that 2.4 is possible, given that the sheep must split into either (3,1) or (1,3) before you can apply any strategy, then you must have found a special case. I developed my strategy for arbitrary numbers of black and white sheep. It clearly agrees with the one used by the checker (except perhaps for (2,2)). Perhaps you should consider numbers of sheep larger than (2,2). My strategy certainly agrees with each of the other examples (except for some precision on the last one).

For (3, 1), we can send the one black sheep down the river and thus the expected value is 3.0. This, I believe, leads to 0.0 / 1.8 / 2.4 for (0, 4) / (1, 3) / (2, 2).

I want to get the very first example right.

(2,2) splits into (3,1) and (1,3) with equal probability of 0.5. If you are rejecting the single black sheep from (3,1) in order to claim 3 white sheep, then this contributes 0.5 x 3 = 1.5 to the expectation value. You now need to consider what you do with the (1,3). If you reject the 3 black sheep and claim the one white sheep then you have a contribution of 0.5 x 1 = 0.5 to the expectation value, giving a total expectation value of 1.5 + 0.5 = 2.0. We can clearly do better than this so one or both of these decisions is/are wrong.

I got the cause (sheep bleats) and effect (sheep of other colour jumps and changes colour) the wrong way around. My probabilities are in a sense inverted and thus wrong.

In my calculations, when you had 3 white and 1 black sheep, the probability that a white sheep changes to black was 3/4 when it actually should be 1/4. As I wrote, wrong way around.

I think you guys are correct that some of the example testcases may be incorrect... (2 2) should yield 2.2916667, (2 3) should be 2.3939394...

Kevin,

2.25 is not correct for (2,2). It is easy to demonstrate that 2.29166666667 is achievable. I did it with pencil and paper and confirmed it using my general strategy.

I see that this has just overlapped with Rodion's detailed explanation, which matches my pencil and paper approach.

You guys are correct! Caught my mistake and went back to correct it, but you guys caught it first.

And Rodion, we called that game "Red Rover" when I was a child. One team would yell "Red Rover! Red Rover! Send child_name over!", and then the named child from the other team would be the chain-breaker!

I did reconsider that, 2,3 looks correct to me. The other testcases look mostly correct, except I'm wondering if some of the decimal places for 15,100 result are wrong... should that one be 22.6717838 (instead of 22.67178696)?

Also, it looks like the checker actually does expect the testcase 2,2 to produce the result 2.75 instead of the correct 2.2916667... Currently trying to figure out why...
^ Looks like this was fixed!

Also, should the example answers be truncated to 1e-7 to align with the rounding being asked for? The checker still accepts answers accurate to more than that, but maybe it would be clearer if the examples were rounded off.

And if I remember correctly, I think the game title referred to "roving red-haired men" which originally referred to the Danish invaders in England?

The question states: Answers should be accurate to 1e-7. To me, that means that an answer will be accepted if it is within 1e-7 of the checker's answer, irrespective of the number of digits given. If rounding to 7 decimal places is required then this should be clearly stated. This actually requires greater accuracy than the previous requirement and has a particular responsibility on the checker to be accurate.