Practice
Div-2 Contest
Div-1 Contest
Author & Editorialist: Alei Reyes
Tester: Danya Smelskiy
DIFFICULTY:
TIE-BREAK.
PROBLEM:
We are given a matrix of N rows and N columns, the cell at position (i,j) has a strength T_{i,j}. Find the minimum number of laser shots to destroy all cells. The laser can be fired from the left or right of each row, or from the top or bottom of each column. The laser destroys all the cells in its way with a total strenght less than ore equal to F.
EXPLANATION:
The minimum number of shots to destroy one row of N cells using only horizontal shots can be calculated using the following dynamic programming
f[L][R] = minimum number of shots to destroy cells between L and R.
The recurrence relation is of the form f[L][R]=min(1+f[L'][R],1+F[L][R']) where L' and R' are the respective new indices if the laser is shot from the left or right respectively.
The following greedy score some points: While the matrix is not empty, find the row or column that requires the minimum number of shots (using the previous dp) and destroy it.
Note that after removing one row or column the dp must be recalculated. Since the dp is cuadratic, some heuristics to approximate the value can be used. The idea of only partially remove a preffix or suffix of the rows can also be incorporated.
Mihai Bunget: Random search
Mihai Bunget was the first one to AC the tie-break, moreover his solution is very simple and scores at least 50 points.
The idea is to flip a coin to chose a direction, and shot the laser only on the rows (or columns) from which at least X cells are destroyed, initially we can set X=512 . If no such file exists, we decrease X, rinse and repeat.
The state of the board can be represented as horizontal and vertical segments. Each segment contains only non-destroyed cells. When a laser is shot, the segments shrink.
The previous algorithm runs very fast, since we have 10s to solve the problem, we can keep it repeating many times searching for the best solution.
Lewin Gan: Score function heuristic
For each possible laser shot, let’s calculate two parameters:
- s, the total thickness sum of the destroyed cells
- c, the number of destroyed cells.
Which of the 4 \cdot n possible shots should we use?
Lewin designed the following score function to meassure the goodness of each each shot:
score(s,c) = \left\{ \begin{array}{ll} \sqrt c \cdot (4 \cdot F -s) & \quad s \leq f/2 \\ \sqrt c \cdot (F -s) & \quad s \gt f/2 \\ \end{array} \right.
The idea of the score function is to give weight to the number of destroyed cells, and penalize the shots with a small sum.
The laser shot with minimum score is fired, the matrix is updated and the process is repeated until all cells are destroyed.
I don’t know exactly how the function was designed, but we can try different score functions and choose the one that works better in practice. Also some machine learning approaches can help.
Hardifying problems
NBOTS is the 2D version of my BRKBKS. Just like in alchemy a cakewalk was converted into an unsolvable problem! Initially I included gravity i.e once the cells are destroyed they fall by gravity, and also there was the operation of rotation (after rotating the cells fall by gravity). However our admin told me that those operations could make it more unpredictable.