About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
January 2018 - Solution
The solution we designed was [AB,AC,AD,BC,BD,CD] = [23,1,20,19,15,14] ("WATSON").
There are many similar answers - Bert Dobbelaere gave us a different answer [1,1,16,1,15,8625], and Ozgur Sumer's solution (thanks!) is:
I arrived at this solution by a brute-force algorithm with a lot of branch pruning using mathematical insights. The mathematical insights are as follows
3450 | AB*AC*BC*AC*CD*AD. This is because the expectation calculation will have the AB*...*AD term as denominator with an integer numerator, and to get an integer numerator, the denominator must be divisible by 69 * 50 = 3450.
AD > 12 ==> otherwise the expectation <= 425.36/69 due to AD.
Without loss of generality, we can assume AB >= max(AC, BD, CD). This is because the problem is identical if A is swapped with D, or B is swapped with D.
AB >= 6, otherwise the path AB + BD < 10 brings the expectation <= 426.36/69. Note that AB >= BD is based on the previous assumption.
min(AB, AC, AD) <= 20, otherwise the expectation goes above the target. Just to get to anywhere from A is too costly in this case.
Once you fix five edges, the expectation value is monotone on the remaining edge.
While writing a program, we need to calculate the expectation accurately with 6 for loops, and this may be costly. So we have a Monte Carlo approximation along with an accurate computation.
When we try we will write conditions to reflect the insights I put above. Here the last insight is actually implying that the final loop can be a binary search.