[algogeeks] Re: a question about pseudo random integers
Hi Gene, and thanks for your reply! Yes, I had thought of something like that. However, it seems sort of cumbersome to me: I guess I would want to split the 32-bit integer by means of 32 bitwise ands... Or probably there's a smarter way. Anyway, if the random integers come in bunches of 16 I'd have to rewrite some code (I do not know in advance how many integer I need to complete my task). First thing that comes to mind is adding a counter for the spent random integers and generating a new batch of them when all of them have been used. Nothing too difficult, althoug a bit cumbersome. And I'm wondering whether I'd end up with a significant increase in speed. I'll make some experiment Thanks again F On Dec 8, 3:14 am, Gene gene.ress...@gmail.com wrote: Well for one thing if your rng is very good you can use a single 32- bit integer to generate 16 numbers in [0..3]. -- 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] The best multiply matrix algorithms ?
What is best multiply matrix algorithm for: -multiply a n x n matrix by another n x n matrix -multiply a m x n matrix by a n x p matrix I need a best performance cpu algorithm. Note: it can use a parallel programming concept. Thankfully. Luciano. -- 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] program for evaluation of remainders
Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance -- 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] Largest rectangle in a binary matrix
Hi Given a binary matrix containing 0s and 1s as elements in it. I need to find efficiently the largest rectangle containing all 1s. For example: in case of 4x4 matrix 1 0 0 1 0 1 1 0 1 1 1 0 0 1 1 1 The largest rectangle is 1 1 1 1 1 1 -Prims -- 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] Largest rectangle in a binary matrix
Hi, Solution is available at http://geeksforgeeks.org/?p=6257 -- 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] Largest rectangle in a binary matrix
Use kadane's 3D algorithm -- 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: Largest rectangle in a binary matrix
Hello Gobind The link contains the solution for finding the largest square in a binary matrix which is not valid in case of largest rectangle. -Prims On Dec 8, 6:38 pm, GOBIND KUMAR gobind@gmail.com wrote: Hi, Solution is available athttp://geeksforgeeks.org/?p=6257 -- 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: program for evaluation of remainders
@Ankit: Try this: x = 0; for( i = N ; i 0 ; --i ) x = (i * x + i) % n; Dave On Dec 8, 7:19 am, ankit sablok ankit4...@gmail.com wrote: Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance -- 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: Largest rectangle in a binary matrix
ravi is right .. http://alexeigor.wikidot.com/kadane On Wed, Dec 8, 2010 at 7:31 PM, Prims topcode...@gmail.com wrote: Hello Gobind The link contains the solution for finding the largest square in a binary matrix which is not valid in case of largest rectangle. -Prims On Dec 8, 6:38 pm, GOBIND KUMAR gobind@gmail.com wrote: Hi, Solution is available athttp://geeksforgeeks.org/?p=6257 -- 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.comalgogeeks%2bunsubscr...@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: program for evaluation of remainders
rem=1; for(j=3;j=N+1;j++) rem=(rem*j)%n; return rem; -- 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: Amazon Interview Question
@gene: can you do dry run a test case: a[0]-a[n-1] 0 1 2 31 34 135 and if u c On Tue, Dec 7, 2010 at 8:55 AM, Gene gene.ress...@gmail.com wrote: I should have mentioned that this problem only makes sense if the array values must be unique. On Dec 6, 8:20 pm, Gene gene.ress...@gmail.com wrote: You guys are working too hard. Think about the sequence of numbers [ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this sequence to find the number of zeros. If you think about it for a while, you will see that this sequence is non-decreasing. It must be a segment of zero or more negative numbers followed by a segment of zero or more zeros followed by a segment of zero or more positive numbers. Therefore you can easily use two binary searches to find the index of the leftmost and rightmost zeros. This identifies all the elements where A[i]=i in O(2 log n) = O(log n) time. Of course if the searches fail, you have no elements at all where A[i]=i. On Dec 5, 9:46 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: @Divesh I have updated my algo and Array A[1,2,3.n] is sorted with unique elements.CALL FIND_EQUAL(A,1,n) int FIND_EQUAL(A,start,end) 1.Go to the middle element 2. If A[mid]mid) 3. if(start==mid) 4 return mid-1; 5return FIND_EQUAL(A,1,mid-1); 6 if(A[mid]=mid) 7if(mid==end) 8 return mid; 9return FIND_EQUAL(A,mid+1,end); On Sun, Dec 5, 2010 at 7:36 PM, coolfrog$ dixit.coolfrog.div...@gmail.comwrote: @Nikhil run you algo .. on test case index - 1 2 3 4 5 value - 1 2 3 4 5 ouput is mid+1= 3+1=4 but it should be 5... correct me if i am wrong... and u have assumed all are positive, hence base index should be 1 On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: If All the elements are unique and sorted in ascending order then we can design an algorithm for O(lgn) and all nos are positive. Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements] FIND_EQUAL(A,start,end) 1.Go to the middle element 2.If A[mid]==mid) return mid+1; if(A[mid]mid) then FIND_EQUAL(A,start,mid-1) else FIND_EQUAL(A,mid+1,end) Runs in O(lgn) On Sun, Dec 5, 2010 at 12:20 PM, jai gupta sayhelloto...@gmail.com wrote: Any algorithm must in worst case lead to O(n) if the elements are not unique. Take the case: 1 2 3 4 5 6 as all the elements satisfy the condition of of key==index . we must go someway to each element. Hence O(n). This may be somehow made less if the element are given to be unique by using heap. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Divesh* (¨`·.·´¨) Always `·.¸(¨`·.·´¨ ) Keep (¨`·.·´¨)¸.·´Smiling! `·.¸.·´ Life can give u 100's of reason 2cry,but u can give life 1000's of reasons 2Smile -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// beta.freshersworld.com/communitie... -- 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.
[algogeeks] qsort
how can i use qsort a structure. please give me the code if possibe -- 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] valid paranthesis
Hi, You can use Recursion logic of Catalan Numbers. M. Vamsee -- 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: convert binary matrix to zero matrix
As Amir pointed out: convert the first row and first column to all zeros In details: 1. choose operations on first row and first column to make up-left element 0. * There are 2 cases, 2 choices for each case: 1. If the up-left element is 0, then 1. toggle both first row and first column, or 2. leave both untouched. 2. If the up-left element is 1, then 3. toggle first row, or 4. toggle first column 2. for each 1 on the first row, toggle the corresponding column, to change first row to all 0s. 3. for each 1 on the first column, toggle the corresponding row, to change first column to all 0s. After above 3 steps, if there are still some 1's, no solution is possible. Otherwise, compare the 2 choice, and choose the minimum steps. --- In fact, we can directly calculate the number of steps in choice a)-d): 1. number of 0's on the first row and first column 2. number of 1's on the first row and first column 3. number of 0's on the first row + number of 1's on the first column 4. number of 1's on the first row + number of 0's on the first column And if we denote the j'th element on i'th row as M[i,j] (start from 1), then the problem have valid solution if and only if: for each element M[i,j], M[1,1]+M[1,j]+M[i,1]+M[i,j] is even. On 2010-12-7 22:59, Prims wrote: Hello Rajan Suppose we have the following matrix 1 1 0 0 If a toggle operation performed on first row, it will change all 1s to 0s and 0s to 1s which result in the followig matrix 0 0 0 0 It is zero matrix and the result. Similarly if a toggle operation is performed on column, it will change all 1s to 0s and 0s to 1s in that particular column. Say you have a function toggle(int , Type) which does the toggle operation. where number is the number of row or column Type can be of Type.Row or Type.Column. Hope it is clear -Prims On Dec 7, 5:33 pm, rajan goswamirajan.goswam...@gmail.com wrote: @Prims Can you please elaborate the problem in detail... What do you mean by toggling row and column... 1 Interchanging a row with some column ? 2 Changing 0s to 1s and 1s to 0s of that row ? or Some thing else ? In both options mentioned above .. no of 1s present in a matrix can not be changed to 0s in any ways ... Please explain the step that can be performed on given matrix. regards, Rajan. On Mon, Dec 6, 2010 at 11:55 PM, Primstopcode...@gmail.com wrote: Amir Could you please explain with an example in detail? On Dec 6, 7:02 pm, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: actually a greedy approach for this problem exists: just convert the first row and first column to all zeros if after this step matrix is not a complete zero matrix then it's impossible to make it On Sun, Dec 5, 2010 at 9:10 AM, Primstopcode...@gmail.com wrote: How do i convert a binary matrix(containing only 0s and 1s) to a complete zero matrix? Only operations allowed are u can toggle a whole row or a whole column. The conversion has to be done in minimum number of steps (a step is defined as toggling a whole row or whole column -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Longest interval with maximum sum
@jai : since sum of all values in C is between -n and n the last step can be done in O(n) time and O(n) space On Sun, Dec 5, 2010 at 12:44 PM, jai gupta sayhelloto...@gmail.com wrote: @fenghuang: the last step will take O(n logn ) . Or there is some better 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.comalgogeeks%2bunsubscr...@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] program for evaluation of remainders
Let me try. Any thing involving n would leave no remainder. so (1 + 2 ! + ... + n ! + + N !) mod n = (1 + 2 ! + ... + (n-1)! ) mod n This should be computed from a loop. I don't know how to reduce it further. Ashim. On Wed, Dec 8, 2010 at 6:49 PM, ankit sablok ankit4...@gmail.com wrote: Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance -- 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.comalgogeeks%2bunsubscr...@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] program for evaluation of remainders
@Ashim with a check that N =n N can also be less than n On Wed, Dec 8, 2010 at 6:57 PM, Ashim Kapoor ashimkap...@gmail.com wrote: Let me try. Any thing involving n would leave no remainder. so (1 + 2 ! + ... + n ! + + N !) mod n = (1 + 2 ! + ... + (n-1)! ) mod n This should be computed from a loop. I don't know how to reduce it further. Ashim. On Wed, Dec 8, 2010 at 6:49 PM, ankit sablok ankit4...@gmail.com wrote: Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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: program for evaluation of remainders
Using this idea makes my solution into x = 0; for( i = (n N ? n : N) ; i 0 ; --i ) x = (i * x + i) % n; Dave On Dec 8, 7:27 am, Ashim Kapoor ashimkap...@gmail.com wrote: Let me try. Any thing involving n would leave no remainder. so (1 + 2 ! + ... + n ! + + N !) mod n = (1 + 2 ! + ... + (n-1)! ) mod n This should be computed from a loop. I don't know how to reduce it further. Ashim. On Wed, Dec 8, 2010 at 6:49 PM, ankit sablok ankit4...@gmail.com wrote: Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance -- 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: k nearest points
@coolfrog the question never asked u to find thm in order of thier distances. Correct me if i m wrong! find the distances in O(n) now using the partitioning process of quicksort. Dividing the array into two parts: Now if the Length of the first part is less than or equal to i we have to now make our search into one of the subarrays In average: T(n)=T(n/2)+O(n) which satisfies T(n)=O(n) though in worst case this algorithm can take u to O(n^2) but in average case it takes u to O(n) -- 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] help me reduce the time limit
please help mewritea program for this problem to reduce the time limit http://www.codechef.com/problems/FLIPCOIN/ thnx in advance i have ben banging my head on this for a full day -- 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: program for evaluation of remainders
@ all the authors thanx for the suggestions actually wt i know about the problem is i think we can solve the problem mathematically if we know about congruences for instance if N=100 1! + 2! + . + 100! and n=12 we find that 4!mod24=0 hence the above equation reduces to the (1!+2!+3!)mod 12 =9 hence the answer is 9 so can anyone write a program for this logic On Dec 8, 6:19 pm, ankit sablok ankit4...@gmail.com wrote: Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance -- 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: k nearest points
I like Your algorithm; it's the same as I think. -- 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] qsort
you mean the function qsort() in crt? here is a sample struct foostruct{ int key; int value1; int value2; }; int compare(const void* a1, const void* a2){ return ((foostruct*)a1)-key - ((const foostruct*)a2)-key; } void bar(){ foostruct s[] ={ {3, 2, 3}, {5, 2, 1}, {2, 6, 5} }; qsort(s, sizeof(s)/sizeof(s[0]), sizeof(s[0]), compare); } Thank U! On Tue, Dec 7, 2010 at 3:30 AM, ANUJ KUMAR kumar.anuj...@gmail.com wrote: how can i use qsort a structure. please give me the code if possibe -- 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.comalgogeeks%2bunsubscr...@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] help me reduce the time limit
see TC forums : On Wed, Dec 8, 2010 at 10:44 PM, ankit sablok ankit4...@gmail.com wrote: please help mewritea program for this problem to reduce the time limit http://www.codechef.com/problems/FLIPCOIN/ thnx in advance i have ben banging my head on this for a full day -- 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: program for evaluation of remainders
@Ankit: So how does that work with, e.g., N = n = 997? I.e., what is the calculation? Dave On Dec 8, 11:33 am, ankit sablok ankit4...@gmail.com wrote: @ all the authors thanx for the suggestions actually wt i know about the problem is i think we can solve the problem mathematically if we know about congruences for instance if N=100 1! + 2! + . + 100! and n=12 we find that 4!mod24=0 hence the above equation reduces to the (1!+2!+3!)mod 12 =9 hence the answer is 9 so can anyone write a program for this logic On Dec 8, 6:19 pm, ankit sablok ankit4...@gmail.com wrote: Q) can anyboy find me the solution to this problem Given an integer N and an another integer n we have to write a program to find the remainder of the following problems (1! + 2! + 3! + 4! + . + N!)mod(n) N=100 n=1000; please help me write a program for this problem thanx in advance- 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.
Re: [algogeeks] The best multiply matrix algorithms ?
Try using Strassen's Matrix Multiplication Algorithm. Regards, Rakib On 12/8/10, Luciano Junior luciano@gmail.com wrote: What is best multiply matrix algorithm for: -multiply a n x n matrix by another n x n matrix -multiply a m x n matrix by a n x p matrix I need a best performance cpu algorithm. Note: it can use a parallel programming concept. Thankfully. Luciano. -- 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] The best multiply matrix algorithms ?
But Strassen's Matrix Multiplication Algorithm take a performance near O(n^2,7)! Is there some other algorithm that take less time ? 2010/12/8 Rakib Ansary Saikot ansaryfantas...@gmail.com: Try using Strassen's Matrix Multiplication Algorithm. Regards, Rakib On 12/8/10, Luciano Junior luciano@gmail.com wrote: What is best multiply matrix algorithm for: -multiply a n x n matrix by another n x n matrix -multiply a m x n matrix by a n x p matrix I need a best performance cpu algorithm. Note: it can use a parallel programming concept. Thankfully. Luciano. -- 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. -- Luciano. -- 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: The best multiply matrix algorithms ?
Are you interested in actual computation speed or are you interested in theoretical big-O speed? If you want the fastest computation for a specific, reasonable-sized problem with no particular structure (i.e., non-sparse), then using the ordinary matrix multiply algorithm that is coded the best will probably beat any theoretically-faster algorithm. You probably will find the fastest matrix-multiplication code in one of the sets of the so-called Basic Linear Algebra Subprograms (BLAS). Check out http://www.netlib.org/blas/faq.html, and especially 5) therein: http://www.netlib.org/blas/faq.html#5. Dave On Dec 8, 6:09 am, Luciano Junior luciano@gmail.com wrote: What is best multiply matrix algorithm for: -multiply a n x n matrix by another n x n matrix -multiply a m x n matrix by a n x p matrix I need a best performance cpu algorithm. Note: it can use a parallel programming concept. Thankfully. Luciano. -- 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: k nearest points
There is an O(n) worst case algorithm for finding the kth smallest element. See http://en.wikipedia.org/wiki/Select_kth_element#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm. Dave On Dec 8, 10:26 am, jai gupta sayhelloto...@gmail.com wrote: @coolfrog the question never asked u to find thm in order of thier distances. Correct me if i m wrong! find the distances in O(n) now using the partitioning process of quicksort. Dividing the array into two parts: Now if the Length of the first part is less than or equal to i we have to now make our search into one of the subarrays In average: T(n)=T(n/2)+O(n) which satisfies T(n)=O(n) though in worst case this algorithm can take u to O(n^2) but in average case it takes u to O(n) -- 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] help me reduce the time limit
#includestdio.h int main() { int arr[11]={0},sum2[1001]={0}; int type[1001]={0};//0 for tails int N,Q,i,j,sum; int a,b,c; scanf(%d,N); scanf(%d,Q); for(i=0;iQ;i++) { scanf(%d%d%d,a,b,c); if(a==0) { j=b; int k=j/100; while(j%100 j=c) { if(arr[j]) { arr[j]=!arr[j]; sum2[k]--; } else{ arr[j]=!arr[j]; sum2[k]++; } j++; } while(j+100=c) { type[j/100]=!type[j/100]; j+=100; } k=j/100; while(j=c) { if(arr[j]) { arr[j]=!arr[j]; sum2[k]--; } else{ arr[j]=!arr[j]; sum2[k]++; } j++; } } else{ sum=0; j=b; int k=j/100; while(j%100 j=c) { sum+=arr[j]^type[k]; j++; } while(j+100=c) { if(type[j/100]) sum+=100-sum2[j/100]; else sum+=sum2[j/100]; j+=100; } k=j/100; while(j=c) { sum+=arr[j]^type[k]; j++; } printf(%d\n,sum); } } return 0; } -- 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] Google questions
explain the 1st one again On Thu, Dec 9, 2010 at 11:16 AM, Anand anandut2...@gmail.com wrote: One of my friend recently had a telephonic interview and he got two question to program. 1. Given a binary search tree. Write a function which takes any given node from the binary tree and a number. Functin has to return the next highest number of the given number from the binary search tree. 2. You have given a structure which has two member, One which stores the time and other stores the function pointer Your function has to call the function stored in the fuction poitner after the time given in the structure elapses. Design that function? let me know in case if the questions are not clear in any 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.comalgogeeks%2bunsubscr...@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] help me find a solution
can anyone suggest me how to go about this problem i m finding it quite tough http://www.codechef.com/problems/TEAMSEL/ thanx in advance -- 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.