[algogeeks] Re: Dynamic Programming Problem SPOJ-AMR11A

[Bharat Kul Ratan]

If you need hint:
I used DP (Dynamic Programming) to solve this and get AC (Accepted). I 
stored the matrix as 2-D array and then started with array[R][C]. From 
there I can go upward and left. In each element of array put the minimum 
possible value to get the array[R][C]. In case, if we get the value <= 0 
substitute it by 1 because values <=0 are not allowed. Follow this 
procedure up to array[1][1] which is your final answer. I don't know what's 
wrong with your approach as I don't have enough time to examine it.
Here is my solution: http://pastebin.com/Cwah24Xi

-- 
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/-/9t6zsIUpYWYJ.
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Appropriate data structure

[emacs ray]

On Wednesday, July 18, 2012 4:26:11 AM UTC+8, Navin Kumar wrote:
>
> @Dave sir,
> K is known in advance. Many people including me think stack as an 
> appropriate data structure but still i am not satisfied with this answer. 
>
> In case K is not known in advance : according to your solution when a new 
> item is inserted next larger and next smallest item is searched.Isn't it 
> cause much overhead?? can we think a better data structure to optimize this 
> ? 
>
> On Tue, Jul 17, 2012 at 10:52 PM, Dave  wrote:
>
>> @All: We seem to have different understandings of the problem. So Navin, 
>> as original poster, answer this question: Is k known in advance, or is it 
>> given in the request for the min and max elements. I assumed the latter, so 
>> that one request could ask for the max and min of the last 5 days and 
>> another could ask for the max and min for the last 100 days. Others seem to 
>> assume that k is known as the data are collected.
>>  
>> Dave
>>
>> On Saturday, July 14, 2012 2:55:48 PM UTC-5, Navin Kumar wrote:
>>
>>> A set of integer values are being received (1 per day). Store these 
>>> values and at any given time, retrieve the min and max value over the last 
>>> k days. What data structures would you use for storing and retrieving ?
>>
>>  -- 
>> 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/-/c58RGUBQobUJ.
>>
>> 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 options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> For the purpose of finding the max element:

Keep an input-restricted queue with elements in non-strict descending order.
Whenever a new element, says x, comes, remove the head if it is antiquated 
(not reside in the last k positions) and keep removing the last until it is 
greater then x. Retrieve the last element to get the max. Ditto for the min 
element. 

-- 
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/-/7RKV57H0ppAJ.
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Anagram problem

[Navin Kumar]

Assuming a preexisting list of 100 words, how would you efficiently see if 
a word received from input is an anagram of any of the 100 words?

-- 
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/-/5kuxjymYEc4J.
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Appropriate data structure

[Navin Kumar]

@Dave sir,
K is known in advance. Many people including me think stack as an
appropriate data structure but still i am not satisfied with this answer.

In case K is not known in advance : according to your solution when a new
item is inserted next larger and next smallest item is searched.Isn't it
cause much overhead?? can we think a better data structure to optimize this
?

On Tue, Jul 17, 2012 at 10:52 PM, Dave  wrote:

> @All: We seem to have different understandings of the problem. So Navin,
> as original poster, answer this question: Is k known in advance, or is it
> given in the request for the min and max elements. I assumed the latter, so
> that one request could ask for the max and min of the last 5 days and
> another could ask for the max and min for the last 100 days. Others seem to
> assume that k is known as the data are collected.
>
> Dave
>
> On Saturday, July 14, 2012 2:55:48 PM UTC-5, Navin Kumar wrote:
>
>> A set of integer values are being received (1 per day). Store these
>> values and at any given time, retrieve the min and max value over the last
>> k days. What data structures would you use for storing and retrieving ?
>
>  --
> 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/-/c58RGUBQobUJ.
>
> 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 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 algogeeks@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: Appropriate data structure

[Dave]

@All: We seem to have different understandings of the problem. So Navin, as 
original poster, answer this question: Is k known in advance, or is it 
given in the request for the min and max elements. I assumed the latter, so 
that one request could ask for the max and min of the last 5 days and 
another could ask for the max and min for the last 100 days. Others seem to 
assume that k is known as the data are collected.
 
