Please elaborate the explanation, i want to understand it in detail.
On 17 December 2013 11:36, Saurabh Paliwal <[email protected]>wrote: > I think that can be done by having 2 different values at every position in > the answer matrix. One when the previous house is of same color and one > when it does not. Answer[n][k][2] will be the new dimensions. > > I can explain in detail if you don't get this. ☺ > On Dec 15, 2013 4:43 PM, "kumar raja" <[email protected]> wrote: > >> What can be the recurrence relation if the condition is changed to "No 3 >> adjacent houses should get same color"? >> >> >> On 15 December 2013 16:26, kumar raja <[email protected]> wrote: >> >>> No need for the explanation ,got it man thanks. >>> >>> >>> On 15 December 2013 16:20, kumar raja <[email protected]> wrote: >>> >>>> Saurabh your solutions seems right , but can u explain me how did u >>>> arrive at the time and space complexity with some proof /pseudocode/ >>>> explanation? >>>> >>>> >>>> On 15 December 2013 09:47, Saurabh Paliwal <[email protected] >>>> > wrote: >>>> >>>>> what is the issue with the usual recurrence :- >>>>> >>>>> Let answer[i][j] represent minimum cost of coloring i houses with ith >>>>> house colored with jth color. >>>>> >>>>> answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from >>>>> 1 to k except j. >>>>> >>>>> initial setting :- answer[1][j] = colorvalue[j] >>>>> >>>>> final answer is min(answer[n][j]) for all j from 1 to k. >>>>> >>>>> Time complexity = O(n*k*k) >>>>> Space complexity = O(k) if only 2 rows are taken ( effectively only 2 >>>>> are required ). >>>>> >>>>> >>>>> 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]. >>>>>> >>>>> >>>>> >>>>> >>>>> -- >>>>> - 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]. > -- 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].
