Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
for your example 5 4 3 2 1 5 4 3 2 1 -- candies assignement. (since the length of the longest decreasing sequence is 4, and length of increasing seq. before it is 0. its max(0+1,4)+1 = 5 --Sravan Reddy On Tue, Jul 10, 2012 at 8:09 AM, bala bharath wrote: > > can u explain ur algorithm for the sequence > > * > 5 4 3 2 1* > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
can u explain ur algorithm for the sequence * 5 4 3 2 1* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
@sumit the sequence is fixed -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
@g4... : Is the sequence in which children are arranged is fixed or the teacher can change the sequence to minimize the candies ? On Mon, Jul 9, 2012 at 3:58 PM, Anshu Mishra wrote: > @sanjay it's not like that > > e.g : (3 5 6 7 8 4) 7 > 1 2 3 4 5 1 2 > Yes we have to increase just by one, but while decreasing choose the > lowest possible such that each trivial component, if it is in decreasing > phase, should end with 1. > > On Mon, Jul 9, 2012 at 12:53 PM, sanjay pandey > wrote: > >> does ur sol seems lyk incerasing 1 if next number is greater that prev n >> decreasing 1 if less..??? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Anshuman Mishra | Software Development Engineer | Amazon > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
a very good counter example. for the approach. even thought you didn't solve as per my solution. (1 2 3 4 5 6 3 2) (6 9 10 12 6 5 4 3 2 1) A small change to the original algorithm. The candies to max. element in each trivial array is max(elements_before_it + 1 ,elements_after_it) + 1 And, start with 2 in each subarray except the first one, where we start with 1. and.. keep increasing until max is reached. for the decreasing sequence. start with (number of elements in decreasing seq. and reach until 1. (1 2 3 4 5 6 3 2) (6 9 10 12 6 5 4 3 2 1) 1 2 3 4 5 6 2 1 2 3 4 (5/7) 6 5 4 3 2 1 so, candies for 12 will be *max (3+1, 6) + 1* 1 2 3 4 5 6 *2 1* 2 3 4 (5/7) 6 5 4 3 2 1 you gave a wrong assignment as (5,4) instead of (2,1) underlined above. this was the point where your did a mistake with my solution. On Monday, 9 July 2012 11:04:40 UTC-4, Bhaskar wrote: > > take a test case: > 1 2 3 4 5 6 3 2 6 9 10 12 6 5 4 3 2 1 > > the subarrays then are: > (1 2 3 4 5 6 3 2 ) (6 9 10 12 6 5 4 3 2 1) > 1 2 3 4 5 6 5 44 5 6 7 6 5 4 3 2 1 -->candies allotment on > solving subarrays.. > > here both are given same candies which is wrong ! > I mean that the subarrays solution are not independent! > > > On Mon, Jul 9, 2012 at 3:58 PM, Anshu Mishra wrote: > >> @sanjay it's not like that >> >> e.g : (3 5 6 7 8 4) 7 >> 1 2 3 4 5 1 2 >> Yes we have to increase just by one, but while decreasing choose the >> lowest possible such that each trivial component, if it is in decreasing >> phase, should end with 1. >> >> On Mon, Jul 9, 2012 at 12:53 PM, sanjay pandey > > wrote: >> >>> does ur sol seems lyk incerasing 1 if next number is greater that prev n >>> decreasing 1 if less..??? >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Anshuman Mishra | Software Development Engineer | Amazon >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > regards, > Bhaskar Kushwaha > Student > Final year > CSE > M.N.N.I.T. Allahabad > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/pGua7kg5LvUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
take a test case: 1 2 3 4 5 6 3 2 6 9 10 12 6 5 4 3 2 1 the subarrays then are: (1 2 3 4 5 6 3 2 ) (6 9 10 12 6 5 4 3 2 1) 1 2 3 4 5 6 5 44 5 6 7 6 5 4 3 2 1 -->candies allotment on solving subarrays.. here both are given same candies which is wrong ! I mean that the subarrays solution are not independent! On Mon, Jul 9, 2012 at 3:58 PM, Anshu Mishra wrote: > @sanjay it's not like that > > e.g : (3 5 6 7 8 4) 7 > 1 2 3 4 5 1 2 > Yes we have to increase just by one, but while decreasing choose the > lowest possible such that each trivial component, if it is in decreasing > phase, should end with 1. > > On Mon, Jul 9, 2012 at 12:53 PM, sanjay pandey > wrote: > >> does ur sol seems lyk incerasing 1 if next number is greater that prev n >> decreasing 1 if less..??? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Anshuman Mishra | Software Development Engineer | Amazon > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- regards, Bhaskar Kushwaha Student Final year CSE M.N.N.I.T. Allahabad -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
@sanjay it's not like that e.g : (3 5 6 7 8 4) 7 1 2 3 4 5 1 2 Yes we have to increase just by one, but while decreasing choose the lowest possible such that each trivial component, if it is in decreasing phase, should end with 1. On Mon, Jul 9, 2012 at 12:53 PM, sanjay pandey wrote: > does ur sol seems lyk incerasing 1 if next number is greater that prev n > decreasing 1 if less..??? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Anshuman Mishra | Software Development Engineer | Amazon -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
does ur sol seems lyk incerasing 1 if next number is greater that prev n decreasing 1 if less..??? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
Requires review and comments: My solution: find the continuous increasing sequences from the input followed by continues decreasing array. let there are k such array (continuous increase followed by continuous decrease) Now we have the trivial components. find sum for each such array.. and sum all those. 4 5 2 3 6 5 4 7 8 2 1 2 1 3 2 4 trivial components from the above input are (4 5 2) (3 6 5 4) (7 8 2 1) (2 1) (3 2) (4) 1 2 1 2 3 2 1 2 3 2 1 2 1 2 1 2 <--- and candies for them are solution. solutions for the trivial are simple.. things become interesting when teacher arranges in circle instead of line.. -- On Sunday, 8 July 2012 08:26:11 UTC-4, g4ur4v wrote: > Alice is a teacher of kindergarten. She wants to give some candies to > the children in her class. All the children sit in a line and each > of them has a rating score according to his or her usual > performance. Alice wants to give at least 1 candy for each children. > Because children are somehow jealousy. Alice must give her candies > according to their ratings subjects to for any adjacent 2 children if > one's rating is higher than the other he/she must get more candies > than the other. Alice wants to save money so she wants to give as few > as candies in total. > > > Input > > The first line of the input is an integre N, the number of children in > Alice's class. Each of the following N lines contains an integer > indicates the rating of each child. > > Ouput > > On the only line of the output print an integer describing the minimum > number of candies Alice must give. > > Sample Input > > 3 > 1 > 2 > 2 > > Sample Ouput > > 4 > > Explanation > > The number of candies Alice must give are 1,2 and 1. > > Constraints: > > N and the rating of each children is no larger than 10^5. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/SBGlA8Z32vAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