Dave

On Saturday, July 14, 2012 2:55:48 PM UTC-5, Navin Kumar wrote:

> A set of integer values are being received (1 per day). Store these values 
> and at any given time, retrieve the min and max value over the last k days. 
> What data structures would you use for storing and retrieving ?

-- 
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/-/c58RGUBQobUJ.
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Dynamic Programming Problem SPOJ-AMR11A

[aditya ravichandran]

Respected Sir/Madam,
In the problem www.spoj.pl/problems/AMR11A 
I have used the following recursion : 
Definitions :
S[i][j]=>stores the maximum minimized value that the sum attains starting 
from i,j and ending at R-1,C-1 ;
a(i)(j)=>(i,j) th element of given array 


I applied the following recursion:

m=max(S(i,j+1),S(i+1,j))
if(m<0)
S(i,j)=a(i,j)+m ;
else 
S(i,j)=a(i,j);


Finally if S(0,0) <=0 
i am returning |S(0,0)|+1 
else 
i am returning 1 ;
I am getting WA after my submission
Please , point out the error .
For my code:ref.=http://ideone.com/EK5SC
Thanking you ,
rpf

-- 
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/-/oibyUihUOhoJ.
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Directi Interview Ques

[Amit Jain]

Please see *stable merge *in question.

On Sun, Jul 15, 2012 at 2:04 AM, sengar.mahi  wrote:

> @naveen : 3*7+2*9+1*3 =42 is not maximum..
> sum of the product would me maximum wen, i guess, most weighted elements
> are adjacent
> like in this case
> if c={1,2,3,3,7,9}
> 1*2 + 3*3 + 7*9=74 (maximum )
>
> thus this question is just merging both strings such resultant (here C) is
> in sorted order which can be easily done in nlogn .
>
>
> On Sat, Jul 14, 2012 at 2:15 PM, Navin Gupta wrote:
>
>> As the final array contains element in stable-order, at any time we have
>> 3 options for choosing the elements from A & B.
>> 1- A[i] & A[i+1]
>> 2- A[i] & B[I]
>> 3- B[i] & B[i+1]
>> we will choose that pair whose product is maximum.
>> For ex:-
>> A-2,1,3
>> B-3,7,9
>> C- 3,7,2,9,1,3
>> Its a linear time solution with constant time complexity.
>> Algo :-
>> 1 - Keep two indexes i=0 and j=0 pointing to arrays A & B respectively
>> and k=0 for array C.
>> 2 - Now , check the maximum of (a[i]*a[i+1], a[i]*b[j], b[j]*b[j+1] ).
>> 3 - If  a[i]*a[i+1] is maximum,  add a[i],a[i+1] to C, i+=2.
>> 4 - If  a[i]*b[j] is maximum,  add a[i],b[j] to C, i++,j++.
>> 5 - If  b[j]*b[j+1] is maximum,  add b[j],b[j+1] to C, j+=2.
>> 6 - k+=2.
>> 7 - If i,j reached end, then break else Goto step 2.
>> Time Complexity :- O(n)
>> Space Complexity :- O(1)
>>
>>  --
>> 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/-/6-JIwC7l-hYJ.
>>
>> 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 options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> *Regards*
> Mahendra Pratap Singh Sengar
> B-tech 4/4
> NIT Warangal.
>
> Facebook ID 
>
>  --
> 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 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 algogeeks@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: Directi Interview Ques

[Amit Jain]

Awesomely done :) +1

On Mon, Jul 16, 2012 at 2:15 AM, Anshu Mishra wrote:

