Re: [algogeeks] Re: Printing all inversions in an array
^ Exactly! Dipit Grover B.Tech in Computer Science and Engineering - lVth year IIT Roorkee, India -- 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] Printing all inversions in an array
Since the number of inversions are of order n^2 in the worst case, so should be the complexity of printing them apparently. -- 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] Codeforces Problem
Hi, you just need to see the figure carefully and derive a simple formula here. The tiles are all regular hexagons and The figure shown is for the given sample case where a=2,b=3,c=4, thereby implying that each side of the hexagonal tile(say, x) satisfies : x*(cos 30) = 1/2; Thanks Digo -- 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] [Offtopic] Wedding Invitation
http://yeees.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.
Re: [algogeeks] Maximize XOR
http://discuss.joelonsoftware.com/default.asp?interview.11.614716 -- 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 : GAMECOIN
I did it using dp. dp[i] = probability that Roger wins in 'i' or less tosses. dp[i]= dp[i-1] + when he wins in exactly 'i' tosses The second term above means that the last three tosses have got to be THH or else he would have won in less than 'i' tosses which has already been counted in dp[i-1] . So the second term would mean (1-dp[i-3])*1/2 * 1/2 * 1/2 . Now the probability that Dave wins for any 'i' would be (1-dp[i]). -- Dipit Grover B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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: sort 2D array
sorry I mean 1 variable per each array -- 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: sort 2D array
@Shady : you would definitely need two index variables for each array I feel. -- 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: sort 2D array
@ all k-way people : I dont get it how the complexity would be O(m*n) . I just went through the algo and I feel that one would need to find the minimum element among the head-elements of all individual row-arrays, for all the resulting m*n elements. I say so since we may not necessarily have a sorted column-array(array formed by taking the head elements of each row-array) each time we look for the min element. Please correct me if I am wrong. @Lucifer- yeah we need to only traverse the columns till the current column. -- 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] sort 2D array
@Lucifer : I came up with a similar algorithm as yours but I dont
understand your complexity analysis : " sum over all i (1 to M} { i*(M+N-i)
} " .
Shouldnt it be " M * sum over all i(1 to N) {(M+N-i)} " ? M= no of
columns, N= no of rows . Since we always have the min element at the 0th
column of the next row for each element of the current row.
--
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: Best algorithm possible
@Lucifer (Regarding your latest approach) - I guess you meant string based comparison sort in the first step, as in 9 would be greater than 10. The special case seems correct but I doubt the complexity being nlog n, considering the special case. -- 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: Find Largest number in log(n)
^it cant get better than O(n) apparently. Just applying max-heapify once would not yield the max element. You need to construct a heap for it, which is no less than O(n). -- 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] No of triangles
http://susam.in/downloads/mathematics/theorems/integer-triangles-with-fixed-perimeter.pdf -- Dipit Grover B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] NUMBER OF MST ?
http://en.wikipedia.org/wiki/Cayley%27s_formula -- 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] NUMBER OF MST ?
Mistake noted! Haste makes waste indeed. -- 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] NUMBER OF MST ?
^ we need to count "each permutation and its reverse" together as one possibility since both would result in identical mst. -- Dipit Grover B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] NUMBER OF MST ?
Shouldnt it be (n!)/2 ? Equivalent to permutation of n distinct numbers except that we need to count each permutation once, since for any permutation, there would also be a reverse permutation that would result in an identical mst in the given scenario. -- Dipit Grover B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] Finding the indexes of a repeated element??
Using binary search, first find the first occurrence of x. Using this first occurrence run another binary search to find the last occurrence of x. -- 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: Modular arithmetic + Combinatorics
Thats really cool! Thanks Dave :) -- 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] Modular arithmetic + Combinatorics
Hi everyone, I am stuck at places where I need to find lets say Binomial_coefficient(1000,10) mod 1000 000 007 . What is the best way to do this, assuming we donot have sufficient memory to use the naive approach : (n,r) = (n-1,r) + (n-1,r-1) . -- Dipit Grover B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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: Amazon online test
25*16*9 / 3! or 5C3 * 5 *4 *3 = 600 On Sat, Sep 24, 2011 at 6:21 PM, Ankur Garg wrote: > Deoki nandan > > In MCQ there were options as well ?? is it ? > > Also were questions in MCQ only from coding or OOPS,DBMS,OS etc also are > part of those ? > > Regards > > > On Sat, Sep 24, 2011 at 6:13 PM, Aamir Khan wrote: > >> @shiv : Correct Answer should be : 5C3 X 5 X 4 X3 = 600 >> >> >> >> >> >> Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee >> >> >> -- >> 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. > -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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: Problem on overflow
Oops, I just saw that Dave had already corrected it. Net problem, sorry guys! On Sat, Aug 27, 2011 at 11:02 PM, dipit grover wrote: > I think you just need to reverse the comparison operators in Dave's earlier > post > > > On Sat, Aug 27, 2011 at 10:59 PM, Dave wrote: > >> @Abishek: I was brain-dead in my earlier posting. Let me try again: >> >> If either number is zero, the sum will not overflow. >> If the numbers have different signs, the sum will not overflow. >> If both numbers are positive, overflow will occur if b > maxint - a. >> If both numbers are negative, overflow will occur if b < -maxint - a - >> 1. >> >> Dave >> >> On Aug 27, 12:18 pm, Abhishek wrote: >> > @Dave: i didn't understand, >> > suppose a=3, b=31000 and MaxInt=32000; >> > you are saying if (MaxInt-a)>=b; then overflow will occur. but here >> > condition is not satisfying. >> > plz explain. >> >> -- >> 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. >> >> > > > -- > Dipit Grover > B.Tech in CSE > IIT Roorkee > > -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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: Problem on overflow
I think you just need to reverse the comparison operators in Dave's earlier post On Sat, Aug 27, 2011 at 10:59 PM, Dave wrote: > @Abishek: I was brain-dead in my earlier posting. Let me try again: > > If either number is zero, the sum will not overflow. > If the numbers have different signs, the sum will not overflow. > If both numbers are positive, overflow will occur if b > maxint - a. > If both numbers are negative, overflow will occur if b < -maxint - a - > 1. > > Dave > > On Aug 27, 12:18 pm, Abhishek wrote: > > @Dave: i didn't understand, > > suppose a=3, b=31000 and MaxInt=32000; > > you are saying if (MaxInt-a)>=b; then overflow will occur. but here > > condition is not satisfying. > > plz explain. > > -- > 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. > > -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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]
Because for the first iteration, while loop isnt executed and hence flag isnt set any value. But the condition for checking value in flag variable is evaluated when it doesnt have any initialised value. Hence the runtime error. On Sat, Aug 27, 2011 at 3:18 PM, Amol Sharma wrote: > why it is happening soi mean it is initialised later > > what's the reason that it is giving run time error if not initialized at > start > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://youtube.com/amolsharma99> > > > > > > On Sat, Aug 27, 2011 at 3:13 PM, dipit grover wrote: > >> <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. > -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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]
Just initialize your flag variable. On 8/27/11, UTKARSH SRIVASTAV wrote: > why is it giving run time error > > http://www.ideone.com/DhIX0 > > -- > *UTKARSH SRIVASTAV > CSE-3 > B-Tech 3rd Year > @MNNIT ALLAHABAD* > > -- > 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. > > -- Dipit Grover B.Tech in CSE IIT Roorkee -- 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.
