this is like a DP problem to me
1) build a 2 D array .
2) store If difference b/w any two number is = K then M[i,j]=1
else M[i,j]=0
3) Now find max size square (containing all ones) by using Dynamic
Programming.
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
--
You received this message
@lucifer: can you please give a small example and explain?
Now, all we need to do is sequentially access the list and do the
following:
Given 2 pairs (xi, yi) and (x i+1, y i+1),
We will insert RevStr(yi .. y i+1) , excluding the extreme chars, just
before Str(x i+1)...
On Fri, Dec 16, 2011 at
@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 0
@Lucifer
In your algo: how do we get the starting index of the subarray i.e
result?
On Jan 1, 11:03 pm, Lucifer sourabhd2...@gmail.com wrote:
@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
@arun , topcoder
As i have mentioned above we need to also include (0,0) and (N, N)
Also, 0th index is inclusive while adding the chars from RevStr...
i.e *We will insert RevStr(yi .. y i+1) , excluding the extreme chars*
if yi = 0 , then RevStr [0 yi +1)
Now, its obvious that when you get the
Hey,
There is a basic Dp solution.
have two indexes. one at 0 and another at n-1(n is the length of the string)
let it be i and j
if(string[i]==string[j])
then do solve(i+1,j-1)
else
min(solve(i+1,j),solve(i,j-1);
--
Regards,
R.KARTHIKEYAN
BE CSE 3rd year,
Anna university,Chennai-600025.
Suppose you have a tree. A binary tree (for something like
simplicity :p). You are traversing it (using infix, postfix or prefix)
to search for a node. You find your required node. You just realized
that you need to know the path from this node back to the root node
(and/or vice versa). Given the
@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
we might implement it using recursive calls where once found..the node is
printed and true is returned and if leaf is reached...false is
returnedall the function calls getting true will again print and return
true...and false will just return false without printing...this way we can
print only
@Luccifer:
Yes. It is the same!!
Regards,
R.KARTHIKEYAN
BE CSE 3rd year,
Anna university,Chennai-600025.
--
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
@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
@topcoder..
Below i have added a semi pseudocode for better understanding..
Let me know if u want further explanation..
int currMax = 0;
int strtInd = -1;
int endInd = -1;
int currStartInd = 0;
int MinH[N];
int MaxH[N];
// this will return the value of the root stored in the heap..
int
@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)
{
maxLen=temp_maxlen;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
@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 think this can be solved in NlogN using binary search
Here is the idea
We take a deque which stores the index of the array in increasing order
i.e. the index with minimum value is always on the front of the deque
Now when a new element comes we check with the front of this deque .
If the
@Ankur..
A : 2 4 6 8 1, diff is 6.
Looks like the answer acc. to ur code would be 5, but actually it
should be 4..
I m correct, then it can be fixed by looking at the front and back of
the queue and see whether the A[i] is actually the curr min or curr
max..
And then calculate the diff based
@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 in order of increasing values ..so
for curr min we need to only check the front of the queue.
Also I remove the elements of the queue till all the diff of
@Ankur..
I just executed ur code and i m getting 5, instead of 4..
Also,
*
Then yesit is possible that i j and i k... but a[i] is always
less
than a[j] and a[k]...
*
Yes u r right.. but, then when u are calculating the size u are also
by default including the element at index K which
@Lucifer
I checked again and saw a few flaws in my code . Please ignore my prev post
.. :P
1) I am always comparing with q.front() and taking the diff but I should
also do the same with q.back() as it might contain values which have diff
k . So yes , this is a bug
For this as you rightly
@ Ankur,,
Also, in the statement..
*
Then yesit is possible that i j and i k... but a[i] is
always
less
than a[j] and a[k]...
*
* but a[i] always less* - by a[i] i meant the latest element accessed
and not the element positioned at Q.front which is nothing but element
at index 'i'
Hence,
@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
@utkarsh: in yr code it shud be two-- after the swap function and not
before for case 2
On Thu, Nov 10, 2011 at 1:25 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.comwrote:
sorry it was incomplete
On Fri, Nov 11, 2011 at 2:53 AM, UTKARSH SRIVASTAV
usrivastav...@gmail.com wrote:
one = zero =
also I dont think that for case 0 we do not need to have one ++. I guess it
fails for this example
2200101
On Mon, Jan 2, 2012 at 5:36 PM, Arun Vishwanathan aaron.nar...@gmail.comwrote:
@utkarsh: in yr code it shud be two-- after the swap function and not
before for case 2
On Thu, Nov 10,
Here is an O(n*n) time complexity solution with O(n*n) space cost.
The basic idea is using double hashing(hash+set):
Step 1:
Use two for loops to calculate the sum of two integers and store them
in the hash table, which also has an inner set storing the two
integers' index.
E.g. For array
@Lucifier :
*if ( A[j] max)
{
max = A[j];
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
@atul..
Again :) an editing mistake...
Instead of A[j] it should be X[j];
i.e.
*
if ( X[j] max)
{
max = X[j];
strtind = i - max + 1;
endind = j - 1;
}
*
On Jan 3, 10:11 am, atul anand atul.87fri...@gmail.com wrote:
@Lucifier :
*if ( A[j] max)
{
max = A[j];
I just have a basic doubt..does the string s1,s2 statement call any default
constructor?or is it that it is not performed since parameterised
constructor is present?
On Wed, Sep 21, 2011 at 1:31 AM, vijay singh vijaysinghb...@gmail.comwrote:
It is because of the presence of the single
for problem 1, simply keep an array and counter of length of tree, pass it
in each recursive call,
when you find the required node, just print the array and exit.
if not clear, then i will post the code.
@lucifier
for problem 2 nice solution
On Mon, Jan 2, 2012 at 10:56 PM, Lucifer
SuperSum is a function defined as:
* SuperSum(0 , n) = n, for all positive n.
* SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... +
SuperSum(k-1 , n), for all positive k, n.
Given k and n, return the value for SuperSum(k , n) modulo 17.
1=k=50
1=n=1,000,000,000
For Example:
For input..
6,7,1,5,4,10,8
K=8
Start - 0 , end - 6
It shud be start =0 , end = 4
On 3 Jan 2012 12:10, Lucifer sourabhd2...@gmail.com wrote:
@atul..
Again :) an editing mistake...
Instead of A[j] it should be X[j];
i.e.
*
if ( X[j] max)
{
max = X[j];
strtind = i - max + 1;
we can use Boyer's Moore algo
int isSubset(int*mat,int p,int q,int*arr,int n)
{
int h;
h=hash(arr,n);
for(i=0;ipq;i++)
{
if(h==hash(mat+i,n))
{
for(k=0;kn;k++)
{
if(arr[k]!=*(mat+i+k))break;
}
32 matches
Mail list logo
