Re: [algogeeks] BST Question
> > Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Least fare for a return trip Algorithm
@Dave You are partly correct. If i ask for four minimum fares for the round trip then first suggestion is what u said : sum the sum of the minimum cost from A to B and the minimum cost from B to A after that we have to see which combination from both costs, sums up least On Oct 14, 9:55 am, Dave wrote: > @Amod. Isn't the minimum sum the sum of the minimum cost from A to B > and the minimum cost from B to A? What am I missing? > > Dave > > On Oct 13, 11:06 pm, Amod wrote: > > > > > Hi > > > I think I forgot to mention that the SUM of the ROUND trip i.e. A->B->A > > (sum = going + returning) should be least. > > > Please don't take into account any other thing like time and > > availability. > > So solution is not that straightforward. > > > Its like we have two arrays and we have to return least k sum from the > > given arrays where we take one element from the first and one from > > second in the sum. > > > Cheers > > Amod > > > On Oct 13, 2:26 pm, Shiyam code_for_life > > wrote: > > > > When a user wants to choose to fly from A to B, suggest the flight > > > with lowest fare that's available, here its A1, if A1 is busy then A2 > > > and so on > > > Repeat the same for B to A. > > > > Am I missing something here? > > > > Complexity is O( (number of flights from A to B) + number of flights > > > from B to A) ) > > > > Cheers > > > > 'Coding is an art'- 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 algoge...@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] BST Question
HI A BST is given you need to print all the negative numbers. Sol: Inorder traversal will work. but i want to ignore the right sub trees based on the value at the root. (i.e efficient sol) -- Regards, C. Narsimha Raju MS, IIIT Hyderabad. http://research.iiit.ac.in/~narsimha_raju/ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Least fare for a return trip Algorithm
@Amod. Isn't the minimum sum the sum of the minimum cost from A to B and the minimum cost from B to A? What am I missing? Dave On Oct 13, 11:06 pm, Amod wrote: > Hi > > I think I forgot to mention that the SUM of the ROUND trip i.e. A->B->A (sum > = going + returning) should be least. > > Please don't take into account any other thing like time and > availability. > So solution is not that straightforward. > > Its like we have two arrays and we have to return least k sum from the > given arrays where we take one element from the first and one from > second in the sum. > > Cheers > Amod > > On Oct 13, 2:26 pm, Shiyam code_for_life > wrote: > > > > > When a user wants to choose to fly from A to B, suggest the flight > > with lowest fare that's available, here its A1, if A1 is busy then A2 > > and so on > > Repeat the same for B to A. > > > Am I missing something here? > > > Complexity is O( (number of flights from A to B) + number of flights > > from B to A) ) > > > Cheers > > > 'Coding is an art'- 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 algoge...@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: Least fare for a return trip Algorithm
Hi I think I forgot to mention that the SUM of the ROUND trip i.e. A->B- >A (sum = going + returning) should be least. Please don't take into account any other thing like time and availability. So solution is not that straightforward. Its like we have two arrays and we have to return least k sum from the given arrays where we take one element from the first and one from second in the sum. Cheers Amod On Oct 13, 2:26 pm, Shiyam code_for_life wrote: > When a user wants to choose to fly from A to B, suggest the flight > with lowest fare that's available, here its A1, if A1 is busy then A2 > and so on > Repeat the same for B to A. > > Am I missing something here? > > Complexity is O( (number of flights from A to B) + number of flights > from B to A) ) > > Cheers > > 'Coding is an art' -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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 problem BOTTOM
The simplest approach is probably to compute the transitive closure of the graph. Then look at each pair (row k, column k) of the closure. When they're equal, k is an element of bottom. All this requires O(n^3). Since n <= 5000, this should take a few seconds in the worst case. On Oct 13, 12:52 pm, praba karan wrote: > spoj.pl/problems/BOTTOM > > my algo for this prob goes by this way..will this work correctly? > > 1)first make a bfs from an arbitrary node and store the nodes visited > in order in an array. > > 2)the node that is visited at the end of the BFS in the 1st bfs is now > taken as the root and then make a BFS from this node and store the > nodes visited in order in an array. > > 3)reverse the array in step 2 > > 4)find the Longest Common Subsequence between the arrays in step 1 and > step 3 > > 5)if any one of the array is empty,then all the other nodes in the > other array sud b printed. > > will this logic work? > > any other ideas are welcomed... > > praba... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Maximum set of Collinear points
@Asquare. Yes, you are wrong. If the slope of the line AB equals the slope of the line AC, then points A, B, and C are collinear. One way to look at it is that because AB and AC have the same slope, they are parallel (if you can call coincident lines parallel), and they both contain point A. Therefore, they are coincident. Dave On Oct 13, 3:04 pm, Asquare wrote: > @Dave - > > Although what u have posed is correct to an extent but this will also > include cases where the line joining the points are parallel and not > collinear > So we will have to impose a check for one of the points involved > in every two same slopes to be coincident. > > Do correct me if i am wrong.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: DP
The example I did by hand was { 3,7,2,1 }. Here the answer is 8. My code I ran on 2,5,7,1,8,9. This produces 18 if you run it. See http://codepad.org/FW0Y4rL7 . Both are correct as far as I can see. Sorry for the confusion. On Oct 9, 12:56 am, Lego Haryanto wrote: > I think this pasted code is incorrect ... answer for { 2, 5, 7, 1, 8, 9 } > should be 18, right? > > > > > > On Thu, Oct 7, 2010 at 10:53 PM, Anand wrote: > > Using standard Dynamic Programing logic: > >http://codepad.org/IwBTor4F > > > On Thu, Oct 7, 2010 at 8:43 PM, Gene wrote: > > >> Nice problem. Let N_1, N_2, ... N_n be the values of the N notes. > >> Let F(i,j) be the maximum possible score the current player can get > >> using only notes i through j. Then > > >> F(i,j) = sum_{k = i to j}N_k - min( F(i+1, j), F(i, j-1) ) > > >> This is saying that the current player always makes the choice that > >> minimizes B the best score that the other player can achieve. When we > >> know that choice, the best _we_ can do is the sum of all the available > >> notes minus B. > > >> The base case is F(k,k) = N_k, and we are unconcerned with F(i,j) > >> where i > j. > > >> For example, suppose we have notes 3 7 2 1 . The answer we want is > >> F(1,4). > > >> Initially we have > >> F(1,1) = 3 > >> F(2,2) = 7 > >> F(3,3) = 2 > >> F(4,4) = 1 > > >> Now we can compute > >> F(1,2) = 10 - min(F(2,2), F(1,1)) = 10 - min(7,3) = 7 (pick N_1=7). > >> F(2,3) = 9 - min(F(3,3), F(2,2)) = 9 - min(2,7) = 7 (pick N_2=7). > >> F(3,4) = 3 - min(F(4,4), F(3,3)) = 3 - min(1,2) = 2 (pick N_3=2). > >> F(1,3) = 12 - min(F(2,3), F(1,2)) = 12 - min(7,7) = 5 (don't care). > >> F(2,4) = 10 - min(F(3,4), F(2,3)) = 10 - min(2,7) = 8 (pick N_2=7). > >> F(1,4) = 13 - min(F(2,4), F(1,3)) = 13 - min(8,5) = 8 (pick N_4=1). > > >> On Oct 7, 8:14 pm, Anand wrote: > >> > Given a row of notes (with specified values), two players play a game. > >> At > >> > each turn, any player can pick a note from any of the two ends. How will > >> the > >> > first player maximize his score? Both players will play optimally. > > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > >> To post to this group, send email to algoge...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com >> .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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Maximum set of Collinear points
There are only O(n^2) pairs of points. So compute the normalized coefficients (A,B,C) of the line passing through each pair: Ax + By + C = 0 where sqrt(A^2 + B^2) = 1 and either A>0 or (A=0 and B = 1). This is simple algebra. Now you can hash all the points in the pairs using their (A,B,C) triples as keys. This will give you equivalence classes of points. The largest equivalence class is your answer, and you'll have it in O(n^2) time. The interesting thing is to consider whether it can be done in less than O(n^2)... On Oct 13, 5:52 am, Mridul Malpani wrote: > There are n points in 2d space.we have their (x,y) co-ordinates. you > have to find the maximum set of points that are colinear? > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or > n^2). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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] spoj-party problem
Replace if(x>=y) { m[i][j]=x; //cost=wt[i]; ans[i][j]=wt[i]+ans[i-1][j-wt[i]]; } with if(x>y){ m[i][j] = x; ans[i][j] = wt[i]+ans[i-1][j-wt[i]]; }else if(x==y){ m[i][j] = x; ans[i][j] = min(ans[i-1][j] , ans[i-1][j-wt[i]]+wt[i]); } try it On Wed, Oct 13, 2010 at 9:35 AM, keyankarthi wrote: > hey guys.., i tried solving this problem > http://www.spoj.pl/problems/PARTY/ > i get answer for the test cases that i try.. getting WA in the judge.. > can anyone help me out here.. my code is as follows.. > > #include > #include > using namespace std; > > int m[150][150],v[150],wt[150],ans[150][150]; > void dp(int weight,int n) > { >int i,j,x,y,anscount=0; >for(i=0;i<=weight;i++) >m[0][i]=0; >for(i=1;i<=n;i++) >ans[0][i]=0; > >for(i=1;i<=n;i++) >{ >for(j=0;j<=weight;j++) >{ >if(wt[i]<=j) >{ >x=(v[i]+m[i-1][j-wt[i]]); >y=(m[i-1][j]); >if(x>=y) >{ >m[i][j]=x; >//cost=wt[i]; >ans[i][j]=wt[i]+ans[i-1][j-wt[i]]; >} >else >{ >m[i][j]=y; >ans[i][j]=ans[i-1][j]; >} >} >else >{ >m[i][j]=m[i-1][j]; >ans[i][j]=ans[i-1][j]; >} >} >} >printf("%d %d",ans[n][weight],m[n][weight]); > } > > int main() > { > >int weight,no,i,j; >while(1) >{ >scanf("%d %d",&weight,&no); >if(!weight && !no) >break; >for(i=1;i<=no;i++) >scanf("%d %d",&wt[i],&v[i]); >dp(weight,no); >} > } > > thanks, > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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. > > -- Devendra Pratap Singh B.Tech (IT) IIIT - Allahabad -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Maximum set of Collinear points
@Dave - Although what u have posed is correct to an extent but this will also include cases where the line joining the points are parallel and not collinear So we will have to impose a check for one of the points involved in every two same slopes to be coincident. Do correct me if i am wrong.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: first unrepeated char
Thanks :) This is definitely a much better option than O(mn) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: plz explain output
@Nidhi - I guess thats correct.. but am still not 100% sure about how the explanation goes.. Actually printf() is a variable argument function and so the acceptance of a value of a data type depends on the way it is defined in the library.. and since %f if encountered in the string must be replaced by a float value (as defined since it can be anything - VARIABLE) so the function (as we see the way it works) expects a float value.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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] Modify Queue Data Structure which returns min in O(1) time.
Similar question was posted sometime back but the DS in question was stack. please look in to the existing topics to look for the solution to your problem. On Thu, Oct 14, 2010 at 12:13 AM, rahul wrote: > it look like a priority queue type of DS to me > well min-heap is another solution,which do the heap process at each > insertion and deletion,so that min element stay the root position. > > comments invited. > > regards. > > > On Wed, Oct 13, 2010 at 11:52 PM, malli wrote: > >> A queue data structure has functions enqueue(int x) ( inserts element >> in right end), dequeue() ( deletes element from left end) functions. >> These operations take O(1) time. Modify this queue data structure, so >> that it supports findmin() which returns minimum element of stack 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 algoge...@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 algoge...@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 algoge...@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] Modify Queue Data Structure which returns min in O(1) time.
it look like a priority queue type of DS to me. well min-heap is another solution,which do the heap process at each insertion and deletion,so that min element stay the root position. comments invited. regards. On Wed, Oct 13, 2010 at 11:52 PM, malli wrote: > A queue data structure has functions enqueue(int x) ( inserts element > in right end), dequeue() ( deletes element from left end) functions. > These operations take O(1) time. Modify this queue data structure, so > that it supports findmin() which returns minimum element of stack 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 algoge...@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 algoge...@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] Modify Queue Data Structure which returns min in O(1) time.
A queue data structure has functions enqueue(int x) ( inserts element in right end), dequeue() ( deletes element from left end) functions. These operations take O(1) time. Modify this queue data structure, so that it supports findmin() which returns minimum element of stack 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 algoge...@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 problem BOTTOM
I didnt understand the above solution, but I have a bad complexity solution. Make an nXn boolean adjacency matrix. Run transitivy closure on the matrix. For every node w, check if for all v E V, w->v=> v->w On Oct 13, 9:52 pm, praba karan wrote: > spoj.pl/problems/BOTTOM > > my algo for this prob goes by this way..will this work correctly? > > 1)first make a bfs from an arbitrary node and store the nodes visited > in order in an array. > > 2)the node that is visited at the end of the BFS in the 1st bfs is now > taken as the root and then make a BFS from this node and store the > nodes visited in order in an array. > > 3)reverse the array in step 2 > > 4)find the Longest Common Subsequence between the arrays in step 1 and > step 3 > > 5)if any one of the array is empty,then all the other nodes in the > other array sud b printed. > > will this logic work? > > any other ideas are welcomed... > > praba... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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] spoj problem BOTTOM
spoj.pl/problems/BOTTOM my algo for this prob goes by this way..will this work correctly? 1)first make a bfs from an arbitrary node and store the nodes visited in order in an array. 2)the node that is visited at the end of the BFS in the 1st bfs is now taken as the root and then make a BFS from this node and store the nodes visited in order in an array. 3)reverse the array in step 2 4)find the Longest Common Subsequence between the arrays in step 1 and step 3 5)if any one of the array is empty,then all the other nodes in the other array sud b printed. will this logic work? any other ideas are welcomed... praba... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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] regarding output
p[b] is equivalent to *(p+b) here p is converted to the void pointer pointing to address location 0x0003 then the pointer value is added by the offset b which is 8 here . 8+3 giving 11 this is one of the method of finding the sum of two numbers without using addition operator -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: sorted array
let the numbers be i1,i2,i3i8 Array A has to contain 5 sorted numbers.. So basically u have to make 5 choices among given 8. Standard formula of it is 8C5 (8!/(3! * 5!)). After creating array A there will be 3 elements left which will suffice to create array B (no choice is left in this case so it will be 1C1=1). No shuffling among the numbers in array A and B will be there as numbers have to be sorted and so only one possible arrangment is possible to maintain the array sorted. so total number of arrangements will be 8C5 * 1C1 = 8C5= 56. On Wed, Oct 13, 2010 at 5:25 PM, Divya Jain wrote: > ignore the above post of mine > @ shiyam > u r doing wrong. we hv been the size of both array b and c which is 5 n 3 > respectively > > @ AlgoSAu > can u please explain ur method? > > > On 13 October 2010 17:23, Divya Jain wrote: > >> @above >> can u plz explain hw did u apply this formula? >> >> >> On 13 October 2010 16:14, Shiyam code_for_life >> wrote: >> >>> Lets say 8 integers are 1 to 8 >>> >>> So first way array can be split is 1,7 >>> >>> 1st array can have one among 8 integers so in 8 ways and 2nd array has >>> just one arrangement of other integers in sorted manner and same goes >>> on for other ways to split the array. >>> >>> Whats wrong here? >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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: remove redundantt parenthesis
how can once evaluate a+b, when a and b are just variables.. Its not necessary that the expression contains all the constants. On Wed, Oct 13, 2010 at 10:07 AM, Shiyam code_for_life < mailshyamh...@gmail.com> wrote: > For every pair of braces, > Evaluate the expression within the outer braces of current braces > under consideration > (1)With current braces > (2)Without current braces > > If both are the same, then you can drop the current braces that its > redundant. > > P.S for outer most braces, evaluate the entire expression with and > without it > > Ex: > (a+[b+c]) > Here to check if square braces are redundant > (1)Evaluate (a+[b+c]) and (a+b+c) > (2)If both are equal then drop the braces so expression can be reduced > as (a+b+c) > (3)Else the braces are required so they remain as (a+[b+c]) > > Cheers > > 'Coding is an art and I'm one of the finest of them' > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: sorted array
ignore the above post of mine @ shiyam u r doing wrong. we hv been the size of both array b and c which is 5 n 3 respectively @ AlgoSAu can u please explain ur method? On 13 October 2010 17:23, Divya Jain wrote: > @above > can u plz explain hw did u apply this formula? > > > On 13 October 2010 16:14, Shiyam code_for_life wrote: > >> Lets say 8 integers are 1 to 8 >> >> So first way array can be split is 1,7 >> >> 1st array can have one among 8 integers so in 8 ways and 2nd array has >> just one arrangement of other integers in sorted manner and same goes >> on for other ways to split the array. >> >> Whats wrong here? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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 algoge...@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: sorted array
@above can u plz explain hw did u apply this formula? On 13 October 2010 16:14, Shiyam code_for_life wrote: > Lets say 8 integers are 1 to 8 > > So first way array can be split is 1,7 > > 1st array can have one among 8 integers so in 8 ways and 2nd array has > just one arrangement of other integers in sorted manner and same goes > on for other ways to split the array. > > Whats wrong here? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: Least fare for a return trip Algorithm
Although no inputs are given on flight timing (date and time) front but that is one more factor that should be considered while scheduling the cheapest round trip journey as it happens on travel sites normally On Wed, Oct 13, 2010 at 2:56 PM, Shiyam code_for_life < mailshyamh...@gmail.com> wrote: > When a user wants to choose to fly from A to B, suggest the flight > with lowest fare that's available, here its A1, if A1 is busy then A2 > and so on > Repeat the same for B to A. > > Am I missing something here? > > Complexity is O( (number of flights from A to B) + number of flights > from B to A) ) > > Cheers > > 'Coding is an art' > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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] plz explain output
How is the link you gave related to the output question here?? On Wed, Oct 13, 2010 at 7:20 PM, dinesh bansal wrote: > check http://en.wikipedia.org/wiki/NaN > > On Sat, Oct 9, 2010 at 6:15 PM, ankush wrote: > >> #include >> void main() >> { >>int x; >>float t; >>scanf("%f",&t); >>printf("%f\n",t); >>x=90; >>printf("%f\n",x); >>{ >>x=1; >>printf("%f\n",x); >>{ >>x=30; >>printf("%d\n",x); >>} >>printf("%f\n",x); >>} >>x=9; >>printf("%f\n",x); >> } >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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. >> >> > > > -- > Dinesh Bansal > The Law of Win says, "Let's not do it your way or my way; let's do it the > best way." > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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] C puzzle
No const char * p is a pointer to a constant string, and is not itselves a constant pointer! On Sun, Oct 10, 2010 at 11:41 AM, Harshal wrote: > @Soumya > Typedef merely adds a new name for some existing type, here for char* type > in your code. > So instead you should write *typedef const char* char*p rather than *typedef > char* char*p. bcoz you want new name for the whoole thinge (const char*), > not just char*. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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] plz explain output
check http://en.wikipedia.org/wiki/NaN On Sat, Oct 9, 2010 at 6:15 PM, ankush wrote: > #include > void main() > { >int x; >float t; >scanf("%f",&t); >printf("%f\n",t); >x=90; >printf("%f\n",x); >{ >x=1; >printf("%f\n",x); >{ >x=30; >printf("%d\n",x); >} >printf("%f\n",x); >} >x=9; >printf("%f\n",x); > } > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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. > > -- Dinesh Bansal The Law of Win says, "Let's not do it your way or my way; let's do it the best way." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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] spoj-party problem
hey guys.., i tried solving this problem http://www.spoj.pl/problems/PARTY/ i get answer for the test cases that i try.. getting WA in the judge.. can anyone help me out here.. my code is as follows.. #include #include using namespace std; int m[150][150],v[150],wt[150],ans[150][150]; void dp(int weight,int n) { int i,j,x,y,anscount=0; for(i=0;i<=weight;i++) m[0][i]=0; for(i=1;i<=n;i++) ans[0][i]=0; for(i=1;i<=n;i++) { for(j=0;j<=weight;j++) { if(wt[i]<=j) { x=(v[i]+m[i-1][j-wt[i]]); y=(m[i-1][j]); if(x>=y) { m[i][j]=x; //cost=wt[i]; ans[i][j]=wt[i]+ans[i-1][j-wt[i]]; } else { m[i][j]=y; ans[i][j]=ans[i-1][j]; } } else { m[i][j]=m[i-1][j]; ans[i][j]=ans[i-1][j]; } } } printf("%d %d",ans[n][weight],m[n][weight]); } int main() { int weight,no,i,j; while(1) { scanf("%d %d",&weight,&no); if(!weight && !no) break; for(i=1;i<=no;i++) scanf("%d %d",&wt[i],&v[i]); dp(weight,no); } } thanks, -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Maximum set of Collinear points
@Sudheer: We don't need to do any extra work to eliminate it. It is a smaller set than the previous max found, so we don't have to consider it further. The problem says "the maximum set," and doesn't specify what to do in the case of ties. Since apparently one answer is expected, I assume that it means "a maximal set," so you can ignore any set that is not larger than the current max. Dave On Oct 13, 6:41 am, sudheer babu wrote: > suppose after caliculating slopes for ist point we formed set points(n=9) > whose slopes are eequal are > {1,2,3,4},{1,5,6,7,9},{1,}. > now for second point we will definitely get 1 set{1,2,3,4}and some other and > we have to eliminate this set > it takes some more time > > > > On Wed, Oct 13, 2010 at 5:52 PM, Dave wrote: > > @Mridul: For each point i, find the slope to every other point j and > > look for duplicates. Duplicates can be found by sorting the slopes and > > comparing adjacent values. Point i is collinear with the points in > > each set of duplicates. Keep track of the maximal set as you go. > > > For each i, you have n-1 slopes to calculate and sort and compare. > > Therefore, using a log n sort, the complexity of the algorithm is > > O(n^2 log n). > > > Dave > > > On Oct 13, 4:52 am, Mridul Malpani wrote: > > > There are n points in 2d space.we have their (x,y) co-ordinates. you > > > have to find the maximum set of points that are colinear? > > > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or > > > n^2). > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@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 - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Maximum size binary search tree
in the gopinath solution we need to maintain another array and it contains the maximum bst constructed so far... when len is updated this array also updated to contain the present queue values... On Aug 15, 11:57 am, Ankit Singh wrote: > Space complexity- O(n), Time - O(n2). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Maximum set of Collinear points
suppose after caliculating slopes for ist point we formed set points(n=9) whose slopes are eequal are {1,2,3,4},{1,5,6,7,9},{1,}. now for second point we will definitely get 1 set{1,2,3,4}and some other and we have to eliminate this set it takes some more time On Wed, Oct 13, 2010 at 5:52 PM, Dave wrote: > @Mridul: For each point i, find the slope to every other point j and > look for duplicates. Duplicates can be found by sorting the slopes and > comparing adjacent values. Point i is collinear with the points in > each set of duplicates. Keep track of the maximal set as you go. > > For each i, you have n-1 slopes to calculate and sort and compare. > Therefore, using a log n sort, the complexity of the algorithm is > O(n^2 log n). > > Dave > > On Oct 13, 4:52 am, Mridul Malpani wrote: > > There are n points in 2d space.we have their (x,y) co-ordinates. you > > have to find the maximum set of points that are colinear? > > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or > > n^2). > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: Maximum set of Collinear points
@Mridul: For each point i, find the slope to every other point j and look for duplicates. Duplicates can be found by sorting the slopes and comparing adjacent values. Point i is collinear with the points in each set of duplicates. Keep track of the maximal set as you go. For each i, you have n-1 slopes to calculate and sort and compare. Therefore, using a log n sort, the complexity of the algorithm is O(n^2 log n). Dave On Oct 13, 4:52 am, Mridul Malpani wrote: > There are n points in 2d space.we have their (x,y) co-ordinates. you > have to find the maximum set of points that are colinear? > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or > n^2). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: output for optimal binary search tree
Can you be clear here? There is no difference in printing a binary tree whether its optimized or not! Or am I missing something here? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: sorted array
Lets say 8 integers are 1 to 8 So first way array can be split is 1,7 1st array can have one among 8 integers so in 8 ways and 2nd array has just one arrangement of other integers in sorted manner and same goes on for other ways to split the array. Whats wrong here? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Smallest window of K[] in N[]. Best order solution
@ ankit agarwal, you are right. thanx man. On Oct 13, 11:37 am, prodigy <1abhishekshu...@gmail.com> wrote: > Let I,Q be input array,query array respectively. > > 1. Sort query array. O(klogk) > 2. Allocate an array A of size N. > 3. Fill A such that A[i]= position of Q[i] in I, -1 if not present in > I. O(nlogk) > 4. Allocate an array B of size k with all elements initiated to -1. > 5. for(counter=0,i=0,counter { > if(B[i]==-1) > counter++; > if(A[i]!=-1) > B[A[i]] = i > } > 6. Build min-heap of B.(use an auxiliary array C to keep track of > position of last occurence of an element of Q in min-heap B.) > 7. for(diff=i-B[1] ; i if(A[i]!=-1) > B[C[A[i]] = i > //percolate up or down if needed > diff=max(diff,i-B[1]); > > 8. print diff > > On Oct 7, 1:20 pm, RAHUL KUJUR wrote: > > > > > @prodigy: how is it coming O(nlogk) can u explain??? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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] Maximum set of Collinear points
There are n points in 2d space.we have their (x,y) co-ordinates. you have to find the maximum set of points that are colinear? I have used brute force, time =O(n^4). he wants a solution in O(n^3 or n^2). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Least fare for a return trip Algorithm
When a user wants to choose to fly from A to B, suggest the flight with lowest fare that's available, here its A1, if A1 is busy then A2 and so on Repeat the same for B to A. Am I missing something here? Complexity is O( (number of flights from A to B) + number of flights from B to A) ) Cheers 'Coding is an art' -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: first unrepeated char
(1) Take a hash table of all characters (2) Initialize them to 0 (3) For each character (3.1) If hash[character] == 0 then hash[character]=current loop index #Appearing for first time so store index at which it appears (3.2) elsif hash[character] > 0 then hash[character]=-1 #Already occurred so reject it (4) Loop through the hash table, the element with lowest positive value is the first unrepeated character Time complexity : O(n) Tips: If hash[character] is 0 then character has never occurred if hash[character] is > 0 then character has occurred once at position which is stored as hash value if hash[character] is -1 then it has repeated. 'Coding is an art' -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: first unrepeated char
(1) Take a hash table of all characters (2) Initialize them to 0 (3) For each character (3.1) If hash[character] == 0 then hash[character]=current loop index #Appearing for first time so store index at which it appears (3.2) elsif hash[character] > 0 then hash[character]=-1 #Already occurred so reject it (4) Loop through the hash table, the element with lowest positive value is the first unrepeated character Time complexity : O(n) Tips: If hash[character] is 0 then character has never occurred if hash[character] is > 0 then character has occurred once at position which is stored as hash value if hash[character] is -1 then it has repeated. 'Coding is an art' -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: sorted array
Read the question again..only 3rd case you have mentioned needs t On Wed, Oct 13, 2010 at 12:58 PM, Shiyam code_for_life < mailshyamh...@gmail.com> wrote: > First lets look at how many ways the array can be split > (1) 1,7 > (2) 2,6o be considered here... > (3) 3,5 > (4) 4,4 > > Now how many combinations in each > > 1,7 => 8 combinations for first array > 2,6 => 8*7 combinations for first array > 3,5 => 8*7*6 combinations for first array > 4,4 => 8*7*6*5 combinations for first array > > so its the sum (8) + (8*7) + (8*7*6) + (8*7*6*5) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: sorted array
First lets look at how many ways the array can be split (1) 1,7 (2) 2,6 (3) 3,5 (4) 4,4 Now how many combinations in each 1,7 => 8 combinations for first array 2,6 => 8*7 combinations for first array 3,5 => 8*7*6 combinations for first array 4,4 => 8*7*6*5 combinations for first array so its the sum (8) + (8*7) + (8*7*6) + (8*7*6*5) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Bee Maja spoj
Ruby simple code(ruby is so damn readable) pos[0]=x pos[1]=y just pass the value u wanna convert to translate function, logic is quite clean :) step=10 print translate(step) def move(pos,direction) case direction when :down pos[1]+=1 when :left pos[0]-=1 when :up pos[1]-=1 when :right pos[0]+=1 when :diagup pos[0],pos[1]=pos[0]+1,pos[1]-1 when :diagdown pos[0],pos[1]=pos[0]-1,pos[1]+1 end end def translate(steps) guide=[:left,:up,:diagup,:right,:down,:down,:diagdown] pos=[0,0] move(pos,:down) (steps-1).times{|i| move(pos,guide[i%7]) } return pos end -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.