This is pretty simple task - we have cycle and must direct all edges on it in one of 2 directions. We need to calculate cost of both orientation and print smallest of them.
There is a small trick - we can calculate cost of only one orientation and then cost of the other will be sum of costs of all edges minus cost of first orientation.
Also very simple - we need literary do what we asked. We put all data in a map where for each pilot we have number of points and array of 50 elements - number of times pilot finished at corresponding place. Then we just need to find maximum in this array according to 2 given criteria.
Reflection over 2 points is just a parallel shift for a doubled vector between them. So M2n = M0 because sequence of reflections may be replaced with sequence of shifts with doubled vectors A0A2, A2A4, ..., An - 2A0 - and their sum is 0. So we can replace j with j' = jmod2N. Now we can just perform j' reflections. Suppose we need to find M' (x', y') - reflection of M(x, y) witch center at A(x0, y0). Then x' = 2x0 - x, y' = 2y0 - y.
If robot is at last row then answer is 0. Suppose that for every cell of the next row we now expected number of steps to reach last row - zi. Let xi be expected value of steps to reach the last row from current row. Then we have following system of equations:
x1 = 1 + x1 / 3 + x2 / 3 + z1 / 3
xi = 1 + xi / 4 + xi - 1 / 4 + xi + 1 / 4 + zi / 4 for i from 2 to M - 1
xM = 1 + xM / 3 + xM - 1 / 3 + zM / 3
This is tridiagonal system, it can be solved using tridiagonal matrix algorithm in linear time.
So we just have to solve this for each row starting from N - 1 and ending at i and then take x[j].
For M = 1 the answer is 2(N - i) because expected number of steps to go down is 2 - on each turn we either go down or stay
At first we need to exclude answer -1. Answer is -1 if and only if first part of particles moves left and second part moves right (any of this parts may be empty)
Let's use binary search. Maximal answer is 1e9. Suppose we need to unserstand - whether answer is more then t or less then t. Let's itirate particles from left to right and maintain maximal coordinate that particle moving right would achive. Then of we will meet particle moving left that will move to the left of that coordinate in time t that we have 2 particles that will collide before time t. Otherwise we won't have such pair of particles.