Re: [algogeeks] Re: LARGEST NUMBER PUZZLE 6 MAY
why not (...((9!^9!)!)!)! or so? there should be some limit on number of operators On Fri, May 6, 2011 at 6:32 PM, Rohit J. email.rohit.n...@gmail.com wrote: I think (9!^9!)! is the correct answer. 1/0 is not because to be precise it's not defined. Lim(x -0) 1/x is infinity. :) Cheers Rohit On 5/6/11, subramania jeeva subramaniaje...@gmail.com wrote: (9! pow 9! ) ! :) Cheers ~ Jeeva ~ On Fri, May 6, 2011 at 6:22 PM, sourabh jakhar sourabhjak...@gmail.comwrote: @manjeet you are genious go for google On Fri, May 6, 2011 at 5:09 PM, ps.raghuchan...@gmail.com ps.raghuchan...@gmail.com wrote: @manjeet ...heheheheheh On Fri, May 6, 2011 at 5:08 PM, Manjeet Chayel chayel.manj...@gmail.comwrote: 1/0 On Fri, May 6, 2011 at 5:06 PM, sourabh jakhar sourabhjak...@gmail.comwrote: what about 9!pow9! On Fri, May 6, 2011 at 5:04 PM, RAghu ps.raghuchan...@gmail.com wrote: What about (9 pow 9) ! On May 6, 4:30 pm, uday kumar uda...@gmail.com wrote: 9 pow 9. On Fri, May 6, 2011 at 3:41 PM, Bala cmb...@gmail.com wrote: 99! Thanks Bala On Fri, May 6, 2011 at 2:48 PM, Lavesh Rawat lavesh.ra...@gmail.comwrote: * LARGEST NUMBER PUZZLE What is the largest number you can get using only 2 digits? Update Your Answers at : Click Here http://dailybrainteaser.blogspot.com/2011/05/largest-number-puzzle-6-.. . Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . * -- 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. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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. -- Cheers!! Manjeet Chayel -- 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. -- P.S.Raghu Chandra, IIIT Allahabad, B.Tech 8th sem. ps.raghuchan...@gmail.com -- 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. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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,
[algogeeks] Re: Corman Question
Please consider this method...
with respect to first point sort (in place) other n-1 ponits comparing the
angles (between the horizontal line passing through 1st point and the line
passing through 1st point and current point)... (nlogn) (merge sort may be
used)
checke for 3 collinear points (nlogn)
now for i=n-1 to 3
{
swap 1st point and (i+1)th point; (we have already taken care of 1st point
and i+2, i+3, ..., n th points)
with respect to the new 1st point, sort (in place) other i-1 ponits
comparing the angles (between the horizontal line passing through 1st point
and the line passing through 1st point and current point)... (ilogi)
checke for 3 collinear points (ilogi)
}
Thanks
Malay
On Mon, Jun 2, 2008 at 12:34 PM, Raghavendra Sharma
[EMAIL PROTECTED] wrote:
Hi Guys,
Can anyone please give me a solution for this??
On a plane if there are n points. How to find out if there are three (3)
points which are collinear in O(N**2log n) time. I got a solution which uses
extra space. But i need a solution which doesn't use any extra space.
Thanks,
Raghavendra
On Fri, May 30, 2008 at 9:26 AM, Raghavendra Sharma
[EMAIL PROTECTED] wrote:
Hi,
On a plane if there are n points. How to find out if there are three (3)
points which are collinear in O(N**2log n) time. I got a solution which uses
extra space. But i need a solution which doesn't use any extra space.
Thanks,
Raghavendra
--
I would love to change the world, but they won't give me the source code.
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: can you solve these questions!!!
2. keep a counter n take the first element of the array say e and initialize the counter n=1 for each remaining number in the array if n==0, e=current element, n=1 if current element is equal to e, n++ else n-- if n==0 there is no number otherwise check the number of occurrences of e in the array n/2 then e output e otherwise there is no number This is known algo... I forgot the name... On Jan 26, 2008 12:38 AM, Dave [EMAIL PROTECTED] wrote: Regarding problem 2: If you really require o(n) rather than O(n), then you can't even look at all of the entries in the array. If you know that one number appears multiple times and all of the other numbers are unique, then you do it in O(n) by looking for two adjacent numbers that are equal. That would have to be the one repeated value, and you can then count the number of occurrences in the array. If there are no adjacent equal values, then there cannot be n/2+1 equal values. I don't have an algorithm yet that will work in O(n) if there can be multiple repeated values and you have to find out if one of them is repeated n/2+1 times. Dave On Jan 25, 8:24 am, kamalakannan .h [EMAIL PROTECTED] wrote: hai guys these questions were asked in anna university onsite programming contest. 1) find the second biggest number in a given array of size n. you have to use n+logn number of searches or less 2) how will you find out if a number is repeated (n/2+1) times in an array of size n? the complexity should be o(n). -- I would love to change the world, but they won't give me the source code. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
I did not get the point:-we mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimumcan you give some example? On 11/7/06, mohamad momenian [EMAIL PROTECTED] wrote: No they can't over lap thank you for your attention On 11/7/06, shisheng li [EMAIL PROTECTED] wrote: Can the 4 overlap? From: algogeeks@googlegroups.com [mailto: algogeeks@googlegroups.com] On Behalf Of mohamad momenianSent: Tuesday, November 07, 2006 4:09 PM To: algogeeks@googlegroups.comSubject: [algogeeks] Problem Hi i have a problem please help me The input of problem is : width and height of 4 rectangle that is between 1,50 and thewe mustcalculate widthand height ofallof rectangles that can coverthis 4 rectangles and it'sareabecome minimum and we can place 4 rectangle vertically or horizontally in the result rectangle --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Balanced tree building
Most importantly, I am not convinced about the correctness of the algorithm.
yes i thought it nefore. there is one problem with my method. my
method only ensures that the height of the new tree will be =
ceiling(log(N+1)). but it is not perfectly balanced. it is possible to
have tree with only right subtree. for example let old tree was
4-3-2-1
then my algo will result in
1
\
3
/\
2 4
For a chain of considerable length yours will contine you to be
unbalanced except that most of the nodes will have left and right
children, a simple test per your algorithm the root of the original
chain continues to be the root of the final result, which is not true.
i did not get your point. can you please clarify it with a suitable example??
On 3/18/06, Malay Bag [EMAIL PROTECTED] wrote:
thts not true
first of all n is height of the new tree i.e. ceiling[log(N+1)] where
N is the no. of node in the old tree.
N = 2^n - 1
and T(n) = T(n-1) + T(n-2) + .. + T(0) + cn
T(n-1) = T(n-2) + ... + T(0) + c(n-1)
so T(n) = 2T(n-2) + 2T(n-3) + .. + 2T(0) + cn + c(n-1)
T(n-2) = T(n-3) + .. + T(0) + c(n-3)
so T(n) = 4T(n-3) + ... + 4T(0) + cn + c(n-1) + c(n-2)
in this way you will get T(n) = 2^(n-1)T(0) + c(n + n-1 + n-2 + .. 1)
now T(0) = O(1)
so T(n) = 2^(n-1)O(1) + O(n^2)
= O(N) + O((logN)^2) = O(N) as NlogN
so effectively the alfgo runs in O(N) time where N is no of node
On 3/18/06, Padmanabhan Natarajan [EMAIL PROTECTED] wrote:
Hi Malay,
I don't see how you algorithm takes O(n) time or O(logn) space, The use
of
recursion should take into account the implicit stack.
for(int i = 0; i n; i++)
process(height - 1)
itself transforms into recurrence T(n) = nT(n - 1) + O(1)
You will see that this is exponential (forget about linear, its not even
polynomial). Also the space requirement is n + n - 1 + n - 21 =
O(nexp2)
Most importantly, I am not convinced about the correctness of the
algorithm.
For a chain of considerable length yours will contine you to be
unbalanced
except that most of the nodes will have left and right children, a simple
test per your algorithm the root of the original chain continues to be
the
root of the final result, which is not true.
Thanks Regards,
Padmanabhan
On 3/13/06, Malay Bag [EMAIL PROTECTED] wrote:
node *root;
node * build(int height)
{
node *r, *temp;
for(i=1, r=null; i=height root; i++)
{
temp = root;
root=root-left;
temp-right=r;
r=temp;
r-left = build(i-1);
}
return r;
}
void main()
{
node *tree;
tree = buld(n); // n=height of of new tree
}
i think this will take O(N) time and logN space... plz check
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Balanced tree building
@rajiv... everything is right. but i think there is small problem. in order to get the middle point of the chain you will need to traverse half of the chain. this will take linear time. so effectively it becomes T(N) = 2T(N/2) + O(N) which results T(N) = O(NlogN) plz check whether i am right On 3/17/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: I think the problem can be solved using tree rotations. So, we start with a left skewed tree 32 // \ 2---1 3 / 1 Find out the total number of nodes initially, can be done in O(n) time and O(1) space. Once we know the number of nodes, rotate the tree right, by n/2 positions. Each rotation takes O(1) time. Now the left and right subtrees have n/2 and n/2 nodes each. (Plus or minus 1 node, forget about that!) Rotate the left subtree and right subtree apropriately, recursively. (One will be right and other left) This will work out to an O(n) time solution, cos in the base case you'll have a subtree of size 1 and that wont need to be rotated. And the recursive stack will grow to atmost O(lg n) size, the height of the tree at any time during rotations. Well, it does seem to work! --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Balanced tree building
Another solution
node *oldtree;
node *build_new(N)
{
node *temp, *r;
int N1, N2;
if N==0 return NULL;
N1 = (N-1)/2; //no of node in the right subtree
N2 = N-1-N1; //no of node in the left subtree
temp = build_new(N1);
r = oldtree;
oldtree = oldtree-left;
r-right = temp;
r-left = build_new(N2);
return r;
}
main()
{
node *newtree;
N= no_of_node(oldtree);
newtree = build_new(N);
}
i think this solution fulfill all the criteria in the problem i.e. perfectly height balanced, O(N) time and O(logN) space complexity. plz check it. if there is a probem in this solution plz dont forget to mention it
i have really enjoyed this problem. thanx Gene for such good problem
On 3/19/06, Malay Bag [EMAIL PROTECTED] wrote: @rajiv.. can you plz write the code or pseducode? i am not clear yet.. thanx in advance
On 3/19/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: No, I guess you've misunderstood the logic.
See, the idea is to build a max balanced tree. For which,we need to check the height of the tree only the first time, there after we know what the lengths of the left and right chains are
going to be. So, though your recursive formula looks right, T(N) = 2T(N/2) + O(N) which results T(N) = O(NlogN) there is a subtle flaw in that, the O(N) isn't
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Balanced tree building
node *root;
node * build(int height)
{
node *r, *temp;
for(i=1, r=null; i=height root; i++)
{
temp = root;
root=root-left;
temp-right=r;
r=temp;
r-left = build(i-1);
}
return r;
}
void main()
{
node *tree;
//root contains original tree
tree = buld(n); // n=height of of new tree
}
i will explain with an example
ake an example 6-5-4-3-2-1
here N=6, height of the new tree = 3
so main will call build(3)
it will build the tree as follows
in build(3)
i=1 6root 5-4-3-2-1
i=2 5 root 4-3-2-1
/ \
build(1) 6
in build(1)
i=14root 3-2-1
so5
/ \
4 6
i=3 3 root 2-1
/ \
build(2) 5
/ \
4 6
in build(2)
i=1 2 root 1
i =21 root null
/ \
build(1) 2
in build(1)
i=1 as root null it will be null
so 1
\
2
so 3
/ \
1 5
\ / \
2 4 6
this way it will work..
by the way can you give me an example that does not work ? it will be
great help as i can find the bug in my program. i am waiting for your
reply. for ne clarification i am here, you can ask me :)
On 3/17/06, pramod [EMAIL PROTECTED] wrote:
Malay, I think your solution gives wrong results. Can you please verify
and explain us.
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Balanced tree building
calculating total no of nodes is too easy... a single traverse through the tree will suffice... this will take linear time and hence will not increase runtime complexity On 3/14/06, BiGYaN [EMAIL PROTECTED] wrote: If we can have the total no. of nodes in tree as an input (say N), this problem is pretty easy. We construct a full BST of level = ceiling ( log (base 2) N ) - 1 conatining only dummy nodes. Now we travel the BST in the same fashion as a linked list starting from the root node. The root must have the highest number, so it becomes the right-most daughter of the right-most node of the last level of the full BST. This tree is then filled (filled in reverse inorder mode) with the numbers obtained from the list-list traversal of the original BST. While doing the traversal in the original tree, we can delete each node as we have passed through it. At the exhaution of the original tree this new tree will obviously be balanced as the original tree with dummy values was balanced and in the worst case there will be only one level more in the RHS of the root of the BST. This algorithm can be accomplished in O(N) time O(N/2) space. The only hitch is that we have to know the total no. of nodes at the beginning. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Balanced tree building
see my solution it will take logN space and O(N) time On 3/15/06, pramod [EMAIL PROTECTED] wrote: But this will require O(N) space anyway. The problem asks for O(log(n)) space. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Balanced tree building
node *root;
node * build(int height)
{
node *r, *temp;
for(i=1, r=null; i=height root; i++)
{
temp = root;
root=root-left;
temp-right=r;
r=temp;
r-left = build(i-1);
}
return r;
}
void main()
{
node *tree;
tree = buld(n); // n=height of of new tree
}
i think this will take O(N) time and logN space... plz check
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: GREAT AND PROMISING WAY TO MAKE MONEY- READ THIS!!!!
roflol On 3/1/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: HOW YOU ARE GOING TO MAKE A $6 INVESTMENT INTO $6000 IN 2 WEEKS ONLINE. ONLINE. A little while back, I was browsing through newsgroups, just like you are now, and came across an article similar to this that said you could make thousands of dollars within weeks with only an initial investment of $6.00! So I thought, Yeah right, this must be a scam,but like most of us, I was curious, so I kept reading. Anyway, it said that you send $1.00 to each of the 6 names and address stated in the article. You then place your own name and address in the bottom of the list at #6, and post the article in at least 200 newsgroups. (There are thousands) No catch, that was it. So after thinking it over, and talking to a few people first, I thought about trying it. I figured: what have I got to lose except 6 stamps and $6.00, right? Then I invested the measly $6.00. Well GUESS WHAT!!... within 7 days, I started getting money in the mail! I was shocked! I figured it would end soon, but the money just kept coming in. In my first week, I made about $25.00. By the end of the second week I had made a total of over $1,000.00! In the third week I had over $10,000.00 and it's still growing. This is now my fourth week and I have made a total of just over $42,000.00 and it's still coming in rapidly. It's certainly worth $6.00, and 6 stamps, I have spent more than that on the lottery!! Let me tell you how this works and most importantly, why it worksAlso, make sure you print a copy of this article NOW, so you can get the information off of it as you need it. I promise you that if you follow the directions exactly, that you will start making more money than you thought possible by doing something so easy! Suggestion: Read this entire message carefully! (print it out or download it.) Follow the simple directions and watch the money come in! It's easy. It's legal. And, your investment is only $6.00 (Plus postage) IMPORTANT: This is not a rip-off; it is not indecent; it is not illegal; and it is virtually no risk - it really works If all of the following instructions are adhered to, you will receive extraordinary dividends. PLEASE NOTE: Please follow these directions EXACTLY, and $50,000 or more can be yours in 20 to 60 days. This program remains successful because of the honesty and integrity of the participants. Please continue its success by carefully adhering to the instructions. You will now become part of the Mail Order business. In this business your product is not solid and tangible, it's a service. You are in the business of developing Mailing Lists. Many large corporations are happy to pay big bucks for quality lists. However, the money made from the mailing lists is secondary to the income which is made from people like you and me asking to be included in that list. Here are the 4 easy steps to success: STEP 1: Get 6 separate pieces of paper and write the following on each piece of paper;PLEASE PUT ME ON YOUR MAILING LIST. Now get 6 US $1.00 bills and place ONE inside EACH of the 6 pieces of paper so the bill will not be seen through the envelope (to prevent thievery). Next, place one paper in each of the 6 envelopes and seal them. You should now have 6 sealed envelopes, each with a piece of paper stating the above phrase, your name and address, and a $1.00 bill. What you are doing is creating a service. THIS IS ABSOLUTELY LEGAL! You are requesting a legitimate service and you are paying for it! Like most of us I was a little skeptical and a little worried about the legal aspects of it all. So I checked it out with the U.S. Post Office (1-800-725-2161) and they confirmed that it is indeed legal! Mail the 6 envelopes to the following addresses: #1) Jeff Millan 1113 N. 19 ½ McAllen,TX 78501 #2) R. Overton P.O. Box 18818 So. Lake Tahoe, CA 96151 #3) KEVIN LEE 8377 APT. I MONTGOMERY RUN RD. ELLICOTT CITY MD 21043 #4) Stephanie Hicks 1283 Evening Canyon Henderson NV 89014 #5) Matt Delorey 102 Centre St Quincy, MA 02169 #6) Aaron Tan 21 SS 22/17 Damansara Jaya 47400 Petaling Jaya Selangor, Malaysia. STEP 2: Now take the #1 name off the list that you see above, move the other names up (6 becomes 5, 5 becomes 4, etc...) and add YOUR Name as number 6 on the list. STEP 3: Change anything you need to, but try to keep this article as close to original as possible. Now, post your amended article to at least 200 newsgroups. (I think there are close to 24,000 groups) All you need is 200, but remember, the more you post, the more money you make! This is perfectly legal! If you have any doubts, refer to Title 18 Sec. 1302 1341 of the Postal lottery laws. Keep a copy of these steps for yourself and, whenever you need money, you can use it again, and again. PLEASE REMEMBER that this program remains successful because of the honesty and integrity of the participants and
[algogeeks] Re: largest Number Smaller Than Given Number
//N=no of digit of n;
//ar[0]=10; for i=1,N a[i]=ith digit of n from left
i=N-1;
while(ar[i]ar[i+1])i--;
if(i==0)return ;//i.e no answer
j = N;
while(ar[i]ar[j])j--;
swap( ar[i],ar[j]);
j = N; i++;
while(i=j)
{
swap(ar[i], ar[j]);
i++; j--;
}
print(ar);
i think this will work.. :)
On 2/28/06, ajay mishra [EMAIL PROTECTED] wrote:
@milochen
Your approach is not correct. I am giving a counter example
say our input is
423, so by ur approach the solution is 243 or 234
but the correct answer is 342.
The approach given by dhyanesh and dazi is correct.
On 2/28/06, milochen [EMAIL PROTECTED] wrote:
Does it always have the solution?
What about that 123456789 ?
I think that it doesn't always have solution for all case.
I am sorry that I couldn't give you a C++ code ,
since I have no complier,so I couldn't ensure whether
the code will be compile successful.
Assume X=(x_1,x_2,x_3, ...,x_(n-2), x_(n-1), x_n) is
our instance s.t. Y=(y_1,y_2,y_3,...,y_(n-2), y_(n-1),y_n)
is the solution for X.
from n-1 to 1, we suppose i is the first i s.t. x_i x_(i+1)
then the solution is almost like the followng
Y
=(y_1,y_2,y_3,...,y_(n-2), y_(n-1),y_n)
=
(x_1,x_2,x_3,...,x_(i-3),x_(i-2),
x_(i-1),x_(i+1),x_i, x_(i+2),x_(i+3)...
...x_(n-2),x_(n-1),x_n )
To pay attension for that
we just need to do one time swap to get
the solution.
From n-1 to 1, If you cannot find the
first i s.t. x_i x_(i+1), then the instance X
have no solution.
--
Ajay kr. Mishra
http://ajay.mishra19.googlepages.com
IIT KGP
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: 0-1 Knapsack Problem
i think this link will answer ur query http://www-cse.uta.edu/~holder/courses/cse2320/lectures/l15/node12.html On 2/21/06, shooshweet [EMAIL PROTECTED] wrote: n objects x1...xn, each having weight wi and profit pi, are to be placed into a sack with capacity M. Can somebody please help me write a algorithm that determines which objects should be placed in the sack inorder to maximize the profit. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
