seems to be a independent problemu can see maximum subarray problem
On Tue, Nov 1, 2011 at 11:54 PM, atul007 atul.87fri...@gmail.com wrote:
Assume that there are n numbers (some possibly negative) on a circle,
and
we wish to find the maximum contiguous sum along an arc of the circle.
This can be done by kadanes algo..
//suppose n numbers has been stored in array
// i is the intial point
// n is the number of points to be considered in O(n)
int maxsum(int a[], int N,int i,int n)
{
int max=0;
int max_end_ here =0;
int max_so_far=0;
for(int j=i;jN;j++)
{
Hi,
Can anyone what is being done here ? This is a question
http://www.codechef.com/JAN11/problems/SPLIT/ from Codechef. I have read
the editorials, but that didn't help.
http://www.codechef.com/download/Solutions/2011/January/Setter/Split.cpp
--
You received this message because you are
any solutions for this ?
dutch national flag problem could be done in O(n) time and O(1) space by
considering two pointers, but how to do this (reverse dutch national flag
problem) ?
On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal srn...@gmail.com wrote:
Suppose we are given a string
a1 a2 a3 a4 b1 b2 b3 b4
given these two arrays convert them to a1 b1 a2 b2 a3 b3 a4 b4
i can do this in O(1) space and O(n^2)time is there any O(n) solution
for this problem ? I searched in archives, but there people mention about
in-shuffle, but how to implement it in O(n) is not clear.
--
This is a challenge problem
and you don't need to find a best solution for each case, optimal
solutions are acceptable if they satisfy the problem constraints
for this problem the constraint is cuts should be made so that both
are able to eat equal no of each available ingredient
Examples:
Lets
actually i wanted to know what approach the problem setter is using, since
this problem is NP hard so optimal solution is not always possible.
On Wed, Nov 2, 2011 at 7:20 PM, sunny agrawal sunny816.i...@gmail.comwrote:
This is a challenge problem
and you don't need to find a best solution for
problem setters solution is just a greedy approach
as ingredients are represented using integer values ranging less than 500
so he is making a hash map of ingredients which store the frequency of
the ingredient, whenever the count for some ingredient goes odd, he
makes a cut
On Wed, Nov 2, 2011
O(n) is possible using in-shuffle but doing it in-place was the problem
in case of in-shuffle we need to know which of the elements have been
shuffle so we need O(n) bits of extra space;
O(nlgn) is possible using a quick sort like divide and conquer
algorithm.i read it somewhere and will
does anyone knows how much is the complexity of operations erase and
pop_back in case of Vector(STL)
what would you choose :
Design a data structure where the following 3 functions are optimised:
1. Insert(n)
2. GetRandomElement()
3. Remove(n)
Write a class, and implement the functions. Give
Median of Medians?
On Tue, Nov 1, 2011 at 10:44 PM, Ankuj Gupta ankuj2...@gmail.com wrote:
We have a N X N matrix whose rows and columns are in sorted order. How
efficiently can we find
the median of those N^2 keys ?
--
You received this message because you are subscribed to the Google
@praveen : thats the tricky part of this question bcoz it is a circle
, this algo will fail...
*[200 -10 -10 -10 -10 -10 100] *for this input , answer should be 300
(200+100).
but simple kadane algorithmn will not give the desired output
On Wed, Nov 2, 2011 at 4:14 PM, praveen raj
Hi everyone, I am stuck at places where I need to find lets say
Binomial_coefficient(1000,10) mod 1000 000 007 . What is the best way to do
this, assuming we donot have sufficient memory to use the naive approach :
(n,r) = (n-1,r) + (n-1,r-1) .
--
Dipit Grover
B.Tech in Computer Science and
I was thinking on the lines of heap
On Nov 2, 8:33 pm, Anup Ghatage ghat...@gmail.com wrote:
Median of Medians?
On Tue, Nov 1, 2011 at 10:44 PM, Ankuj Gupta ankuj2...@gmail.com wrote:
We have a N X N matrix whose rows and columns are in sorted order. How
efficiently can we find
the
@Dipit: Here's how you would do it by hand:
B(1000,10) = 1000*999*998*997*996*995*994*993*992*991 /
(1*2*3*4*5*6*7*8*9*10).
We know that the result is an integer, so all of the terms in the
denominator are factors of the numerator. Do some cancelling: 10
cancels 1000 to 100, 9 cancels 999 to 111,
Thats really cool! Thanks Dave :)
--
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
Simple hash will do it in O(1) but with careful implementation of
getRandomElement to distribute probability evenly to each bucket / element in
the bucket
On Nov 2, 2011, at 5:52 PM, shady sinv...@gmail.com wrote:
does anyone knows how much is the complexity of operations erase and pop_back
17 matches
Mail list logo