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 anshumishra6...@gmail.comwrote: @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 sanjaypandey...@gmail.comwrote: 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.
[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
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.
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 bagop...@gmail.com 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
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.
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 sanjaypandey...@gmail.comwrote: 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
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 anshumishra6...@gmail.comwrote: @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 sanjaypandey...@gmail.comwrote: 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
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 anshumishra6...@gmail.comwrote: @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 sanjaypandey...@gmail.com 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.
[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.
