Re: [algogeeks] Re: sort in minimum cost
Given the list, you would never want to decrement the last element as you
want it to be the maximum.
so either retain or remove the last element
Lets consider the Minimum cost among the sequence i to j as Cost[i..j]
So if you remove the element j, you add j to the cost
Cost[i..j] = Min{ Min(cost[i..j-1])+j, SortByDecremet(Cost(i..j))}
in SortByDecrement returns the total cost of decrementing the elements i to
j-1 so that they are not greater than element j(such that the list is
non-decreasing).
If we solve this equation recursively then I think we will get the minmum
cost.
I hope this can be represented in a better way/better equation.
Correct me if anything is not taken care of .
On Tue, Apr 26, 2011 at 3:58 PM, snehal jain learner@gmail.com wrote:
@above
you cant increment
On Tue, Apr 26, 2011 at 3:48 PM, Naveen Agrawal nav.coo...@gmail.comwrote:
@snehal jain
4 9 8 7 8
o/p 4 7 7 7 8
cost 3 by decrementing 9 n 8
Yes, now question is clear but your last example is incorrect.
4 9 8 7 8
o/p 4 8 8 8 8
cost 2 = decrementing (9 to 8) + incrementing (7 to 8)
--
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.
--
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: Least fare for a return trip Algorithm
@amod I am not sure I understand what you are saying. It is assumed that the K smallest Items(from both list A B) are identified and arranged in increasing order as the first step. Now A(1) and B(1) constitute the least fare round trip(since the list is sorted) and we include that combination into our list of selected round trips with minimal fare. Then we proceed by either including A(1)-B(2) or A(2)-B(1) or both (if they add up to an equal value) I am not clear about what you mean by reuse of elements. Am I missing anything here ? If so a more clear example would help ! On Thu, Oct 28, 2010 at 10:26 AM, Amod gam...@gmail.com wrote: @Algoose Yes, but the algoritm is not correct since we are not covering the condition where element is reused. Ex ia=1 and ib=1 If we increment ia to 2 then there may be a case where A(1)+B(1) is less than A(2)+B(1) but since 1 was denoted by ia which is now 2 hence we will never be able to check this. So algorithm ignores reuse of elements. On Oct 27, 5:06 pm, Algoose chase harishp...@gmail.com wrote: @Dave, I believe in the first if clause ib must be incremented in the else if clause ia must be incremented. is that right ? On Sat, Oct 16, 2010 at 6:21 PM, Dave dave_and_da...@juno.com wrote: @Coolfrog$: 1. No. It should be O(n + k log k) because finding the kth smallest element of an array of size n is O(n), using the Median of Medians algorithm; see http://en.wikipedia.org/wiki/Median_algorithm#Linear_general_selectio. .. . 2. Assuming that the entries in A are distinct and so are the entries in B, we can handle the equality of sums case: find the smallest k elements of A and sort them into ascending order. find the smallest k elements of B and sort them into ascending order. ia = 1 ib = 1 output ia, ib, A(ia)+B(ib) for n = 1 to k do if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ia = ia + 1 output ia, ib, A(ia)+B(ib) else if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ib = ib + 1 output ia, ib, A(ia)+B(ib) else // equality case ia = ia + 1 ib = ib + 1 output ia-1, ib, A(ia-1)+B(ib) output ia, ib-1, A(ia)+B(ib-1) end if end for Dave On Oct 16, 6:20 am, coolfrog$ dixit.coolfrog.div...@gmail.com wrote: @Dave 1. should it not be O(k + klogk) ?? 2. but u are not considering all the possible values... let k =3 like i. a1+b1 ii. min( a1+b2, a2+b1) upto these fine one of them will be chosen ...either ia or ib will increase. iii. but know we have to take remaining of step ii in to consideration along with a1+b3,a3+b1,a2+b3,a3+b2 ... On Fri, Oct 15, 2010 at 8:20 PM, Dave dave_and_da...@juno.com wrote: @Coolfrog$: You don't have to sort the arrays. You only have to find the k smallest elements in each and sort those k entries. This can be done in O(n + k log k). Algorithm: find the smallest k elements of A and sort them into ascending order. find the smallest k elements of B and sort them into ascending order. ia = 1 ib = 1 output ia, ib, A(ia)+B(ib) for n = 1 to k do if A(ia + 1) + B(ib) A(ia) + B(ib + 1) then ia = ia + 1 else ib = ib + 1 end if output ia, ib, A(ia)+B(ib) end for Complexity O(n + k log k). Dave On Oct 15, 4:00 am, coolfrog$ dixit.coolfrog.div...@gmail.com wrote: @amod as given A-B andB-A are in sorted form...if not sort them in O(n log n). then first suggestion A1+B1 second suggestion MIN( A1+B2 , B1+A2) === let it be B1+A2 third suggestion MIN( A1+B2 , A1+B3, A3+B1,A2+B3, A3+B2) let it be A2+B3 and so on... @Dave what will be complexity of above solution...? i think O(n log n) for sorting and second part (suggestions) O(n).. Guys do correct me plz... On Thu, Oct 14, 2010 at 11:10 AM, Amod gam...@gmail.com wrote: @Dave You are partly correct. If i ask for four minimum fares for the round trip then first suggestion is what u said : sum the sum of the minimum cost from A to B and the minimum cost from B to A after that we have to see which combination from both costs, sums up least On Oct 14, 9:55 am, Dave dave_and_da...@juno.com wrote: @Amod. Isn't the minimum sum the sum of the minimum cost from A to B and the minimum cost from B to A? What am I missing? Dave On Oct 13, 11:06 pm, Amod gam...@gmail.com wrote: Hi I think I forgot to mention that the SUM of the ROUND trip i.e. A-B-A (sum = going + returning) should be least. Please
Re: [algogeeks] isomorphic trees
@Saurabh
I believe for Isomorphic trees only the structure counts not the value at
each nodes.
So i think there is no need to compare the value at the corresponding node
positions of the two trees.
On Wed, Jun 9, 2010 at 11:15 PM, saurabh gupta sgup...@gmail.com wrote:
is-isomorphic(t1, t2) {
t1ld = t1-left-data
t2ld = t2-left-data
//.
//base case for null or replace by sentinels and check
if( t1ld == t2ld t1rd == t2rd)
return is-isomorphic(t1ld, t2ld) return is-isomorphic(t1rd, t2rd)
if (t1ld == t2rd t1rd == t2ld)
return is-isomorphic(t1ld, t2rd) return is-isomorphic(t1rd, t2ld)
return false;
}
On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.comwrote:
@vadivel and anand
{ 1,2,3 } is *isomorphic* to { 1,3,2 }
{ 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 }
{ 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 }
so its nt necessary that right and left will interchange. it may or may
not. if all right and left are interchanged then it is mirror tree. i think
ur code is for mirror tree and not isomorphic tree..
--
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.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up. Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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.
