JAPC1004 Editorial

PROBLEM LINK:

Practice

Contest

Author: Debanshu Sekhar Jena

Tester: Pritish Priyatosh Nayak

Editorialist: A Rupeswar Subudhi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

dynamic programming

PROBLEM:

Given an array of houses, some of which may be coloured, find the minimum cost to colour the houses such that no two adjacent houses are of the same colour. You may not change the colour of previously coloured houses.

EXPLANATION:

Given: The cost of painting a house red, green and blue are C_r, C_g, C_b respectively.

Now, let us assume that we found the cheapest way to color the houses.
So, the colour of the last house will either be red, green, or blue. Now, we have 3 cases depending on the colour of last house,

Case 1: Red
If the colour of last house is red, the colour of the house before it must either be blue or green.
Let the minimum cost of painting such that the (N-1)th house is blue be x and the minimum cost of painting such that the (N-1)th house is green be y
Since it is the cheapest solution and C_r is a constant, the cost to paint the first N-1 houses must be min(x, y).
Hence total cost = C_r + min(x, y).

The cases where the last house is green and blue is similar to the first case.

Time Complexity : O(T * N)

SOLUTIONS:

Setter Solution