In this problem you're given an N by N grid, where each cell is either empty or colored in a certain color. Your task is to color some of the cells, so that each of the colors forms a single 4-connected region of cells. Since we don't have to restrict ourselves to real-world limitations, it is allowed to color the same cell into more than one color. In particular, it is allowed to color cells which are already colored in the initial grid.
Test case generation:
Unless specified otherwise, all random variables are sampled from uniform distribution.
- N is randomly generated in [20, 60] range.
- colorsSize is randomly generated in [2, 5] range.
- coloredCellsSize is randomly generated in [N / 2 (integer division), 4 * N] range.
- colorWeights is an array of doubles with a size of equal to colorsSize. Each element of the array is generated independently and it is equal to rand() * rand(), where rand() function generates a random double in [0.0, 1.0) range.
- penalty is randomly generated in [N, 8 * N] range.
After all of the above variables are generated, we generate the grid. The grid is N by N and exactly coloredCellsSize cells are colored. The cells to be colored are chosen randomly. The color of each cell is determined independently and the probability that a given cell gets colored into a specific color is proportional to the element of colorWeights corresponding to that color. Please note that some colors may turn to be not used at all.
You need to implement link method that takes String grid and int penalty and returns a valid coloring. The grid is formatted as follows: each element describes one row of cells and each character describes a single cell. That means that grid[r][c] describes the cell at row r and column c. Empty cells are represented by '-' (dash) character and digits from '0' to '4' represent different colors.
You should return an array of integers. For each cell that you want to color, you have to return 3 integers (all 0-based) describing its row, column and color. More formally, if you want to color X cells, your return should contain 3 * X integers and elements 3 * k + 0, 3 * k + 1, 3 * k + 2, 0 <= k < X, must describe one of the colored cells. Remember that you can color one cell into many colors. In this case you need to include a separate triple for each of the colors you use for that cell. You are also required to include triples for the initially colored cells that are given to you in grid parameter.
Raw score for a test case is equal to the sum of scores for each cells. Score for each cell is equal to colors_used + colors_used * (colors_used - 1) * penalty, where colors_used is the number of colors used in that particular cell. If we fail to get your return value (time limit, memory limit, crash, etc.) or if it does not define a valid coloring, then your raw score for that test case will be 0.
In this contest we use relative scoring and your task is to minimize the score. This means that your score for each test will be equal to best score (lowest positive score among all of the competitors) divided by your score: normalizedScore = bestRawScore / rawScore. The small exception is, when your rawScore is 0 then your normalizedScore will also be 0. Your overall score will be equal to 1000000 * (the arithmetic average of your normalized scores for all test cases). This is the score you will see on the standings page.
An offline tester/visualizer tool is available.