PROBLEM LINK:Author: Tuan Anh Tran Dang 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 NPhard or NPComplete. 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:
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 4th 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:
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 top3 "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. :D
This question is marked "community wiki".
asked 01 Jan '14, 19:10

FYI, my approach which became 2nd: Note that as mentioned in editorial if the paintings are done in reverse order, then each pixel may be colored infinite times, but still only the first time colored remains So we only paint a rectangle if there are no pixels left that have another color or are unpainted. My algorithm (part 1):
Split: put all pixels of S with the color of the overlapping shape into a new shape which is added to L Shrink: remove the pixels of the existing overlapping shape, and try again to minimize its size
The result of this algorithm is a directed acyclic graph The 2nd part of the algorithm is painting the Shapes from P in reverse order, and each time notifying the shapes that are depending on the drawn shape. E.g. In this example P = [2, 9, 10]
A possible actual result of these shapes would be 7, 5, 11, 3, 8, 2, 9, 10 where each number stands for a paint operation Remarks:
answered 02 Jan '14, 05:43
glad to hear your great algorithm!
(02 Jan '14, 10:17)
Amazing!...
(02 Jan '14, 11:53)
Good work.
(02 Jan '14, 13:36)
thank you very much !
(02 Jan '14, 18:16)

My approach, not very good but easy to implment (http://www.codechef.com/viewsolution/3102955) was
For ex: to get
Step 1: 1 can be drawn as
Because all number we are overpainting are larger, and they would later get corrected. Step 2: After we encounter a smaller color (already used one) in 2's bounding box, we break it into smaller boxes. So 2 would be drawn in
Step 3: Similarly 3's bounding box is contain 2's in it. Splitting it we get
By the time we finish 100 steps, we would get our final answer. Unfortunately I could not get time to debug and correct my solution. May be someday I would debug and upload. answered 02 Jan '14, 13:35
