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.