Re: [algogeeks] Re: Suggest Algo for this Question
@sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesra http://shashank7s.blogspot.com/ -- 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/-/lsuMzgEQdMwJ. 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: doubt in TSUM
@anubhaw ..its like spoon feeding , never mind u could have googled it :D http://www.google.co.in/search?q=3+sumie=utf-8oe=utf-8aq=trls=org.mozilla:en-US:officialclient=firefox-a Thanks Shashank Mani CSE, BIT Mesra http://shashank7s.blogspot.com/ -- 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/-/T06Sq0YuMP4J. 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: SPOJ . 10186.PUCMM025
hey ,i got the bug and got AC ALSO..there was several bugs ...sry ,for silly dbt -- 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: convert into palindrome
@Lucifer- thnks got ur logic...:)
On Thu, Dec 15, 2011 at 12:07 PM, Lucifer sourabhd2...@gmail.com wrote:
Correction:
for NAN :
N(IT)A + TI + N = NITATIN
On Dec 15, 11:33 am, Lucifer sourabhd2...@gmail.com wrote:
@topcoder..
String: NITAN
RevStr: NATIN
LCS ( NITAN, NATIN) = { NIN , NAN }
Here all we care about the count which is 2. Hence, 2 additions would
be required to convert it into a palindrome..
The possible palindromes would be:
for NIN :
N + AT + I(TA)N = NATITAN
for NAN :
N + TI+ A(IT)N = NATITAN
On Dec 15, 11:24 am, top coder topcode...@gmail.com wrote:
@Mohit
Suppose for example
String: NITAN
LCS(Longest Common Subsequence) : NIN
How do you get the palindrome with it?
On Dec 15, 3:47 am, Lucifer sourabhd2...@gmail.com wrote:
@Mohit
I think what he meant is 2* strlen(Input String) - 2* (Length of
LCS)
On Dec 15, 3:44 am, Mohit kumar lal kumarmohit...@gmail.com wrote:
@saurabh-as by the above example LCS of HELLO and its inverse
would be
LL and how can we form the word HELLOLLEH with it ...
and is your ans for the word NITAN is NITATIN ...?
On Wed, Dec 14, 2011 at 8:39 PM, saurabh singh
saurab...@gmail.com wrote:
Find the LCS of string with its reverse
On Wed, Dec 14, 2011 at 8:33 PM, top coder topcode...@gmail.com
wrote:
Given a word, convert it into a palindrome with minimum
addition of
letters to it. letters can be added anywhere in the word.
. for eg if hello is given, result should be hellolleh
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Mohit kumar lal
rit2009014
IIIT ALLAHABAD
contact@9454681805
kumarmohit...@gmail.com
mohitkumar...@yahoo.com
rit2009...@iiita.ac.inhttp://
profile.iiita.ac.in/rit2009014-Hidequoted text -
- Show quoted text -
--
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.
--
Mohit kumar lal
rit2009014
IIIT ALLAHABAD
contact@9454681805
kumarmohit...@gmail.com
mohitkumar...@yahoo.com
rit2009...@iiita.ac.in
http://profile.iiita.ac.in/rit2009014
--
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] Interesting Liked List problem..Suggest Algo
Twisted linked list problem: Two linked lists merge at some node p,both the head pointers are given find the merging point under the following restrictions. 1. You should not traverse to the end any of the linked list. 2. Merge node p should be detected by the time you reach at most most k nodes from p. 3. Space should not exceed by k units. 4. No saving of nodes to hard discs. 5. No recursion. Regards Ankur -- 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] Exclusively For You
I like this offer http://www.chrisbeck.de/inf.php It could be interesting for you, too -- 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] Interesting Liked List problem..Suggest Algo
in the link list take another variable suppose toggle and initialize all with 0,,, at the time of declaring the link list( so no traversal of entire link list).. now starting from both head traverse a single element at a time but in alternating way... for one linklist the toggling value is set to 1, while another linklist sets its next element value to 2, now for any one of the list that reaches to the merge point.. will change its value either by 1 or 2.. when the other one reaches the junction and if it finds a non zero b\value then will confirm it wil be the junction so without traversing the entire linklist one can determine the merge point -- Ravi Ranjan Sinha final yr computer science NIT Jalandhar 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] Interesting Liked List problem..Suggest Algo
seem like very twisted problem :P :P . lot of restriction. On Thu, Dec 15, 2011 at 7:30 PM, Ankur Garg ankurga...@gmail.com wrote: Twisted linked list problem: Two linked lists merge at some node p,both the head pointers are given find the merging point under the following restrictions. 1. You should not traverse to the end any of the linked list. 2. Merge node p should be detected by the time you reach at most most k nodes from p. 3. Space should not exceed by k units. 4. No saving of nodes to hard discs. 5. No recursion. Regards Ankur -- 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: convert into palindrome
Sorry for replying late...ya posted the reply in hurry.But it appears that
finally it has been resolved what i meant to say in my original post.
On Thu, Dec 15, 2011 at 6:38 PM, Mohit kumar lal kumarmohit...@gmail.comwrote:
@Lucifer- thnks got ur logic...:)
On Thu, Dec 15, 2011 at 12:07 PM, Lucifer sourabhd2...@gmail.com wrote:
Correction:
for NAN :
N(IT)A + TI + N = NITATIN
On Dec 15, 11:33 am, Lucifer sourabhd2...@gmail.com wrote:
@topcoder..
String: NITAN
RevStr: NATIN
LCS ( NITAN, NATIN) = { NIN , NAN }
Here all we care about the count which is 2. Hence, 2 additions would
be required to convert it into a palindrome..
The possible palindromes would be:
for NIN :
N + AT + I(TA)N = NATITAN
for NAN :
N + TI+ A(IT)N = NATITAN
On Dec 15, 11:24 am, top coder topcode...@gmail.com wrote:
@Mohit
Suppose for example
String: NITAN
LCS(Longest Common Subsequence) : NIN
How do you get the palindrome with it?
On Dec 15, 3:47 am, Lucifer sourabhd2...@gmail.com wrote:
@Mohit
I think what he meant is 2* strlen(Input String) - 2* (Length of
LCS)
On Dec 15, 3:44 am, Mohit kumar lal kumarmohit...@gmail.com
wrote:
@saurabh-as by the above example LCS of HELLO and its inverse
would be
LL and how can we form the word HELLOLLEH with it ...
and is your ans for the word NITAN is NITATIN ...?
On Wed, Dec 14, 2011 at 8:39 PM, saurabh singh
saurab...@gmail.com wrote:
Find the LCS of string with its reverse
On Wed, Dec 14, 2011 at 8:33 PM, top coder
topcode...@gmail.com wrote:
Given a word, convert it into a palindrome with minimum
addition of
letters to it. letters can be added anywhere in the word.
. for eg if hello is given, result should be hellolleh
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
--
Mohit kumar lal
rit2009014
IIIT ALLAHABAD
contact@9454681805
kumarmohit...@gmail.com
mohitkumar...@yahoo.com
rit2009...@iiita.ac.inhttp://
profile.iiita.ac.in/rit2009014-Hidequoted text -
- Show quoted text -
--
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.
--
Mohit kumar lal
rit2009014
IIIT ALLAHABAD
contact@9454681805
kumarmohit...@gmail.com
mohitkumar...@yahoo.com
rit2009...@iiita.ac.in
http://profile.iiita.ac.in/rit2009014
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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] Complexity
saurabh is right nd or U can also download lecture 2 of series Introduction to Algorithm mit lecture . It is jst awesome . On 12/15/11, saurabh singh saurab...@gmail.com wrote: Introduction to Algorithms Coreman On Wed, Dec 14, 2011 at 8:21 PM, Shashank Jain shashan...@gmail.com wrote: I need to study both space and time complexities. What is the best source? -- 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. -- Saurabh Singh B.Tech (Computer Science) MNNIT 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. -- *Durgesh Kumar* Final Year, B.tech Information Technology HALDIA INSTITUTE OF TCHNOLOGY HALDIA -- 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: Dynamic programming question
http://www.geeksforgeeks.org/archives/14943 is a very similar problem. On Thu, Dec 15, 2011 at 1:12 PM, WgpShashank shashank7andr...@gmail.comwrote: @Azhar , also for 1st question u r trying Array DS will suffices. Its Standard Coin Change Problem , u need to solve subproblem 1st , store it in extra array to avoid recalculation , if u are able to produce the sum less given sum then u can use same approach to reach desired sum . it uses the memozation (DP) approach solve efficiently . hope it help. Thanks Shashank Mani CSE, BIT Mesra http://shashank7s.blogspot.com/ -- 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/-/N3nEi3dNwR0J. 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] Interesting Liked List problem..Suggest Algo
@Ravi : your solution will not work for all the cases because of the restriction * * *1)You should not traverse to the end any of the linked list.* * * now consider one linked list to be very large while other is very small say 1/5 of the large one. now because second linked list is short and it will reach to the end of the linked list before first linked list has reached the intersection point hence it violates the rule. On Thu, Dec 15, 2011 at 8:56 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: in the link list take another variable suppose toggle and initialize all with 0,,, at the time of declaring the link list( so no traversal of entire link list).. now starting from both head traverse a single element at a time but in alternating way... for one linklist the toggling value is set to 1, while another linklist sets its next element value to 2, now for any one of the list that reaches to the merge point.. will change its value either by 1 or 2.. when the other one reaches the junction and if it finds a non zero b\value then will confirm it wil be the junction so without traversing the entire linklist one can determine the merge point -- Ravi Ranjan Sinha final yr computer science NIT Jalandhar 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. -- 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: Suggest Algo for this Question
@All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesrahttp://shashank7s.blogspot.com/ -- 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] Interesting Liked List problem..Suggest Algo
@Ravi : if your solution is acceptable then there is no need ok modifying data structure. we can use hashMap which table address and count as an input. then we can move in same fashion as you have mentioned , if count is of given address is 1 then it means that address is the intersection point. On Thu, Dec 15, 2011 at 10:19 PM, atul anand atul.87fri...@gmail.comwrote: @Ravi : your solution will not work for all the cases because of the restriction * * *1)You should not traverse to the end any of the linked list.* * * now consider one linked list to be very large while other is very small say 1/5 of the large one. now because second linked list is short and it will reach to the end of the linked list before first linked list has reached the intersection point hence it violates the rule. On Thu, Dec 15, 2011 at 8:56 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: in the link list take another variable suppose toggle and initialize all with 0,,, at the time of declaring the link list( so no traversal of entire link list).. now starting from both head traverse a single element at a time but in alternating way... for one linklist the toggling value is set to 1, while another linklist sets its next element value to 2, now for any one of the list that reaches to the merge point.. will change its value either by 1 or 2.. when the other one reaches the junction and if it finds a non zero b\value then will confirm it wil be the junction so without traversing the entire linklist one can determine the merge point -- Ravi Ranjan Sinha final yr computer science NIT Jalandhar 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. -- 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: Suggest Algo for this Question
@Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesrahttp://shashank7s.blogspot.com/ -- 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: find numbers if pair wise sums are given
Hi Topcoder. First of all you posted the wrong array . The array should be 4, 5, 10, 7, 12, 13 a+b a+c a+d b+cb+d c+d Now first calculate a+b+c+d which will be (sumofarray)/N-1 So here a+b+c+d = 17 Now take a[1] is a+c and a[N-1] = b+c subtracting them gives b-a = 2 a[0] is b+a=4 that gives b=3,a=1 Now u have a and b calculate c as a[1]-a=4 and d as9 . For this we traverse from a[1] to a[N-2] We calculate a and b because we know the order of sum of their elements(a+bis given and b's addition with rest elements are there in array) This will work in Linear Time Now lets take an example with 8 elements to let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8 then N=8 and array is 3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15 Now by above logic first a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36 Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5 a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1 Now we have a=1,b=2 So we traverse from a[1] to a[N-2] to calculate values c to h c= a[1]-a=4-1=3 d=a[2]-a=5-1=4 e=a[3]-a=6-1=5 similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8 This will work in O(n) Regards Ankur On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank shashank7andr...@gmail.comwrote: @all , a Naive Approach with Quadratic Time will be for each i=1 to n , check if i and a[i]-i makes given sum , so for each each number we will do the thus can achieve the solution ...i am just thinking about if we can do it linear time ..will post if able to do it :) Thanks Shashank CSe BIT Mesra -- 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/-/lF0kSVRUp5cJ. 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: find numbers if pair wise sums are given
on above algo , there is no need to calculate sum of array so we can do it in O(N) and not O(n). On Fri, Dec 16, 2011 at 12:59 AM, Ankur Garg ankurga...@gmail.com wrote: Hi Topcoder. First of all you posted the wrong array . The array should be 4, 5, 10, 7, 12, 13 a+b a+c a+d b+cb+d c+d Now first calculate a+b+c+d which will be (sumofarray)/N-1 So here a+b+c+d = 17 Now take a[1] is a+c and a[N-1] = b+c subtracting them gives b-a = 2 a[0] is b+a=4 that gives b=3,a=1 Now u have a and b calculate c as a[1]-a=4 and d as9 . For this we traverse from a[1] to a[N-2] We calculate a and b because we know the order of sum of their elements(a+bis given and b's addition with rest elements are there in array) This will work in Linear Time Now lets take an example with 8 elements to let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8 then N=8 and array is 3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15 Now by above logic first a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36 Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5 a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1 Now we have a=1,b=2 So we traverse from a[1] to a[N-2] to calculate values c to h c= a[1]-a=4-1=3 d=a[2]-a=5-1=4 e=a[3]-a=6-1=5 similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8 This will work in O(n) Regards Ankur On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank shashank7andr...@gmail.comwrote: @all , a Naive Approach with Quadratic Time will be for each i=1 to n , check if i and a[i]-i makes given sum , so for each each number we will do the thus can achieve the solution ...i am just thinking about if we can do it linear time ..will post if able to do it :) Thanks Shashank CSe BIT Mesra -- 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/-/lF0kSVRUp5cJ. 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: Suggest Algo for this Question
oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.comwrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have atmost two visited childrens so we have visted at-most 3K nodes isn;t it ? for total time O(K) ? let me know where i am wrong ? i am not getting for uy k nodes greater then x ? why we will do that then how much comparisons u needs for that ? Thanks Shashank Mani CSE, BIT Mesrahttp://shashank7s.blogspot.com/ -- 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
Re: [algogeeks] Re: find numbers if pair wise sums are given
I saw this term non-decreasing order So we need to sort the numbers first..it will take nlogn . On Fri, Dec 16, 2011 at 1:12 AM, Ankur Garg ankurga...@gmail.com wrote: on above algo , there is no need to calculate sum of array so we can do it in O(N) and not O(n). On Fri, Dec 16, 2011 at 12:59 AM, Ankur Garg ankurga...@gmail.com wrote: Hi Topcoder. First of all you posted the wrong array . The array should be 4, 5, 10, 7, 12, 13 a+b a+c a+d b+cb+d c+d Now first calculate a+b+c+d which will be (sumofarray)/N-1 So here a+b+c+d = 17 Now take a[1] is a+c and a[N-1] = b+c subtracting them gives b-a = 2 a[0] is b+a=4 that gives b=3,a=1 Now u have a and b calculate c as a[1]-a=4 and d as9 . For this we traverse from a[1] to a[N-2] We calculate a and b because we know the order of sum of their elements(a+bis given and b's addition with rest elements are there in array) This will work in Linear Time Now lets take an example with 8 elements to let a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8 then N=8 and array is 3 4 5 6 7 8 9 5 6 7 8 9 10 7 8 9 10 11 9 10 11 12 11 12 13 13 14 15 Now by above logic first a+b+c+d+e+f+g+h = (sum)/7 = 252/7 = 36 Now a[1]=a+c = 4 and a[N-1] =a[7]=b+c=5 a[8]-a[1]= b-a=1 and a+b=a[0]=3 gives b=2 and a =1 Now we have a=1,b=2 So we traverse from a[1] to a[N-2] to calculate values c to h c= a[1]-a=4-1=3 d=a[2]-a=5-1=4 e=a[3]-a=6-1=5 similarly f=a[4]=6,g=a[5]=7 and h=a[6]=8 This will work in O(n) Regards Ankur On Thu, Dec 15, 2011 at 12:42 PM, WgpShashank shashank7andr...@gmail.com wrote: @all , a Naive Approach with Quadratic Time will be for each i=1 to n , check if i and a[i]-i makes given sum , so for each each number we will do the thus can achieve the solution ...i am just thinking about if we can do it linear time ..will post if able to do it :) Thanks Shashank CSe BIT Mesra -- 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/-/lF0kSVRUp5cJ. 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] Interesting Liked List problem..Suggest Algo
i got my mistake.. den how to fulfill all the conditions?? -- 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: doubt in TSUM
shashank.dude the algorithm whch u suggested in the morning for tsum ...hv u tried it wid urself bcoz wid the wiki link method if we wl sort the array den wat b the delimiter so that ,i wl get get all combination of 3 .in dat method dat wz given for sum of three number equal to zero so we are checking for specific cases of 3 number sets..bt here we want all possible sets of 3 so hw it wl b possible to have it widout using n^3. -- 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] doubt in spoj 8473 ways
we have to submit it in 120 byte cn ne 1 tl me dat whr z the chances of
further byte reduction in this code.
#includestdio.h
#define s(n) scanf(%d,n)
#define I int
I a[14][14];I d(I m,I n){I s=a[m][n];I k;if(!m||!n)k=1;else
if(s)k=s;else{k=d(m-1,n)+d(m,n-1);s=k;}return k;}main(){I
t,n,k;s(t);while(t--){s(n);k=d(n,n);printf(%d\n,k);}}
tnx in advnce
--
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] doubt in spoj 8473 ways
Post the formatted code too.(With proper indents)Then it would be easier
for others to work on it,
On Thu, Dec 15, 2011 at 11:47 PM, anubhav raj anubhaw@gmail.com wrote:
we have to submit it in 120 byte cn ne 1 tl me dat whr z the chances of
further byte reduction in this code.
#includestdio.h
#define s(n) scanf(%d,n)
#define I int
I a[14][14];I d(I m,I n){I s=a[m][n];I k;if(!m||!n)k=1;else
if(s)k=s;else{k=d(m-1,n)+d(m,n-1);s=k;}return k;}main(){I
t,n,k;s(t);while(t--){s(n);k=d(n,n);printf(%d\n,k);}}
tnx in advnce
--
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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT 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.
[algogeeks] zig zag problem
Problem Statement A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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] zig zag problem
It is dynamic programming. Search in topcoder algo tutorials On Dec 16, 2011 10:33 AM, Sangeeta sangeeta15...@gmail.com wrote: Problem Statement A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence. For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero. Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order -- 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] Dynamic programming problem
Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S. For a better understanding let's take this example: Given coins with values 1, 3, and 5. And the sum S is set to be 11. -- 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] Dynamic programming problem
use dynamic programming to solve this problem :- here is the algo:- result[S]; result[0]=1; index; for i=0 to len(coins[]) c=coins[i]; for k=c to S index=k-c; result[k]= result[k] + result[index]; end end print result[S]; On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta sangeeta15...@gmail.com wrote: Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S. For a better understanding let's take this example: Given coins with values 1, 3, and 5. And the sum S is set to be 11. -- 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] Dynamic programming problem
give explaination On Fri, Dec 16, 2011 at 11:14 AM, atul anand atul.87fri...@gmail.comwrote: use dynamic programming to solve this problem :- here is the algo:- result[S]; result[0]=1; index; for i=0 to len(coins[]) c=coins[i]; for k=c to S index=k-c; result[k]= result[k] + result[index]; end end print result[S]; On Fri, Dec 16, 2011 at 10:52 AM, Sangeeta sangeeta15...@gmail.comwrote: Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S. For a better understanding let's take this example: Given coins with values 1, 3, and 5. And the sum S is set to be 11. -- 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. -- 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: zig zag problem
int LIDS ( vectorint a , int n ){
int s[51][2];
for(int i = 0 ; i n ; i++)
for(int j = 0 ; j 2 ; j++)
s[i][j] = 1;
for(int i = 0 ; i n ; i++){
for(int j = 0 ; j i ; j++){
if( a[i] != a[j] ){
s[i][a[i]a[j]] = max(s[j][a[i]a[j]] + 1 , s[i]
[a[i]a[j]]);
}
}
}
return max( s[n-1][0] , s[n-1][1] );
}
On Dec 16, 10:09 am, Azhar Hussain azhar...@gmail.com wrote:
It is dynamic programming.
Search in topcoder algo tutorials
On Dec 16, 2011 10:33 AM, Sangeeta sangeeta15...@gmail.com wrote:
Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative. The first difference (if one exists) may be either positive
or negative. A sequence with fewer than two elements is trivially a
zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences
(6,-3,5,-7,3) are alternately positive and negative. In contrast,
1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because
its first two differences are positive and the second because its last
difference is zero.
Given a sequence of integers, sequence, return the length of the
longest subsequence of sequence that is a zig-zag sequence. A
subsequence is obtained by deleting some number of elements (possibly
zero) from the original sequence, leaving the remaining elements in
their original order
--
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.
- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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] given a stream of numbers FIND MEDIAN
You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. -- 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.
