Looks like a dp problem..
I have an idea..
I believe that u must have this problem hosted on a system having a code
checker..
Can you provide the link to the same, so that we can see if the logic
works..
On Saturday, 23 March 2013 14:29:42 UTC+5:30, rakesh kumar wrote:
There are N objects
@siva..
if (n%3 == 0)
Player 1 will lose
else
Player 1 will win. The no. of balls picked in the first turn will be
n%3
On Saturday, 12 January 2013 18:33:45 UTC+5:30, siva wrote:
consider there are N balls in a basket. 2 players play the turns
alternatively ..AT each turn,the
@siva..
if (n%3 == 0)
Player 1 will lose
else
Player 1 will win. The no. of balls picked in the first turn will be
n%3
--
@atul007..
I think the solution that you have given is to solve the coin denomination
problem... where the denominations range from 1 to R..
But that's not the question..
The question is :
Given R and N, we need to find a set of coins where the set size is N (out
of all R(C)N combinations
@atul 007..
Also i would like to point out that denomination array that u are using
consists of 1 to R. Therefore ideally the answer that you should get for
each coin[i] is 1. Hence, its a constant time algorithm ..
On Saturday, 22 December 2012 03:31:52 UTC+5:30, shady wrote:
Given R and
@phoenix
The reason is not an implication of using references.
If u are passing emptyvec() as an argument then the vector returned by
emptyvec() is a temp object ( as its not being assigned to a obj var
created by the programmer), which means that the user/programmer shouldn't
be able to
@arun..
If u have a copy of the Ç prog lang by dennis ritchie, then u can
checkout for a simplified implemented version of malloc and free provided
under section 8.7 (storage allocator)... It uses the same concepts as
mentioned by @Don.
On Wednesday, 19 December 2012 22:02:06 UTC+5:30, Anuj
@arun..
Couple of questions need to be clarified :
1) Are all the numbers given in the unsorted array +ive integers.. ?
2) By 2 equal arrays do you mean that both the arrays should be of size N/2
(where N is even) .. ?
If the above assumptions are true then we can use the following recurrence
@vikas
I believe that if we generalize the question saying that there are N
students and K schools, such that each school can accommodate at max
(N/K) students (which means each school needs to accommodate exactly
(N/K) students. Given this we need to find the minimum distance.
By O(n^3), in this
@ above
small correction..
/*
By O(n^3), in this case it means O((N/K ^ K)) .
*/
Therefore, N = 9, K=3.. hence (9/3)^3 = 27
On Aug 4, 4:24 am, Lucifer sourabhd2...@gmail.com wrote:
@vikas
I believe that if we generalize the question saying that there are N
students and K schools
@Prakhar Jain
I believe that the following recurrence shall solve it..
Take an array C[n+1][n+1]...
Now, we only need to calculate those C[i][j]'s where i+j is even..
// Assuming 1-based index...
Initialization condition...
C[0][0]=0;
for(int i =0; i =n; i+=2)
{
C[0][i] = C[0][i-2] +
@small correction:
In the initialization condition the loop index i shall start from 2
and not 0..
// for(int i =2; i =n; i+=2)
On 30 July, 15:23, Lucifer sourabhd2...@gmail.com wrote:
@Prakhar Jain
I believe that the following recurrence shall solve it..
Take an array C[n+1][n+1]...
Now
@ ruru
I think we can do it in log(n)..
I am not jolting down the code but giving out the idea that would lead
to log(n) time..
If we write down all the nos. in the binary format one below the
other.. we will observe the following pattern :-
at bit index '1' the bit value toggles in group of
@Mahendra Sengar..
We can solve it by interpreting it as a graph problem (as N and K are
small).
Lets say that :-
a) Each node in the graph defines a particular state of the disks and
the pegs.
b) Each edge in the graph defines a valid transition from one state to
another and weight of each edge
@above..
In case the no of nodes that are placed at the certain height from the
start node are growing at an extremely fast rate, we can instead use a
dfs approach as well.
On 30 July, 18:13, Lucifer sourabhd2...@gmail.com wrote:
@Mahendra Sengar..
We can solve it by interpreting
, Lucifer sourabhd2...@gmail.com wrote:
@small correction:
In the initialization condition the loop index i shall start from 2
and not 0..
// for(int i =2; i =n; i+=2)
On 30 July, 15:23, Lucifer sourabhd2...@gmail.com wrote:
@Prakhar Jain
I believe that the following recurrence
A[src]=1.
On Wednesday, 30 May 2012 23:49:46 UTC+5:30, Amol Sharma wrote:
just check, In the above loop(posted by lucifer) it will only return zero
everytime..
corrected after getting the linearized list after topological sort :
take an auxillary array, A of size N*A[i] represent
@amrit
Every non-static member function of a class has an implicit parameter
that is passed to the function (when called) This implicit parameter
is nothing but the this pointer. Now if you want to make the
implicit parameter (this pointer) a const, how would u do it? This
is done by placing the
1) Linearize the DAG using DFS. ( topological sorting)
2) Now take an array of size A[N] ( N - nodes in the DAG ), where A[i]
mimics the 'i'th node in the linearized list.
3) Scan the linearized list from left to right to get to the source
node and initialize all the corresponding values in array
The no. of transformations = cost of (no. of replace operations + no.
of deletes + no. of additions) / 2
where,
cost of replace operation = 2
cost of delete/addition operation = 1
On May 22, 8:12 am, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote:
then waht will be it's recurrence relation
O(n) approach for finding the height of the stacks..
-
First take 2 arrays A[n] and B[n],
where A keeps track of the no. of times a start index(the start query
index) occurs.
and B keeps track of the no. of times a end index(the end query index)
I think we can tweak the standard find the height of the tree
program to get the result..
As we know that the 2 extremes of the longest path are nothing but
leaves. Hence, all we need to do is figure out is for which set of
leaves would the path be maximum..
[ Special Case : it need to be always
@above:
Special Case : it need *not* be always leaves
On Mar 26, 2:42 am, Lucifer sourabhd2...@gmail.com wrote:
I think we can tweak the standard find the height of the tree
program to get the result..
As we know that the 2 extremes of the longest path are nothing but
leaves. Hence, all we
@All
[ Let the tree to be searched in be 'T' and the subtree to be matched
be 'S']
If i understood the previous posts correctly.. then basically we
discussed about 2 methods:
1) Brute force, wherein we consider each node of the 'T' as the root
of new subtree and try to compare it with 'S'.
@WgpShashank..
As pointed out by you, yes i agree that catalan no. has various
interpretations. But, keeping that in mind it doesn't mean that the
only relationship b/w binary tree and catalan no. is the following:
Catalan No = No. of full binary trees having (n+1) leaves..
If you read the
@WgpShashank
Nope...
Catalan no. has nothing to do with full binary trees..
On Jan 23, 1:16 pm, WgpShashank shashank7andr...@gmail.com wrote:
@Lucifier Catelan NUmber will gives Number of *Full binary Trees* not
BInary Tree ? isn't it ?
Thanks
Shashank
--
You received this message
@another approach..
Lets say,
F(n) - basically represents of ways n 'H' and 'T''s can be placed
such that there are no consecutive 'H''s.
1) Now, say the sequence of 'H' and 'T' ends with 'T'. Now, 'T' is at
nth position, hence it doesn't matter whether (n-1) th position has
'H' or 'T'.
But then
to win:
for( int i =1; i 23; ++i)
{
sampleCount+= a[i]*b[i-1]*b[i-1];
}
probability= sampleCount/ 474552;
sampleCount will be: 145650
probability = 0.306921
On Jan 23, 2:36 pm, Lucifer sourabhd2...@gmail.com wrote:
@Don..
Yup, it seems I misread it ... :) .. Thanks
On Jan 23, 9:17 am, Don
in P1 winning.
Thus P(p1 wins) = 0.30850919745967...
Don
On Jan 23, 7:34 am, Lucifer sourabhd2...@gmail.com wrote:
@Don and Sundi..
As Don pointed out, all we are looking for is:
sum of a1 sum of a2
sum of a1 sum of a3
Assumption:
1) The 2 cards picked for a particular
I just wrote a code which would work for any given size K.
I tested it with K = 1 till 7.
[ in the question asked above K=2]
Also, tested for corner cases..
If you guys are interested, then have a look at the code..
I have added few helper functions so that you can directly run the
code and use
@above
attaching the file..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/YW_phbT3me4J.
To post to this group, send email to algogeeks@googlegroups.com.
of time we need to figure
out whether its divisible by 5.
The above given code will work for this case as well.
On Jan 22, 12:19 pm, Lucifer sourabhd2...@gmail.com wrote:
@another approach..
The remainders when the following nos. are divided by 5 are :
Numbers Remainder
2^0
that make
any sence?
Don
On Jan 19, 2:35 pm, Lucifer sourabhd2...@gmail.com wrote:
@correction:
Probalilty (a1 wins) = 24575/474552 = .051786
On Jan 20, 1:30 am, Lucifer sourabhd2...@gmail.com wrote:
hoping that the cards are numbered 1,2,3,,13..
Probalilty (a1 wins) = 21723
@above
editing mistake.. (btw the working code covers it)
/*
int j =*1*;
for(int i = 0; i 12 ; i+=2)
{
A[i] = A[i+1] = A[22-i] = A[21-i] = j;
++j;
}
*/
On Jan 22, 6:53 pm, Lucifer sourabhd2...@gmail.com wrote:
@Don..
Well i will explain the approach that i took to arrive
sundi...@gmail.com wrote:
Hi Lucifer,
Have you checked the sum of probability of (a winning + b
winning + c winning + draw)==1 ?
On Jan 22, 2:38 pm, Lucifer sourabhd2...@gmail.com wrote:
@above
editing mistake.. (btw the working code covers it)
/*
int j =*1*;
for(int
swaps of a[row][col] with a[row+1][0]??
so is heapify sep in all just comparison of x with b and d only and swap if
needed??
On Sat, Jan 14, 2012 at 1:48 AM, Gaurav Kalra gvka...@gmail.com wrote:
Bases on algorithm suggested by Lucifer, I have coded the problem in C
(please see
to NULL.
If you trace it. you will figure it out.
In case there is a doubt do let me know..
On Jan 23, 4:17 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@lucifer: in yr code will not all the root-left be NULL for each iteration
as
startindex is always greater than endindex ( i.e i-1
c
d x f
g h i
Now say,
x = min(f,h)..
Hence, we hit the break statement and exit from the loop..
On Jan 23, 5:03 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@lucifer: yes I get that...I was just saying that after a swap has happened
within the while loop ( since x min(b,d
@Arun..
I think you are generating the bin-tree for ' i =startIndex' and not '
i =startIndex +1'..
Hence, if you just trace it for ' i =startIndex + 1' for all the
recursive calls, you should get it...
On Jan 23, 5:22 am, Lucifer sourabhd2...@gmail.com wrote:
@Arun...
You are not getting
hoping that the cards are numbered 1,2,3,,13..
Probalilty (a1 wins) = 21723/474552 = .045776
On Jan 20, 12:47 am, Don dondod...@gmail.com wrote:
P= 8800/28561 ~= 0.308112461...
On Jan 18, 7:40 pm, Sundi sundi...@gmail.com wrote:
there are 52 cards.. there are 3 players a1,a2,a3
@correction:
Probalilty (a1 wins) = 24575/474552 = .051786
On Jan 20, 1:30 am, Lucifer sourabhd2...@gmail.com wrote:
hoping that the cards are numbered 1,2,3,,13..
Probalilty (a1 wins) = 21723/474552 = .045776
On Jan 20, 12:47 am, Don dondod...@gmail.com wrote:
P= 8800/28561
@All..
I have an idea...
As we are looking for an in-place algo...
Well, given the array, it actually mimics a min-heap.. not exactly a
binary tree heap but a heap wherein its subtrees share some nodes...
Now the point being that... say we select any index pair (i,j), we
know for the submatrix
@correction:
/*
basically either go down or go
*right* in case adjustment is required...
*/
On Jan 11, 1:56 pm, Lucifer sourabhd2...@gmail.com wrote:
@All..
I have an idea...
As we are looking for an in-place algo...
Well, given the array, it actually mimics a min-heap.. not exactly
@correction..
for ( int row = 0; row *M*; ++row)
On Jan 11, 1:56 pm, Lucifer sourabhd2...@gmail.com wrote:
@All..
I have an idea...
As we are looking for an in-place algo...
Well, given the array, it actually mimics a min-heap.. not exactly a
binary tree heap but a heap wherein its
@dipit ..
Yup you are correct..
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i (1 to M} { N*(M+N-i) }
= M * N * (M + 2N - 1) /2
On Jan 11, 2:19 pm, Dipit Grover dipitgro...@gmail.com wrote:
@Lucifer : I came up with a similar algorithm
)
}
}
= M*N*(M + N)/2
On Jan 11, 2:27 pm, Lucifer sourabhd2...@gmail.com wrote:
@dipit ..
Yup you are correct..
Say, no of rows = M and no. of cols = N,
Time complexity = sum over all i (1 to M} { N*(M+N-i) }
= M * N * (M
a sorted column-array(array formed by taking the head elements of each
row-array) each time we look for the min element. Please correct me if I am
wrong.
@Lucifer- yeah we need to only traverse the columns till the current
column.
--
You received this message because you are subscribed
@atul..
Complexity of heapifying(basically re-stabalizing the heap) is (m - i
+ j) when an element A[i][j] is swapped with A[i+1][0] as an impact of
A[i][j] A[i+1][0]..
On Jan 11, 4:44 pm, Dipit Grover dipitgro...@gmail.com wrote:
@Shady : you would definitely need two index variables for
@Ankur..
Yes... If you follow the algo that i have presented above and use
Atul's example you will be able to figure out..
Maybe, the confusion is regarding heapfying.. ryt??
I am assuming so..
Now as i said a submatrix rooted at A[i , j] is nothing but a heap
where its subtrees share a few
@Ankur..
I will try to explain the approach with an example..
Say the given matrix (sorted row wise and column wise) is as follows:
a1 a2a3 a4
b1 b2b3 b4
c1 c2c3 c4
d1 d2d3 d4
Now, we want to sort the 2D array such that when all the rows are
aligned
sorry, in case previously given details by me were
inadequate...
Was posting in a hurry :)...
Hope, now all doubts would be cleared...
---
On Jan 11, 9:55 pm, Lucifer sourabhd2...@gmail.com wrote:
@Ankur..
I
acquired space )
PARENT = floor(*i*/2)
LEFT (*i*) = 2i
RIGHT (*i*) = 2i + 1
is this approach is wrong ??
On Wed, Jan 11, 2012 at 10:34 PM, Lucifer sourabhd2...@gmail.com wrote:
@atul..
Sorry, but i don't agree with both of ur posts...
First of all, the complexity won't be log(m*n
@atul..
Missed ur previous post by a couple of mins..
Nyways it seems u got it .. :)..
On Jan 11, 10:44 pm, Lucifer sourabhd2...@gmail.com wrote:
@atul..
Yup, its incorrect... because as i said.. for A[i][j] its children are
at A[i+1][j] and A[i][j+1]..
Hence, if u look at the array as a 1D
+919966006652
On Wed, Jan 11, 2012 at 11:14 PM, Lucifer sourabhd2...@gmail.com wrote:
@atul..
Yup, its incorrect... because as i said.. for A[i][j] its children are
at A[i+1][j] and A[i][j+1]..
Hence, if u look at the array as a 1D array, then your LEFT and RIGHT
indices would be incorrect
@ravi..
The recurrence would be :
F(N) = F(N-1) + F(N-2) + 2*F(N-3), for N=3..
F(0) = F(1) = 1,
F(2) = F(1) + F(2) = 2
On Jan 11, 11:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote:
*Problem 1: Number of Tilings, (K Narayan Kumar, CMI)*
You have to tile a room that is two units wide and *N*
@correction:
F(2) = F(1) + F(0)..
On Jan 11, 11:59 pm, Lucifer sourabhd2...@gmail.com wrote:
@ravi..
The recurrence would be :
F(N) = F(N-1) + F(N-2) + 2*F(N-3), for N=3..
F(0) = F(1) = 1,
F(2) = F(1) + F(2) = 2
On Jan 11, 11:08 pm, Ravi Ranjan ravi.cool2...@gmail.com wrote
@All
I found a flaw in the recurrence provided above..
Correct recurrence is as follows:
F(n) = F(n - 1) + F(n - 2) + sum over all i ( 0 to (n-3) ) { F(i) }
F(0) = F(1) = 1;
On Jan 12, 12:03 am, Lucifer sourabhd2...@gmail.com wrote:
@correction:
F(2) = F(1) + F(0)..
On Jan 11, 11:59 pm
;
}
Plz, let me know if the test inputs are failing...
On Jan 12, 12:32 am, Lucifer sourabhd2...@gmail.com wrote:
@All
I found a flaw in the recurrence provided above..
Correct recurrence is as follows:
F(n) = F(n - 1) + F(n - 2) + sum over all i ( 0 to (n-3) ) { F(i) }
F(0) = F(1) = 1
@above..
There is a memory leak in the above code.. but that shouldn't cause a
problem .. :)
On Jan 12, 12:42 am, Lucifer sourabhd2...@gmail.com wrote:
@ravi..
A working code, in case u have test inputs against which u can test
the validity of the logic:
int tiles(int N)
{
if( N
@correction..
Though the code implements it, i missed factor '2' in the recurrence
that i have provided above...
F(n) = F(n - 1) + F(n - 2) + sum over all i ( 0 to (n-3) ) { 2 *
F(i) }
On Jan 12, 12:44 am, Lucifer sourabhd2...@gmail.com wrote:
@above..
There is a memory
@priyanka..
I don't think it will work...
Say for ex- 1,-1,3,5,1,-3 ... the answer should be (3),(5,1,-3)..
Will the above fix give the correct answer for the given input ??
Also, i see a couple of flaws in the checks...
Say, Left right and p2 = len -1, then it will actually take A[len]
into
@correction..
1) Find the first pair (i,j) such that:
/*
sum( A[0] .. till A[i]) = sum(B[0] ... B[j])
*/
On Jan 10, 6:13 pm, Lucifer sourabhd2...@gmail.com wrote:
@priyanka..
I don't think it will work...
Say for ex- 1,-1,3,5,1,-3 ... the answer should be (3),(5,1,-3
@atul
First of all, i must say you are really good at catching my editing
mistakes :)..
Correction:
superSum = ( superSum * ( ( n + i )%17 ) ) / (i+1);
On Jan 10, 8:29 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifier : your reduced form is not generating right output...
remove
the pattern...
--
On Jan 10, 8:35 pm, Lucifer sourabhd2...@gmail.com wrote:
@atul
First of all, i must say you are really good at catching my editing
mistakes :)..
Correction:
superSum = ( superSum * ( ( n + i )%17 ) ) / (i+1);
On Jan 10, 8:29 pm
://www.spoj.pl/problems/NY10E/
[@ Non-Decreasing Digits]
On Jan 10, 11:14 pm, Lucifer sourabhd2...@gmail.com wrote:
@priyanka..
SuperSum(k, n) :
For any given base X representation there will be X digits..
Now say, the digits are named as A(i) ... such that,
A1 A2 A3 A(X)...
[ all
@All
The same algo will work for both +ve and -ve nos.. no need for
modification..
For ex-
Say the sum is 4 and the set is { 1, 2, 3, -2 }
Now if u include -2 as part of ur solution then for the rest 3
elements the sum would be 4-(-2) = 6, which is correct...
On Jan 9, 2:20 pm, Siddhartha
@all
Check the link that i have provided above.. It solves the problem
using DP..
On Jan 7, 7:15 pm, atul anand atul.87fri...@gmail.com wrote:
@ Adolfo : little more detail about your approach will be helpful.
On Sat, Jan 7, 2012 at 7:07 PM, Adolfo Ccanto adol...@gmail.com wrote:
this
@Anurag...
'SuperSum' can be reduced to the following form..
SuperSum ( k, n) = SuperSum (k-1, n) * (n+k) / (k+1) ..
Time Complexity : O(K) , Space Complexity : O(1)
Code:
int getSuperSum(int k, int n)
{
int superSum = n; // SuperSum(0, n)
int i = 0;
while( ++i = k)
{
] . dat would be
wrong.
On Dec 7 2011, 6:40 pm, Lucifer sourabhd2...@gmail.com wrote:
I have modified some part of the above post below to avoid confusion
regarding the generation of all subsets:
Say, we need to find all the subsets which led to A[N, K] = 1, to do
this we will take
@atul..
So following the above previous posted link.. the time complexity
would be 4*n = O(n)...
[ just adding it here, because i saw that u went thru the link.. :)]
On Jan 7, 9:30 pm, atul anand atul.87fri...@gmail.com wrote:
@Don : what would be the complexity of your alogithm??
On
intermediate nodes are (A[i,
j] , A[i-1, j])
-
On Jan 7, 11:37 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifer :
for W[]={1,3,2,1,2} and Wmax=4.
this array will be formed.
0
1
2
3
4
0
1
0
0
0
0
1
1
1
0
0
0
3
@ The following link might help..
http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b?hl=en#
Basicaly if A[N, Wmax] = 1, then find all subsets using backtracking..
where,
N = no. of elements,
Wmax = 4...
On Jan 6, 7:50 pm, atul anand atul.87fri...@gmail.com wrote:
Assuming that the N points on the graph are represented in the form of
(x,y) i.e. cartesian coordinates..
Then say, A = ( a1, a2);
The equation of the circle centered at A would be
(x - a1)^2 + (y-a2)^2 = R^2...
Now, to find the points that lie within the range R, u need to check
the following
@ all
Ignore my previous post
On Jan 5, 5:58 pm, Lucifer sourabhd2...@gmail.com wrote:
Assuming that the N points on the graph are represented in the form of
(x,y) i.e. cartesian coordinates..
Then say, A = ( a1, a2);
The equation of the circle centered at A would be
(x - a1)^2 + (y-a2
@atul..
you are not getting it wrong.. Its absolutely correct
On Jan 5, 11:28 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifier :
i was considering algo as mentioned by you and was considering heap with
indexes as mentioned in your first post i.e :-
/*
Also, though the MinH
@atul..
First of all 6 is not in the heap but its index '0' is..
I think before also u had raised this question of heap stability and i
did explain with an example in one of my previous posts that it won't
affect the checks...
I m repeating the same explanation here with the reason why it won't
@above..
This is what i assume is happening ( apart from inherent compiler
optimization is any)...Let me know if i m wrong..
when s2=name; is done it should call the overloaded equal to
operator..
But, 'name' is not a string object, its basically a char pointer to a
const string test..
Now, for
... it can also work for related(different
not same) class types... say, the formal parameter of constrcutor has
a base class type and the RHS of '=' has a derieved class type...
On Jan 3, 7:52 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@lucifer: ok so you are saying that the constructor
@atul...
For the O(n^2) approach, here's the working code..It should work for
all ur examples.. I have fixed it..
int max = 0;
int strtind = -1;
int endind = -1;
int X[2][N];
for(int i=0;i=N;i++)
X[0][i]=X[1][i] = 0;
int *prev, *curr;
for (int i = 0; i N; ++i)
{
prev = X[i%2];
curr =
...@gmail.com wrote:
@Lucifer
As per the LCS for example dabae
Reverse String is eabad
e a b a d
0 0 0 0 0 0 0
d 0 0 0 0 0 1
a 0 0 1 1 1 1
b 0
@Kartikeyan..
I think the above code mimics an LCS equation.. where the 2 strings as
input are Original str and the Reverse of the OrigStr..
Is it ?
On Jan 2, 9:14 pm, Karthikeyan Ravi qwertykarthi1...@gmail.com
wrote:
Hey,
There is a basic Dp solution.
have two indexes. one at 0 and another
@topcoder..
Problem 1:
Say we are doing an inorder traversal..
All we need to do is once the required node X is found.. we will stop
the recursion..
The recursion can be stopped by using a bool value..
Basically the bool value will indicate - no further processing
required..
While the recursion
);
}
}
}
else
{
// vice-versa based on the above logic..
}
}
}
On Jan 2, 8:28 pm, top coder topcode...@gmail.com wrote:
@Lucifer
In your algo: how do we get the starting index of the subarray i.e
result?
On Jan 1, 11:03 pm
@atul..
Say the array is
2 4 6 8 10 and diff is 2.
A = 1 1 1 1 1 which is incorrect..
Or may be the above code explains something else..
If so, can u give more explanation...
On Jan 3, 12:03 am, atul anand atul.87fri...@gmail.com wrote:
@praveen : i guess we can optimize the space to O(n);
@above..
I m sorry,
A would be 1 2 3 4 5 ..
On Jan 3, 12:03 am, atul anand atul.87fri...@gmail.com wrote:
@praveen : i guess we can optimize the space to O(n);
if diff b/w two number is =K then A[i]=A[i-1]+1;
if condition fails temp_maxLen=A[i-1];
if(temp_maxlen maxLen)
{
..
I all my observations are correct, then a couple of modifications will
rectify the code..
In case i m wrong.. then cheers :)
On Jan 3, 1:20 am, Lucifer sourabhd2...@gmail.com wrote:
@ Optimization ... O(N).. single run O(n^2)
Basically in a single run we can calculate the maximum value using
..
-
What do u think?
On Jan 3, 3:36 am, Ankur Garg ankurga...@gmail.com wrote:
@Lucifer
I checked with my code
The answer is coming out to be 4 ..So in this case its passing
Also the queue is containing the indexes
, the actual statement should be,
*
Then yes it is possible that i j and i k... but a[R] is
always less than a[j] and a[k]...
*
R is basically the latest element accessed..
On Jan 3, 3:56 am, Lucifer sourabhd2...@gmail.com wrote:
@Ankur..
I just executed ur code and i m getting 5, instead
@Ankur..
Missed ur post just by 2 mins..
Great..
-
On Jan 3, 3:59 am, Lucifer sourabhd2...@gmail.com wrote:
@ Ankur,,
Also, in the statement..
*
Then yes it is possible that i j and i k... but a[i] is
always
less
than a[j] and a[k]...
*
* but a[i] always
];
strtind = i - max + 1;*
i am not getting this in your code :-
say if input is :- 1,2,3,4,5,6,100
K=8;
A[j]=100;
then
(100 max)
{
max=100;
* strtind= i - 100 +1;}
*
On Tue, Jan 3, 2012 at 4:33 AM, Lucifer sourabhd2...@gmail.com wrote:
@Ankur..
Missed
);
p2 = MergeSort(second half of list pointed by p);
return MergeSortedLLS(p1, p2);
}
Complexity of sorting:
To partition the list in 2 halves - O(N)
To merge 2 sorted list - O(N)
To sort:
T(N) = O(N) + T(N/2) + O(N)
= N log N
On Dec 31 2011, 4:46 pm, Lucifer sourabhd2
@atul
Is the above code's optimization based on the 2nd approach that i have
mentioned above or is it something different..
In case, you are doing something else can u provide us with more
explanation so that it would be easier for everyone to understand the
code ...
On Jan 1, 3:55 pm, atul
@atul..
Below i have explained how the reduction from N^2 to N log N approach
will work..
Space complexity 2*N = O(N)
The following data structures will be used to optimize the same :-
1) a min-heap named MinH - say X[N] can be used to implement the min-
heap.
2) a max- heap named MaxH - say
@ SAMM..
The following might work, but would need verification..
Below solution is for a generic no. of elements.
In your case its 4.
Lets represent 4 by R.
Lets take a 2-dim array named A, to store the intermediate values..
Now, X ( A[i, j] , p ) basically means whether given the first 'i'
@atul..
There are no stability or access issues with the code..
Below i have given explanation for ur concerns...
--
a) I think ur first concern is a stable heap...
The heap might not be stable as u have mentioned.. but the code makes
it stable..
Hence, it
@atul...
The only reason behind storing the indices instead of actual element
values in the heap, as mentioned in my original post, was to resolve
the issues that u have brought up...
Cheers :)
On Jan 2, 11:08 am, Lucifer sourabhd2...@gmail.com wrote:
@atul..
There are no stability or access
@atul..
Yes,
j=K and p=4
Also would like to mention that in my first post I have mentioned
about a variable 'R' and not used it in the explanation..
Actually 'R' is nothing but 'p', in case you got confused...
On Jan 2, 8:20 am, Arun Vishwanathan aaron.nar...@gmail.com wrote:
does this
@atul..
Why both 'l--' and 'm--' together ? doing this you will miss out on
lot of intermediate values..
Also, if the array sorted and u want to capture the all valid values
for check in the minimum runtime then instead of having 2 right
pointers, have 1 left and 1 right pointer and inc/dec
@atul
There is no. correction..
The for loop is correct.. It should be:
for (int i =0; i 9; ++i)
On 31 Dec, 16:02, atul anand atul.87fri...@gmail.com wrote:
correction in Lucifier code :-
if (N 1)
{
int iter = 0;
int totalCount = 10; // this is when N = 1 ...
for (int i=0; i = 9;
@atul..
Yes, A[i] += A[i+1] is correct..
Another correction that is required is :
for (int i = 7; i = 0 ; --i) // earlier for (int i = *8*; i 0 ; --
i)
On 31 Dec, 16:10, Lucifer sourabhd2...@gmail.com wrote:
@atul
There is no. correction..
The for loop is correct.. It should
1 - 100 of 197 matches
Mail list logo
