PROBLEM LINK:Author: Dmytro Berezin DIFFICULTY:CHALLENGE PREREQUISITES:none PROBLEM:You have matrix $A:M \times N \times N$. For each $1\leq k \leq M$ you choose $1\leq i_k,j_k\leq N$ which gives you $A_{kij}$ points. For each $k>1$ you draw segment from $(i_{k1},j_{k1})$ to $(i_k,j_k)$ on the plane and you can only choose such $(i_k,j_k)$ that this segment doesn't intersect any previous segments. Your aim is to maximize sum of scored points. Also you know that for generation of $A_{kij}$ was used one of two types of distributions:
EXPLANATION:Let us first talk about the first probability distribution. In this distribution, the high scoring values are scattered randomly around. So, the problem is almost like finding a tour with maximum possible score. Let us first identify some top values for each of the matrix, and now will try to take them using a tour. One possible solution is to just do the greedy by joining the adjacent pairs without taking care of that they intersect, when they intersect, just break out your solution. The other possible solution is to fix the order in which you are certain that there won't happen any intersection, for example increasing $x$, or increasing $y$. Now, in this scenario, do a greedy approach to maximize the score. The second distribution is more or less centered around the border and around the center. In that case, you are better in case you visit the cells in a connected component first type of the tour. For example, start from a corner and take some part of that corner by visiting (row 1, left to right, and then row 2 right to left and so on, in a connected fashion). This way visit the corners first, and finally come to the mid area of the rectangle and apply similar strategies there. Some sort of simulated annealing/hill climbing type optimizations can be applied too in order to improve these strategies even more. (It would be easier to improve in first case). Basically, we can try changing some of the intermediate cells of the path to some other node, this will be our transition. The top solution applies mentioned hill climbing strategy. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be updated soon. RELATED PROBLEMS:asked 18 Nov '17, 00:11
