PROBLEM LINK:
Author: Tuan Anh Tran Dang
Tester: Gerald Agapov
Editorialist: Jingbo Shang
DIFFICULTY:
Challenge
PREREQUISITES:
Greedy, Dynamic Programming, Heuristic, Mixed Methods
PROBLEM:
Given a N*N matrix with colors ranging from 0 to 100, find the minimum number of painting operations needed to paint a initially all zero matrix to this given matrix. Each painting operation allows you to paint a rectangle area into a color.
EXPLANATION:
This is a challenge problem. The most important thing in solving challenge problem is to find some approximation methods or the plan to use the randomness of the cases, because the challenge problems are always NP-hard or NP-Complete. They are hard to be perfectly solved in polynomial times like other nine problems. Also, it is important to write a local test system to help you find the best strategy (almost all top ranked guys wrote their own test codes).
So let’s look at the test generation plan first. “The test data is generated randomly by simulating the process of making an image in SMPaint using no more than 500 Paint operations”, from this sentence, it is worth noting that the best answer should be no more than 500.
And then, let’s discuss some ideas and methods.
In the output description, there is a limit of output steps. It is easy to fit the constraints of N^2 steps. The most naive one, paints the matrix entry by entry.
Then, the first key idea is that reverse the procedure: choose the last painted rectangle area, and remove it by treating them as any color you want. It is straightforward to get a greedy method then:
while (there is any mismatch)
find the largest rectangle area with the same color
// could contains some painted ones
paint that area in one step
The finding procedure can be done by dynamic programming, similar to the largest empty rectangle problems (e.g. SPOJ 277 CTGAME). It could be done in O(N^2) time. Unfortunately, N is as large as 1,000. Therefore, if the answer is a little large, this greedy algorithm will get TLE. But, we can still apply this algorithm when N is small, such as N <= 600. This greedy algorithm and similar ones were a part of many submissions, such as the 4-th ranked submission from xyz111. It contains a lot of interesting specialized methods for smaller N. From here, we can see that the mixed methods are helpful to the challenge problems.
Since N is a little large, we should find some other efficient good solutions for larger cases. The most intuitive method is to find some good Heuristic Function (not necessary to find some proved/well defined one, just follow your intuition or local experimental results) to define how good the current matrix is. After we defined a such function, we could choose the “best” painting each steps, and finally reach the target matrix.
There are two problems though:
1. Too many choices. Too slow during choosing.
2. The "best" choice looks stupid sometimes.
For the first problem, we can design some simpler rules to maintain a small amount of candidate choices. Therefore, the choosing procedure will be cheaper.
For the second one, we can try some different functions together. For example, we have two functions F and G. We can get two possible solutions by them, and choose the best one. Also, we can randomly choose the trust one function each round (we can try random top-3 “best” choices during each round, too). Repeat this procedure multiple times and output the best solution will yield a good score. In the best submission from Mugurel Ionut Andreica, it looks like maintaining some (not many/all) “good” states and expanding them heuristically.
Of course, further discussions are welcome. 