> two arrays are suppose x[n], y[n];
>
> take a function
> f( x(i, n), y(j, n) , 0) --> taking x[i] as a first element of merged
> array then max sum;
> f( x(i, n), y(j, n), 1)  --> taking y[j] as a first element of
> merged array then max sum;
>
>
> f( x(i, n), y(j, n) ,0) = max(  { x[i] * x[i+1] +  f( x(i+1, n), y(j, n),
> 0)  }, { x[i] * y[j] +  f( x(i+1, n), y(j, n), 1 ) } );
> f( x(i, n), y(j, n) ,1) = max(  { x[i] * y[j] +  f( x(i, n), y(j+1, n), 0)
>  }, { y[j] * y[j+1] +  f( x(i, n), y(j+1, n), 1 ) } );
>
> final sol = max (  f( x(0, n), y(0, n) ,0), f( x(0, n), y(0, n) ,1) );
>
> Now it's looking a very simple *dp *problem with O(n^2) time and space
> complexity. :)
>
> --
> Anshuman Mishra | Software Development Engineer | Amazon
>
>
>  --
> 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 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 algogeeks@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] Appropriate data structure

[praveen raj]

steps:

1) make max heapify and min heapify for first k days
2)for the next day... remove first element from  max heapify and min
heapify  then add new element to existing  max heapify and min
heapify  .
3) Then return max and min in O(1)from max heapify and min heapify .

PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING

-- 
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Appropriate data structure

[adarsh kumar]

For using a stack in order to achieve O(n) time, we can modify push and pop
as follows(assuming we want max):
While pushing, compare the top of the stack with the element to be
pushed(say x). If x>top, just push normally. Else, pop elements until
top>x. Keep an eye on the border cases as well. Thus top will always be
containing the maximum, which can be retrieved obviously in O(1) time.
Similar algo  for pop can be formulated.
regards.

On Tue, Jul 17, 2012 at 9:19 AM, Tushar  wrote:

> can you please elaborate on usage of stack to do it in O(1)?
>
>
>  --
> 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/-/8jTvBVdzsmYJ.
>
> 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 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 algogeeks@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: [Google] Finds all the elements that appear more than n/3 times

[Abhishek Sharma]

I think it can be done by using some randomized algorithm.
Divide the array into subarrays of equal size and then pick a random
element from each group.Do it 3-4 times,if random number comes out equal
for most of the times,return that element.
I haven't tried it.

On Fri, Jul 13, 2012 at 10:53 AM, Ganesh M wrote:

> I guess the 
> linktalks
>  about modified quick sort approach. Remember, if your choise of pivot
> is bad everytime, this will have a worst case performance of O(n). You
> should refer to Selection 
> Algorithmfor better worst 
> case performance.
>
> On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote:
>
>> @sachin:
>>
>> http://valis.cs.uiuc.edu/~**sariel/research/CG/applets/**
>> linear_prog/median.html
>>
>> On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal > > wrote:
>>
>>> To Mr. B
>>> how will you find median in O(n) time? please elaborate.
>>>
>>>
>>> On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:

 I found a similar solution looking somewhere else.

 The solution for this problem is:
 a. There can be atmost 3 elements (only 3 distinct elements with each
 repeating n/3 times) -- check for this and done. -- O(n) time.
 b. There can be atmost 2 elements if not above case.

 1. Find the median of the input. O(N)
 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
 for output if yes}*
 3. partition the array based on median found above. - O(n)  --
 {partition is single step in quicksort}
 4. find median in left partition from (3). - O(n)
 5. check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*
 6. find median in right partition from (3). - O(n)
 7.  check if median element is repeared n/3 times or more - O(n)  *{mark
 for output if yes}*

 its 7*O(N) => O(N) solution. Constant space.

 we need not check further down or recursively. {why? reason it.. its
 simple}


 On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
>
>
> Design an algorithm that, given a list of n elements in an array,
> finds all the elements that appear more than n/3 times in the list. The
> algorithm should run in linear time
>
> ( n >=0 ).
>
> You are expected to use comparisons and achieve linear time. No
> hashing/excessive space/ and don't use standard linear time deterministic
> selection algo.
>
>  --
>>> 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/-/PxIJd3So3tkJ.
>>>
>>>
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>> 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 view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/lZKI47459WgJ.
>
> 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 options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology

-- 
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 options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.