Here's an interesting programming problem I've found...how would you solve it?

[Nineshadow]

Bill has a rather odd TV , that's because he didn't have the money to buy a better one. That's also why he hasn't shown it off to his friends. Be like Bill.

 

Let C be the number of distinct colours from Bill's universe ( considering 1 as white and C as black) .

His TV is initially black and white , meaning it can only show the colours 1 and C (white and black) .

 

For every arbitrary colour i ( i >= 2 , i <= c-1 ) , we know the cost_i necessary to upgrade Bill's TV so that it could show the i colour.

 

Bill has just found out that a photo of him is going to show up on the news. An image can be represented as a N*M matrix of integers , where the value at the i line and j column represent the culour of the pixel at that position.

The TV displays the image by this rules:

• If we have a pixel whose colour the TV can show , then the displayed colour will be that colour , obviously.
• If we have a pixel whose colour the TV can't show , then the TV will show the closest colour to the original one it can display. The distance between two colours is , of course , abs(colour₁ - colour₂). If there are more colours at a minimum distance to the original colour, then the colour with the biggest index will be displayed.

Note : initially the TV is black and white , so in the worst case , the colour of a pixel will be represented by 1 (white) or C (black).

 

Bill wants to pay as little as he can to upgrade his TV so that he can see himself "clearly" on the news. An image is considered "clear" if , however you picked two adjacent pixels with different colours from the original image , the pixels displayed by the TV will be different colours as well.

 

The input is structured as follows :

On the first line , 3 integers : N , M ,C , with the same meaning as above.

Then there will be the N*M matrix which represents the original image.

On the last line there will be C-2 integers representing the cost necessary to upgrade the TV to a particular colour ( the n-th value is cost_n+1 , the cost necessary to upgrade the TV with the colour n+1)

 

The output needs to be a single integer : the minimum cost necessary for the upgrade of the TV such as Bill's picture will be clear.

 

Restrictions :

• 1 <= N , M <= 500
• 3 <= C <=150.000
• Every pixel is an integer between [1,C]
• 1 <= cost_i <= 1.000.000.000
• For 20% of tests : N,M,C <= 50
• For 30% of tests : C <= 500
• For 40% of tests : C <= 2500
• Maximum execution time per test : 0.6 sec
• Memory limit : 16384 kbytes

Example:

Input file :

3 3 75 1 66 4 65 4 34 4 4 5 6

Output file :

13

________________________________________________________________________________

 

My main problem is getting a really nice and optimized solution. Right now I can only get ~40% of the total score.

[Mohenjo]

the answer is 2, your welcome. 

[DavidTheWin]

Haven't read all the details but this looks like a standard linear programming problem, look into the simplex algorithm.

[Nineshadow]

So apparently the official source file for this problem (from the guys who proposed it) is wrong. It doesn't fit in the time requirements , and nobody has found a better solution than that , so... the problem is kinda broken.