Re: [algogeeks] Sum of the Sequence
This is a 'finite calculus' (differences summations) problem.
You can solve it using difference operator (actually its inverse which gives
you the discrete integration which is nothing but summation).
If you do not know finite calculus, Google for it (or refer Concrete
Mathematics by Knuth).
The solution for any k is.
*f(n) = nC(k+1) + nC(k-1) + nC(k-3) + (all the way down to nC0 or nC1
depends on k is odd or even).*
Here nCr is the binomial coefficient n choose r.
Eg: Let k = 3, n = 4
f(4) = 4C4 + 4C2 + 4C0 = 1 + 6 + 1 = 8
Another, k = 3 and n = 5
f(5) = 5C4 + 5C2 + 5C0 = 5 + 10 + 1 = 16
On Wed, Nov 4, 2009 at 11:23 AM, abhijith reddy abhijith200...@gmail.comwrote:
Is there a way to find the sum of the Kth series ( Given below)
K=0 S={1,2,3,4,5,6,}
K=1 S={1,2,4,7,11,16..} common diff = 1,2,3,4 5 ...
K=2 S={1,2,4,8,15,26...} common diff = 1,2,4,7 11... (series with
K=1)
K=3 S={1,2,4,8,16,31...} common diff = 1,2,4,8 15... (series with
K=2)
Note that the common difference of Kth series is the (K-1) series
Any ideas ??
--
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.
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: 100!
On Sun, Oct 11, 2009 at 6:40 PM, Gautham Muthuravichandran gautha...@gmail.com wrote: 9.. All the factorials above 5! is divisible by 9. Divisible by 9 does not mean exactly 9. -Gautham On Sun, Oct 11, 2009 at 11:54 AM, Debanjan debanjan4...@gmail.com wrote: On Oct 11, 10:29 am, Anil C R cr.a...@gmail.com wrote: Project Euler!! I remember I cheated on this problem :P At first I used my SPOJ FCTRL2 solution to get the factorial of 100 then I simply add up those digits :D Most problems of Project Euler can be brute forced ! --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: n balls and k different colors 1=k=n
I just noticed that in your problem the balls are 'similar'.
Then the solution is a simple composition and the answer is {n-1, k-1} where
{n,k} stands for binomial coefficient.
I will give a proof sometime later if needed.
On Sat, Oct 10, 2009 at 11:22 AM, vicky mehta...@gmail.com wrote:
i didn't get anything plz elaborate
On Oct 10, 10:44 am, Prunthaban Kanthakumar pruntha...@gmail.com
wrote:
Sterling numbers of second kind.
On Sat, Oct 10, 2009 at 10:41 AM, vicky mehta...@gmail.com wrote:
example:
n=10,k=10
ans:1
n=30,k=7
ans:
475020
On Oct 10, 9:51 am, vicky mehta...@gmail.com wrote:
u have to color n similar balls with k diff. colors , such that every
color must be used atleast once find the no. of ways
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: n balls and k different colors 1=k=n
Sterling numbers of second kind. On Sat, Oct 10, 2009 at 10:41 AM, vicky mehta...@gmail.com wrote: example: n=10,k=10 ans:1 n=30,k=7 ans: 475020 On Oct 10, 9:51 am, vicky mehta...@gmail.com wrote: u have to color n similar balls with k diff. colors , such that every color must be used atleast once find the no. of ways --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Here is the right answer: Find the sum of missing numbers. Call it S (this is a easy to do). Now the two missing numbers are such that one is =S/2 and the other is S/2 Have two variables S1 and S2, traverse the array and add everything = S/2 to S1 and S/2 to S2. Now First number = (Sum of numbers from 1 to S/2) - S1 Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 O(n) time and O(1) space. On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan karthiksinga...@gmail.com wrote: well..will this work? x + y = SUM(1:N+2) - SUM(array) = a x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b so (a^2 - b) = 2xy so xy = (a^2-b)/2 = k (say) now, x + (k/x) = a x^2 + k = ax (x, y) = (a +/- sqrt(a^2-4k))/2 I may not have written the equations correctly (need coffee !!!) but you get the general idea... solve a quadratic equation to solve for (x+y) = a and (x^2 + y^2) = b - Karthik --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
Try {2, 1}
On Sat, Aug 1, 2009 at 11:45 AM, Devi G devs...@gmail.com wrote:
@Vivek
I had told abt tat border case already once..
Suppose the two missin numbers are greater than n, then m==0 when exitin
the loop.
So they will be n+1 and n+2 only.
in case, one of the missin numbers is greater than n, then m==1, and can be
simply found by subtracting the (array_sum+x[0] ) from (sumof 1 to n+2)
numbers.
Hope it works..
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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: Pigeon Hole Principle
Ouch I got the question completely wrong assuming the inner disc is continuous.Sorry for the confusion. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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: Pigeon Hole Principle
When both disks are not painted continuous 'equivalence' does not work. Because in your proof when one half does not give the answer, you just take take the other half and align it. But for arbitrary configuration, when one configuration does not work, you cannot align the other half. It will not fit unless the sections are painted symmetrically. On 3/25/07, Vishal [EMAIL PROTECTED] wrote: I did assume that the outer disk is painted half (contiguous) red and half white. However the 'equivalence' should do the trick and the same proof applies. As far as Stone's proof goes, I did not understand - For each inner section,no matter white or black ,there is 100 color-matching events. Can somebody explain? ~Vishal On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: Ouch I got the question completely wrong assuming the inner disc is continuous.Sorry for the confusion. On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: On 3/25/07, Rajiv Mathews [EMAIL PROTECTED] wrote: On 3/25/07, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Could you elaborate please. His proof contains, Quote: If r = R-r, match half1 with Red half of outer disk. Total matching = r + 100 - R + r = 100 - R + 2*r How do you justify this if the sections aren't contiguous? I think the proof elaborated by _stone_ is correct and apt. There is an equivalence It is simple.Just consider, Half1 = All the sections in the outer disc painted red (This is not continuous. But nothing prevents you from assuming a non-continuous 100 red sections as a logical half) Half2 = All the sections in the outer disc painted white Now with this interpretation, read his proof. Just remember that when you say 'half' of inner disc it means the sections corresponding to the half in the outer disc as defined above. This is the key to establish equivalence). Regards, Prunthaban -- Regards, Rajiv Mathews --~--~-~--~~~---~--~~ 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: Pigeon Hole Principle
Hi, The proof given by Vishal is correct irrespective of the arrangement (which he himself did not realize). If you see carefully his proof does not assume anything about sections colored continuously. His proof assumes only one thing Half of them are red and half of them are white Half does not mean it should be continuous. So the proof still works correct unmodified even if the halves are not continuous. Regards, Prunthaban On 3/25/07, Karthik Singaram L [EMAIL PROTECTED] wrote: yes...but that does not mean that you can assume that the 100 reds and 100 whites are contiguous blocks.It just says that the outer disk has a sum of the 100 reds and 100 whites and does not say that they are contiguous. --~--~-~--~~~---~--~~ 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: The Game
Try googling for Josephus Permutation On 2/22/07, Manish Garg [EMAIL PROTECTED] wrote: hi, I m posting a game, its like this: Suppose N people are playing the game. All of them are numbered from 1 to N. They all sit in a circle such that their numbering order is also maintained, so that the last person (numbered N) sits adjacent to the first person (numbered 1). Now an integer K is chosen. Starting from the first person, every Kth person is removed from the game, and whenever a person is removed, the counting begins again from the next person onwards. This continues until only 1 person remains. He is declared the winner. so N and k is given to us and we have to tell that who will be the last person. can any one plz help me to find the solution of this problem. I tried and got the solution by simulatio. taking an array of length N and the go on removing untill one person remains. if any other good method is there plz help me... -- Manish Kumar Garg M.Tech IIT Kharagpur, 09732657489 [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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: (need help) How to solve this random number generatioin problem?
Then you will get only the following numbers (1*7)/5 = 1 (2*7)/5 = 2 (3*7)/5 = 4 (4*7)/5 = 5 (5*7)/5 = 7 What you will do to get 3 and 6? On 2/1/07, pramod [EMAIL PROTECTED] wrote: Why can't we simply take the 1..5 random number, multiply by 7 and divide by 5. --~--~-~--~~~---~--~~ 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: whats the fastest way to find the odd man out?
XOR is the best computationally as well as space complexity. On 1/16/07, Satish [EMAIL PROTECTED] wrote: Hangjin Zhang wrote: Do an XOR on all numbers. The resulte is the number which occurs only once HZ On 12/30/06, Abhishek [EMAIL PROTECTED] wrote: Hi, Suppose I have a sequence of numbers in which every number occurs twice in the sequence except one. Whats the fastest way of finding that number which occurs only once? With Regards, Abhishek S I am not sure how XOR will be defined on numbers. Also, calculating XOR for any sequence of N numbers where N is not known a priori is computationally very expensive. A simple way could be to keep additional large bit vector memory. where we have 2 bits per number. For each number visited in sequence, mark the corresponding bit b1 as visited once. On revisiting, mark another corresponding bit b2. At the end, just look for the number that has only b1 set and b2 unset. SKM --~--~-~--~~~---~--~~ 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: Kurukshetra Online Programming Contest
Hi all, This does not look like a 'open to all' contest. The registration asks for college information! Can CEG guys confirm? Regards, Prunthaban On 12/26/06, Aravind Narayanan [EMAIL PROTECTED] wrote: Hello There! College of Engineering, Guindy announces the Kurukshetra Online Programming Contest as a part of it's Inter-departmental Tech. Fest, Kurukshetra. The event is your opportunity to compete with the World's best coders with a prize money that's worth the fight! The event is to be held on December 31th and is open to all. Date: 31-December-2006 Timings : 14:00hrs - 20:00 hrs Team Size : 3 Prizes Worth 2000 USD!! Do visit http://kurukshetra.org.in/ and register for the event. -- Aravind Narayanan [EMAIL PROTECTED] --~--~-~--~~~---~--~~ 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: Copying Books from Sphere online judge.
Yep. It is Binary Search. Greedy will not work :-( My quick thuoght had dome flaws... :( On 10/11/06, Arunachalam [EMAIL PROTECTED] wrote: Can you please state your greedy solution? I have solved these kind of problems on the online judges using binary search. This problem is no exception to the binary search. regards Arunachalam. On 10/10/06, Prunthaban Kanthakumar [EMAIL PROTECTED] wrote: hi, Giving a short thought... I think an O(n^2) greedy solution will work. Regards, Prunthaban On 10/10/06, Amal [EMAIL PROTECTED] wrote: http://www.spoj.pl/problems/BOOKS1/ For this problem I have a Dp solution of O(n^3) and another solution based on Binary search.Is there a better DP (dynamic Programming ) soln of order less than n^3 . Amal.http//ww.livejournal.com/users/arunachalam --~--~-~--~~~---~--~~ 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: Nice question!! (part 2)
If the optimal internal containing a[m] contains oneelement, it is simply a[m] But here the optimal interval containing a[m] is not a[m] alone. 4 alone gives you 4 * 4 = 16 Including 7, you will get (4 + 7) * 4 = 44 Then include 8, (4+7+8) * 4 = 76 Now try including 2, (2+4+7+8) * 2= 21*2 = 42 (This is lesser than previous one) So the optimum one including 4 is,is 4+7+8 Now appy the same O(n) procedure to both small half arrays... On 9/26/06, GoCooL [EMAIL PROTECTED] wrote: Prunthaban Kanthakumar wrote: Hi, The proposed solution does not talk about multiplication. It talks about the sum alone. The sum is simply a[m]. Of course you need to muliply later.But that does not affect the correctness of the solution!For this set:51 2 4 7 8what would the steps be? As you mentioned, if initially, the sum is all we care about, then:a[l..m-1] = 1 + 2 = 3a[m] = 4a[m+1..r] = 7 + 8 = 15Where do we go from here?- GoCooL --~--~-~--~~~---~--~~ 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: Nice question!! (part 2)
Hi, The proposed solution does not talk about multiplication. It talks about the sum alone. The sum is simply a[m]. Of course you need to muliply later.But that does not affect the correctness of the solution! Regards, Prunthaban On 9/24/06, GoCooL [EMAIL PROTECTED] wrote: This is the original thread: http://groups.google.com/group/algogeeks/browse_frm/thread/b6e605273a09d79d/#But since that thread has been closed by the manager as a result ofwhich I'm unable to post to it anymore, I'm creating this new thread. The original problem states -the value of some period of human life is proportional to the sum ofthe emotional values of the days in the given period, multiplied by thesmallest emotional value of the day in it. And in Post# 12 of the above mentioned thread, this is a part of thesolution suggested.* Divide the elements in the middle: a[l..m-1], a[m], a[m+1..r]* Recursively compute the optimal interval entirely in the left half * Recursively compute the optimal interval entirely in the right half* Compute the optimal interval containing a[m]* Return the best of the three intervals The key step for efficiency is computing the optimal interval containing a[m] in linear time. Here's a greedy solution. * If the optimal internal containing a[m] contains one element, it is simply a[m]So, for this example - 1, 2, 4, 7, 8a[m] being suggested is 4 when clearly it should be -a[m] = 4 = 4 * 4 = 16.Am I missing something from the proposed solution here?GoCooL --~--~-~--~~~---~--~~ 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: MineSweeper...
I didn't look into thecorrectness of the algorithm.
But I can tell you the reason for that compilation error
Visual Studio 6.0 does not follow ANSI standards!
Especially the scope of the loop variable 'i' is the thing which causes compilation error for you.
In ANSI C (or gcc for that matter),
if you declare 'i' like this,
for(int i=0;in;i++)
{}
outside the loop you cannot access it. Its scope is limited within the loop.So if you want to declare another loop, again you have to say,
for(int i=0;in;i++)
{
}
Suggestions:
1. If possible use some gcc based compilers available for windows (There are mny available for windows).
2. Try cygwin
3. Use Visual Studio 2003 or 2005 (The 'bug' is fixed in these version ;))
Regards,
Prunthaban
On 8/26/06, Iman [EMAIL PROTECTED] wrote:
today i was solving this problemhttp://acm.uva.es/p/v101/10189.html
and i after i solve it i compile it with Microsoft Visual Studio 6 andi've got the resultscorrect butafter i send it to Valladolid judge it say it has a compiler error!!! omy godanyway need your helps
tanx in advance--/*problem No. 10189 of the Valladolid the problem gets input as a mine field it gets mine fields in this way first it gets two numbers that first integer is number of lines
the second integer is number of columnsand the program stops when the user inputs these both two numbers 0 after getting this N and M it gets a N*M matrix of characters in this matrix the character '*' defines a mine and character '.'
define empty space Output : Field #Number of field that is going to being processed next lines is a M*N matrix that '*' characters will apear in theoutput exactly like inputs and instead of empty space we put numbers in those
cells the numbers define numbers of mines cross that cell obviously the minimum is 0 and the Maximum could be is 8*/#include iostream.hvoid checker(int f1[][100],int m,int n)
{ int Currtemp = 0; // Number of mines across the current cell shouldbeing zero at first of counting for each cell for(int i=1;i=m;i++) { for(int j=1;j=n;j++)
{ Currtemp= 0; if(f1[i][j]!=-1) { if(f1[i-1][j-1] == -1) //1 Currtemp++;
if(f1[i-1][j] == -1) //2 Currtemp++; if(f1[i-1][j+1] == -1) //3 Currtemp++;
if(f1[i][j-1] == -1) //4 Currtemp++; if(f1[i][j+1] == -1) //5 Currtemp++;
if(f1[i+1][j-1] == -1) //6 Currtemp++; if(f1[i+1][j] == -1) //7 Currtemp++;
if(f1[i+1][j+1] == -1) //8 Currtemp++; f1[i][j] = Currtemp; } }
}}int main(){ int RawField[100][100] = {0}; // Our raw mine field int field[100][100] = {0}; // Our mine field int NOF = 0; // Number of Current field int m = 0; // Number of lines
int n = 0; // Number of columns char temp; //this help us to convert chars to int cinmn; while((m!=0)||(n!=0)) { NOF++; for(int i=0;i100;i++)
{ for(int j=0;j100;j++) RawField[i][j] = 0; } for(i=1;i=m;i++) { for(int j=1;j=n;j++)
{ cintemp; if(temp=='*') { RawField[i][j] = -1;
} } } coutField #NOF:endl; checker(RawField,m,n);
for(i=1;i=m;i++) { for(int j=1;j=n;j++) { if(RawField[i][j] !=-1) coutRawField[i][j];
else cout'*'; } coutendl; } coutendl;
cinmn; } return 0;}
--~--~-~--~~~---~--~~
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: Nice question!!
When you have a nice algorithm from Googmeister in O(n log n) why try something else...?
On 7/5/06, mg [EMAIL PROTECTED] wrote:
#includestdio.hstruct key {int min;doublesum;};
int main(int argc,char **argv){int n,i,j,k;int start=0,end=0;double currentValue=0,eValue=0;struct key opt[10];int a[10];while ( scanf(%d,n) != EOF )
{start = 0;end = 0;eValue = 0;for ( i =0;in;i++){scanf(%d,a[i]);opt[i].min = a[i];opt[i].sum = a[i];
currentValue = opt[i].sum * opt[i].min;if ( currentValue eValue ){eValue = currentValue;start= i;end= i;}}
for( i = 0; i = n -1; i++ ){for (j=i+1;j=n-1;j++){if(opt[i].min a[j])opt[i].min = a[j];opt[i].sum += a[j];currentValue = opt[i].sum * opt[i].min;
if ( currentValue eValue ){eValue = currentValue;start= i;end= j;}}}printf(%.0f\n%d %d\n,eValue,start+1,end+1);
}}I am trying to get a better soln.This one is n^2.
--~--~-~--~~~---~--~~
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: DataStructure - Push,Pop Find_Min in O(1)
You can't sort using push-pop-findmin.
@rajivmat
push --- 4, 5, 6, 1, 3, 2- minarray = {0,3}pop -- 4, 5, 6, 1, 3 - minarray = {0,3}pop -- 4, 5, 6, 1- minarray = {0,3}find_min = 3rd element = 1pop -- 4, 5, 6 - minarray{0} =(Now top = mintop so minarray is also popped)
find_min = 0th element = 4pop -- 4, 5 - minarray ={0}find_min = 0th element = 4
Regards,
Prunthaban
--~--~-~--~~~---~--~~
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] DataStructure - Push,Pop Find_Min in O(1)
Hi All,One of my friends asked me this questions:Can you frame a Stack like Data structure where Push,Pop and find_min takes O(1) time?Well...A Stack is already doing a good job by giving O(1) for Push and Pop.
We need a method to make it support O(1) find_min too.Let me share my ideas. Comments are welcome.Double Array (Linked lists can also be used) based Stack
1. There will be two arrays A and MIN2. There will be two indices top and topmin;Here the array MIN stores the minimum value occured so far.Let me show the implementation.Method: Push(Val)
{A[top] = ValIf(top = 0) MIN[topmin] = top topmin = topmin + 1Else If(A[MIN[topmin-1]] Val) MIN[topmin] = top topmin = topmin + 1top = top + 1}Method: Pop{
If(top == 0) throw exceptiontop = top - 1If(MIN[topmin-1] == top) topmin = tommin - 1return A[top]}Method: find_min{return A[MIN[topmin-1]]}(I think there is no need for a proof for why it always return the minimum)
Note: In the worst case... both arrays will be equal in size. This occurs when you push numbers in descending order.Is there a better wayRegards,Prunthaban
--~--~-~--~~~---~--~~
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: tree lock problem
Hi All,If I have understood the question correctly, then this will work! DFS is recursive. So even though our tree has no parent pointers, we will get such a 'pointer for free' , due to recursion. (Remember recursion allows you to pass information from child to parent) So a single highly pruned DFS is suffice.Algo:boolean DFS(node) (Let X be a global boolean which says whether N is in that subtree or not. Initially X is false) 1. If (node is locked) return true; 2. flag = false;1. for each a in child b = DFS(a) If (X == true) return b; flag = flag OR b 2. If (a == N) X = true; 3. return flagIf DFS(root) returns false, you can lock N(My algo will terminate if the root is locked. But.. considering the interviewer's hint... to count the no. of locks, we cannot stop at the root) We need to prove two facts to establish the correctness of my algorithm.FACT 1: DFS(root) will not return false if the DFS returns without reaching N. Proof: DFS(root) will return without reaching N only if it encounters a locked node which is an ancestor of N. In this case the returned value is 'true'. Also we use flag = flag OR bSo only one 'true' is enough to make the return value true. When N is not countered at all, the return value will be that of flag. So the return value is always true if N is not encountered in the DFS.FACT 2: DFS(root) will return false, if all descendents and ancestors of N are not locked. Proof: When we explore the subtree rooted at N, the value of X will be false (note: X is set to True only after N's descendent's are visited). So, the return value from N will be false only if all descendents are not locked. Once X is set to true... (as long as the ancestor is not locked) the return value will be the return value from N.Regards,Prunthaban --~--~-~--~~~---~--~~ 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: tree lock problem
Hi all,I think there can be one more solution... where a BFS is folowed by DFS works.Algo 2:IsLockable(Node N){ queue Q; if(root is not locked) Q.insert(root); while(!Q.empty()) {
Node n = Q.removeHead(); if(n == N) return DFS(n); for(each child a of N) If(a is not locked) Q.insert(a); } return false;
}DFS(node){ for (each child a of node) if(a is locked || DFS(a) == true) return true; return false;}This will be better than my algo 1, for some trees.
Regards,Prunthaban
--~--~-~--~~~---~--~~
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: tree lock problem
Hi all,The third solution is... (I hope there will not be any fourth ;) )Two BFSs...1. The first BFS will traverse all unlocked nodes (same as solution one)...2. The second BFS will traverse until one locked node is encountered. Hey, guys... this is boring...It is always possible to convert between DFS and BFS.It is just about time complexity..As we know...2 BFSs work better.Regards,Prunthaban --~--~-~--~~~---~--~~ 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: An interesting problem from Code4bill second round
No, dp[2] is 100 110 010 011 This is3 * dp[1] + 1 = 3 * 1 + 1 = 4 steps Regards, Prunthaban
[algogeeks] Re: rules for round3 code4bill
Use console application System calls are calls which modify the process,etc (Like fork() in unix) Win32 calls - (Accessing win32 api - Don't include windows.h) On 2/3/06, prick [EMAIL PROTECTED] wrote: hi everyoneRules for round 3 code4billf.Headers/Libraries: You can use the standard libraries headers that come with the compiler set. Please don't use any system calls orWIN32 calls.can u tell what type of project should i start with in visual c++ 20005?1: CLR console application2: CLR empty project or3: win32 applicationor any otherand what do they mean when they say 'system call' or 'win32 call'
[algogeeks] Re: An interesting problem from Code4bill second round
Hi all, Sorry for the late reply. Anyway here is the solution... I want to note down 2 facts... 1. With 1 one the maximum reachable is 1 2. Any sequence of move is exactly reversible. You just have to toggle the bits in reverse order. Now the solution. With n ones.. 1. Use first n-1 ones toreach 2^(n-1) - 1 2. Set 2^(n-1) th one. 3. Reverse the first step. 4. Now use the n-1 ones to set the next 2^(n-1) - 1 ones! So for n, we do three times n-1 and 1 more step to set the 2^(n-1)th element. So the dp solution is, dp[1] = 1 dp[n] = 3 * dp[n-1] + 1 Regards, Prunthaban
[algogeeks] Re: Abacus Online Programming Contest - January 29th
Inmost of the good opcs(Including Abacus)only the best code survives the tests! You can't write bubble sort when asked for a sorting algorithm! It will simply time out! So provided only the best algo survives, the next criteria for evaluation will obviously be How quick u came out with the idea and implemented it... This is the second criteria for Abacus! The third criteria provided by themGetting identical time of submissions for all problems is not going to happen So forget this! PS: There is a place where you can win by writing bubblesort instead of quicksort! Check www.topcoder.com:) Bye.
[algogeeks] Integer Partiotioning into 'n' equal sets!
Hi Guys, I havea question... Integer partitioning is NP-complete. So partitioning a set into 'n' number of equal sets is also in NP (When n=2 we get the first one). But Integer partitioning has a nice DP solution (though not in P)... Similarly does Integer partitioning into 'n' equal sets also has a DP solution? If not... what could be the best approach?
[algogeeks] Bitwise 06
Hi guys, I think most of you knew it... Incase some of you don't know... Bitwise is BACK! http://www.bitwise.iitkgp.ernet.in/ Check out on Jan 1st to register...
