This problem is just a technic problem. So, you should take weights one by one and place the current one into the side of the scales that contains lower number of weights. At the end you should output answer in the correct format.
In the problem you should understand, what is the structure of Artur's operation. You can see that this operation is near operation (b + x) % w (To see that just apply b = w - b - 1). There is nothing hard to get the formula of changing a during the operation. So, if you have k operations, you can see, that b = (b + k·x) % w, a = a - (b + k·x) / w, c = c - k. When you've got all the formulas, you can solve the problem using binary search.
This problem is about considering cases:
1) If n = 1, the answer is -1. Because of any two numbers is arithmetical progression.
2) If array is constant, the answer if that constant.
3) If you have arithmetical progression initially, you can compute its difference d. In this case you should just to output minVal - d, and maxVal + d, where minVal is minimum value among a[i], and maxVal is maximum value among a[i]. But in case of n = 2, also you should check (a + a) / 2. If this number is integer, it is needed to be output.
4) Else, the answer has at most one integer. You find this integer you should sort the sequence, and find the place where the number is missed. If such a place exists you should add the corresponding number to the sequence, else, the answer is 0.
5) In all other cases the answer is 0.
In this problem from every cell except # there is one next cell. That's why this graph is almost functional graph. If this graph contains a cycle, then answer is -1 because the length of the cycle is at least two.
In the other case, there are no cycles in the graph. Let's find the longest path in it, denote is as len. Then is answer is at least 2·len - 1 because we can put the two pawns in the first two cells of this path.
But in some cases we could get the answer 2·len if there are two non-intersecting by vertices (not #) paths of length len. They are non-intersecting because if they intersect in some cell then they will be equal to the end (and the statement says that such moves are invalid).
So, we should check if the graph contains two non-intersecting by vertices (not #) paths of length len. It could be done in any way. For example, using dfs searches.
In this problem you should count trees with some properties. It can be done using dynamic programming. The main idea is that the maximum mathing in tree can be found using simple dynamic dp[v][used] (v -- vertex, used — was this vertex used in matching). So you should to count the trees tou should include in state of the dynamic values dp[v]$ and dp[v].
In other words, you should use dynamic programming z[n][dp0][dp1] — number of rooted trees with n vertices and values of dynamic in root dp[root] = dp0 and dp[root] = dp1. But in simple implementation this solution will get TL. There are two ways to get AC. The first is to opltimize code and make precalc. The second is to optimize asymptotics.
The author's solution uses the second way. To optimize solution you should mark that values dp0 and dp1 differs at most by one. That is dp0 = dp1, or dp0 = dp1 + 1. So the first dynamic becomes r[n][dp0][add]. Another optimization is there are not so many triples (n, dp0, add) with non-negative values (about 250), so you can you use lazy programming to calculate this dynamic.
Comments that describe other solutions: