Re: [algogeeks] coloring problem Dynamic programming
Please elaborate the explanation, i want to understand it in detail. On 17 December 2013 11:36, Saurabh Paliwal saurabh.paliwa...@gmail.comwrote: 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 rajkumar.cs...@gmail.com 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 rajkumar.cs...@gmail.com wrote: No need for the explanation ,got it man thanks. On 15 December 2013 16:20, kumar raja rajkumar.cs...@gmail.com 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 saurabh.paliwa...@gmail.com 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 rajkumar.cs...@gmail.com 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 algogeeks+unsubscr...@googlegroups.com. -- -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 algogeeks+unsubscr...@googlegroups.com. -- 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 algogeeks+unsubscr...@googlegroups.com. -- 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 algogeeks+unsubscr...@googlegroups.com. -- 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 algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
@saurabh : answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. how this DP is taking care of the case where no adjacent house if of same color. what i understand from the DP is the following :- find minimum cost of coloring previous house with color t ( min(answer[i-1][t]) ) and add colorvalue[t] to it for finding minimum cost of coloring answer[i][j]. where t varies from 1 to k except j. - is taking care that ignore coloring house if it of same as colorvalue[t]. I dont see the above restriction of taken care of ... please explain and correct me if i am wrong. On Sun, Dec 15, 2013 at 9:47 AM, Saurabh Paliwal saurabh.paliwa...@gmail.com 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 rajkumar.cs...@gmail.comwrote: 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 algogeeks+unsubscr...@googlegroups.com. -- -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 algogeeks+unsubscr...@googlegroups.com. -- 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 algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] coloring problem Dynamic programming
ohh shoots...my bad.got this condition wrong t varies from 1 to k except j. now got it :)..ignore my previous comment :) :) On Tue, Dec 17, 2013 at 11:47 PM, atul anand atul.87fri...@gmail.comwrote: @saurabh : answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 to k except j. how this DP is taking care of the case where no adjacent house if of same color. what i understand from the DP is the following :- find minimum cost of coloring previous house with color t ( min(answer[i-1][t]) ) and add colorvalue[t] to it for finding minimum cost of coloring answer[i][j]. where t varies from 1 to k except j. - is taking care that ignore coloring house if it of same as colorvalue[t]. I dont see the above restriction of taken care of ... please explain and correct me if i am wrong. On Sun, Dec 15, 2013 at 9:47 AM, Saurabh Paliwal saurabh.paliwa...@gmail.com 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 rajkumar.cs...@gmail.comwrote: 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 algogeeks+unsubscr...@googlegroups.com. -- -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 algogeeks+unsubscr...@googlegroups.com. -- 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 algogeeks+unsubscr...@googlegroups.com.
