@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" <atul.87fri...@gmail.com> 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 <
> saurabh.paliwa...@gmail.com> 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 <atul.87fri...@gmail.com>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
>>> <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.
>>>>
>>>
>>> --
>>> 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.
