@atul your understanding of my recurrences are fine but of the question are not. You cannot have 3 adjacent houses with same colour. GGY is a fine case for this problem. On 28 Dec 2013 20:44, "atul anand" <[email protected]> wrote:
> @saurabh : i did not get your algo for modified ques i.e "No 3 adjacent > houses should get same color" > > according to your recurrence > > answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) + colorvalue[j] for > all t from 1 to k except j. > > > now suppose in some case *answer[i-1][t][0] *is found minimum in > above recurrence . > *answer[i-1][t][0] *means that i - 2 and i - 1 are of same color say for > eg color green. > > answer[i][j][1] is not colored same as i-1 house (green in this case) > ...now say it is colored with color yellow. > > hence, > answer[i][j][1] is sum of house with color green+green+yellow. > > i am not able to understand , how it is taking care that 3 adjacent are > colored > different. > > could you please clarify my doubt. > > > > On Thu, Dec 26, 2013 at 5:25 PM, Saurabh Paliwal < > [email protected]> wrote: > >> @atul anand :- no, we need not use all the colors. >> >> @kumar raja :- sorry dude for replying this late. Continuing with the >> previous idea, I extend the solution for the modified problem as >> >> 1. let answer[i][j][0] represent minimum cost of coloring i houses when >> ith house is colored with jth color and so is the (i-1)th house. >> >> 2. let answer[i][j][1] represent minimum cost of coloring i houses when >> ith house is colored with jth color and (i-1)th is not. >> >> The recurrence will be >> >> 3. *answer[i][j][0] = answer[i-1][j][1] + colorvalue[j]* >> >> 4. *answer[i][j][1] = min(answer[i-1][t][0],answer[i-1][t][1]) + >> colorvalue[j]* for all t from 1 to k except j. >> >> // In the first problem, I mistakenly wrote colorvalue[t] here. It will >> be colorvalue[j] there. ( sorry for the confusion ) >> >> 5. finally solution will be min(answer[n][j][0], answer[n][j][1]) for all >> j from 1 to k. >> >> 6. initial settings -: answer[1][j][0] = answer[1][j][1] = colorvalue[j]. >> >> >> Also now that I read the problem, I guess colorvalue is not fixed for >> every color, so that will be a 2-D matrix as well. >> >> *replace every colorvalue[j] with colorvalue[i][j] in the above >> recurrences*. ( i is the house number, j is the color number ) >> >> >> On Wed, Dec 18, 2013 at 10:16 PM, atul anand <[email protected]>wrote: >> >>> @kumar : i have one doubt regarding this question.Do we have to use all >>> K colors[K] to color all building. >>> >>> for example :- >>> >>> color[3]={1,2,10}; >>> >>> now if we have to color 6 building then i can use only 1st 2 color to >>> color all building and never 10 ...is this allowed ??? >>> building[N]={1,2,1,2,1,2} >>> >>> >>> On Sun, Dec 15, 2013 at 12:44 AM, kumar raja >>> <[email protected]>wrote: >>> >>>> You have 'n' houses and 'k' colors. The cost of coloring a house with >>>> one of the 'k' colors is different from coloring another house with same >>>> color. The cost of coloring the house with different colors are different. >>>> So now how to colour the 'n' houses such that no two adjcent houses will >>>> get the same color and the total coloring cost for 'n' houses is minimized. >>>> >>>> >>>> >>>> Regards, >>>> Kumar Raja. >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to [email protected]. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> >> >> >> >> -- >> - Saurabh Paliwal >> >> B-Tech. Comp. Science and Engg. >> >> IIT ROORKEE >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
