PROBLEM LINK:
Author: Dmytro Berezin
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov
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_{k-1},j_{k-1}) 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:
- \left\lfloor 100 \cdot e^{d-100} \right\rfloor+1 where d is drawn from uniform real distribution on [0;100].
- \min_k[100\cdot2^{-X+d_k}+1] over 10 iterations where d is drawn from real distribution on [0;20] and X denote minimum of Manhattan distances of (k,i,j) from cells (k,1,1),~(k,1,N),~(k,N,1),~(k,N,N) and (k,N/2,N/2) and if value of element exceeds 100 we keep it to 100.
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.
Tester’s solution can be found here.