Re: [algogeeks] Programming Problem
@ ashish the example which you given here ie aaab and at the end you said that ba is the beautiful string how com ba can be derived or produced from aaab becoz as per the definition String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. and ba sequence is not there in aaab On Friday, 20 July 2012 03:00:42 UTC-7, ashish jain wrote: @piyus khanna--- while forming a BST with aaab and removing duplicates if a charcter occur once .. so for aaab first make a node for 'a'. and ignore next two a's as they are already on the BST. next is 'b'. make 'b' as root and 'a' on the right side.. and use inorder parsing to get 'ba' as the unique beautiful string. On Fri, Jul 20, 2012 at 12:22 PM, piyush khanna piyush_khanna2...@yahoo.com wrote: @ashish jain :then what for aaab.. -- *From:* ashish jain ashishjainco...@gmail.com *To:* algogeeks@googlegroups.com *Sent:* Thursday, July 19, 2012 9:48 PM *Subject:* Re: [algogeeks] Programming Problem if from the string s.. a binary search tree (with higher value alphabets on the left side of the root and lower value alphabets on the right side of root) is formed removing the repeated characters during the formation of he BST and then applying inorder technique to get the string s2. String S2 will give the most beautifull unique string producible from s. ^^ Correct me if wrong!! On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb gobind.h...@gmail.comwrote: String s is called *unique* if all the characters of s are different. String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. String s1 is *more beautiful* than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the *most beautiful unique* string that is producible from s. *Input:* First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. *Output:* Print the most beautiful unique string that is producable from s *Sample Input:* babab *Sample Output:* ba *Explanation* In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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. -- 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/-/A5ao8mbElD8J. 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] Programming Problem
@ashish jain :then what for aaab.. From: ashish jain ashishjainco...@gmail.com To: algogeeks@googlegroups.com Sent: Thursday, July 19, 2012 9:48 PM Subject: Re: [algogeeks] Programming Problem if from the string s.. a binary search tree (with higher value alphabets on the left side of the root and lower value alphabets on the right side of root) is formed removing the repeated characters during the formation of he BST and then applying inorder technique to get the string s2. String S2 will give the most beautifull unique string producible from s. ^^ Correct me if wrong!! On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb gobind.h...@gmail.com wrote: String s is called unique if all the characters of s are different. String s2 is producible from string s1, if we can remove some characters of s1 to obtain s2. String s1 is more beautiful than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the most beautiful unique string that is producible from s. Input: First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. Output: Print the most beautiful unique string that is producable from s Sample Input: babab Sample Output: ba Explanation In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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] Programming Problem
@piyus khanna--- while forming a BST with aaab and removing duplicates if a charcter occur once .. so for aaab first make a node for 'a'. and ignore next two a's as they are already on the BST. next is 'b'. make 'b' as root and 'a' on the right side.. and use inorder parsing to get 'ba' as the unique beautiful string. On Fri, Jul 20, 2012 at 12:22 PM, piyush khanna piyush_khanna2...@yahoo.com wrote: @ashish jain :then what for aaab.. -- *From:* ashish jain ashishjainco...@gmail.com *To:* algogeeks@googlegroups.com *Sent:* Thursday, July 19, 2012 9:48 PM *Subject:* Re: [algogeeks] Programming Problem if from the string s.. a binary search tree (with higher value alphabets on the left side of the root and lower value alphabets on the right side of root) is formed removing the repeated characters during the formation of he BST and then applying inorder technique to get the string s2. String S2 will give the most beautifull unique string producible from s. ^^ Correct me if wrong!! On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb gobind.h...@gmail.comwrote: String s is called *unique* if all the characters of s are different. String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. String s1 is *more beautiful* than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the *most beautiful unique* string that is producible from s. *Input:* First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. *Output:* Print the most beautiful unique string that is producable from s *Sample Input:* babab *Sample Output:* ba *Explanation* In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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. -- 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] Programming Problem
Can't we simply hash all the characters in an array and then print the
occurrence of each character in lexicographically decreasing order? This
way, it'll have all unique characters, will be the longest possible string
and will be derivable from s.
int hash[26] = {0};
hash all inputs using :-hash[input_char - 'a']
for i=25 to 0
if(hash[i])
print i+'a';
TC: O(n)
Any improvements/ suggestions/ corrections?
On Fri, Jul 20, 2012 at 3:30 PM, ashish jain ashishjainco...@gmail.comwrote:
@piyus khanna---
while forming a BST with aaab and removing duplicates if a charcter occur
once ..
so for aaab
first make a node for 'a'.
and ignore next two a's as they are already on the BST. next is 'b'.
make 'b' as root and 'a' on the right side..
and use inorder parsing to get 'ba' as the unique beautiful string.
On Fri, Jul 20, 2012 at 12:22 PM, piyush khanna
piyush_khanna2...@yahoo.com wrote:
@ashish jain :then what for aaab..
--
*From:* ashish jain ashishjainco...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Thursday, July 19, 2012 9:48 PM
*Subject:* Re: [algogeeks] Programming Problem
if from the string s.. a binary search tree (with higher value alphabets
on the left side of the root and lower value alphabets on the right side of
root) is formed removing the repeated characters during the formation of he
BST and then applying inorder technique to get the string s2.
String S2 will give the most beautifull unique string producible from s.
^^ Correct me if wrong!!
On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb gobind.h...@gmail.comwrote:
String s is called *unique* if all the characters of s are different.
String s2 is *producible* from string s1, if we can remove some
characters of s1 to obtain s2.
String s1 is *more beautiful* than string s2 if length of s1 is more
than length of s2 or they have equal length and s1 is lexicographically
greater than s2.
Given a string s you have to find the *most beautiful unique* string
that is producible from s.
*Input:*
First line of input comes a string s having no more than 1,000,000(10^6)
characters. all the characters of s are lowercase english letters.
*Output:*
Print the most beautiful unique string that is producable from s
*Sample Input:*
babab
*Sample Output:*
ba
*Explanation*
In the above test case all unique strings that are producible from s are
ab and ba and ba is more beautiful than ab.
--
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.
--
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] Programming Problem
String s is called *unique* if all the characters of s are different. String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. String s1 is *more beautiful* than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the *most beautiful unique* string that is producible from s. *Input:* First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. *Output:* Print the most beautiful unique string that is producable from s *Sample Input:* babab *Sample Output:* ba *Explanation* In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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] Programming Problem
if from the string s.. a binary search tree (with higher value alphabets on the left side of the root and lower value alphabets on the right side of root) is formed removing the repeated characters during the formation of he BST and then applying inorder technique to get the string s2. String S2 will give the most beautifull unique string producible from s. ^^ Correct me if wrong!! On Thu, Jul 19, 2012 at 11:00 AM, gobind hemb gobind.h...@gmail.com wrote: String s is called *unique* if all the characters of s are different. String s2 is *producible* from string s1, if we can remove some characters of s1 to obtain s2. String s1 is *more beautiful* than string s2 if length of s1 is more than length of s2 or they have equal length and s1 is lexicographically greater than s2. Given a string s you have to find the *most beautiful unique* string that is producible from s. *Input:* First line of input comes a string s having no more than 1,000,000(10^6) characters. all the characters of s are lowercase english letters. *Output:* Print the most beautiful unique string that is producable from s *Sample Input:* babab *Sample Output:* ba *Explanation* In the above test case all unique strings that are producible from s are ab and ba and ba is more beautiful than ab. -- 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] programming problem
The following is a statement of a programming problem i encountered I don't know how to solve it. Any ideas?? The owner of shop Jell Bells has order a large consignment of jell balls which is about to arrive. He has hired you as an assistant to help him sort the balls and put them in their respective containers at the shop (pretty simple ? HuH!!). Now the Job Profile Is:- The balls are of different colors (say n), though many of the colors are repeated. Whenever the balls are removed from the consignment, they have to be kept in some temporary sack (say a stack) with each ball on top of other in no particular order. Each sack is of infinite capacity and you can use as many sacks as u like. When all the balls are removed from the consignment, they are then to be put in their respective colored containers at the store. Here comes the tricky thing, any colored container can be given to you by the owner to be filled. All the balls of that particular color have to be put in container at once. It may be possible that that particular colored ball is at the bottom of the sack, then you have to first move all the balls above it in some other sack. The owner wants that the number of temporary sacks multiplied by the number of moves is minimum. (How moves are counted when a ird move) and so on, then finally to the container (last move) for that particular ball). Once the things are sorted, you get your pay (and some jell balls too. Yummy!!) INPUT The first line of input contains an integer X, specifying the number of test cases. Second line contains number of containers N, and the number of balls M. the third line is the sequence in which the balls are removed from the consignment. Fourth is the order in which the owner of shop gives you the containers to be filled. OUTPUT The first line of output will be the number of moves P, and the number of sacks used Q. From second line onwards you have to specify each and every move as described in the example below. EXAMPLE Say the N colors are represented by numbers 1 to n, the temporary sacks as temp1, Sample input 1 3 6 3 3 2 2 1 1 1 2 3 Sample output 12 1 Move 1 :: put ball 3 in temp1 Move 2 :: put ball 3 in temp1 Move 3 :: put ball 2 in temp1 Move 4 :: put ball 2 in temp1 Move 5 :: put ball 1 in temp1 Move 6 :: put ball 1 in temp1 Move 7 :: put ball 1 in cont1 Move 8 :: put ball 1 in cont1 Move 9 :: put ball 2 in cont2 Move 10 :: put ball 2 in cont2 Move 11 :: put ball 3 in cont3 Move 12 :: put ball 3 in cont3 --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
