Re: [algogeeks] How to store largest N values efficiently
Wouldn't a heap be ideal for this ? On Mon, Jul 11, 2011 at 3:35 PM, John Reid j.r...@mail.cryst.bbk.ac.ukwrote: I have a procedure that generates N x M values sequentially. I want to store the N largest ones and discard the others. Obviously I can store all the values in a vector, sort it when it is full and then choose the top N values. Is there a more efficient way using a data structure that just stores the top N values as the procedure goes along? Typically M is 1,000 and N is anywhere from 1,000 to 50,000. I have no prior expectation on how the N largest values are distributed amongst the N x M values. I'm working in C++ with the STL and boost libraries. Thanks for reading this, John. -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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: How to store largest N values efficiently
You can use priority_queue in STL. The size needs to be limited to N elements. At any point the the N elements in the heap will give the largest N elements processed so far. On Mon, Jul 11, 2011 at 4:41 PM, John Reid j.r...@mail.cryst.bbk.ac.ukwrote: On 11/07/11 12:07, abhijith reddy wrote: Wouldn't a heap be ideal for this ? I thought it might. Do I just need to limit the heap to size 2 * N to avoid storing values I'll never need? Thanks, John. On Mon, Jul 11, 2011 at 3:35 PM, John Reid j.r...@mail.cryst.bbk.ac.uk mailto:j.r...@mail.cryst.bbk.**ac.uk j.r...@mail.cryst.bbk.ac.uk wrote: I have a procedure that generates N x M values sequentially. I want to store the N largest ones and discard the others. Obviously I can store all the values in a vector, sort it when it is full and then choose the top N values. Is there a more efficient way using a data structure that just stores the top N values as the procedure goes along? Typically M is 1,000 and N is anywhere from 1,000 to 50,000. I have no prior expectation on how the N largest values are distributed amongst the N x M values. I'm working in C++ with the STL and boost libraries. Thanks for reading this, John. -- 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 mailto:algogeeks@**googlegroups.com algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@__google**groups.com http://googlegroups.com mailto:algogeeks%**2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com **. For more options, visit this group at http://groups.google.com/__**group/algogeeks?hl=enhttp://groups.google.com/__group/algogeeks?hl=en http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@**googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/**group/algogeeks?hl=enhttp://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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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] GATE 2011 C Ques
p[3] = 'E' p[1] = 'A' p[3]-p[1] = 4 ? On Sat, Jul 2, 2011 at 7:10 PM, KK kunalkapadi...@gmail.com wrote: 10. What does the following fragment of C-program print? char c[] = GATE2011; char *p =c; printf(%s, p + p[3] - p[1]); (A) GATE2011 (B) E2011 (C) 2011 (D) 011 Answer: - (C) why is p[3] - p[1] returning 4 -- 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] Algorithmic Pioneers
+1 On Fri, Jun 24, 2011 at 1:06 PM, rizwan hudda rizwanhu...@gmail.com wrote: Add Donald Knuth, Rajeev Motwani, Manindra agrawal, Richard Karp, Vijay V Vazirani to the list. Peter is no doubt a great algorithm champion, and so is ACRush. But they are definetely not the pioneers of the algorithms field, you can probably remove them from list of pioneers. Thanks, Rizwan. On Fri, Jun 24, 2011 at 12:15 PM, radha krishnan radhakrishnance...@gmail.com wrote: Include Euler !!! On Fri, Jun 24, 2011 at 12:11 PM, Vishnutej Mylavarapu mylavarapu.vishnu...@gmail.com wrote: You can add AC Rush too.. On Fri, Jun 24, 2011 at 11:27 AM, rajeev bharshetty rajeevr...@gmail.com wrote: @ankit Thanks for the suggestion , I ahve Updated to include petr Mitrichev :) On Fri, Jun 24, 2011 at 11:19 AM, ankit sablok ankit4...@gmail.comwrote: very nice man nice collection add Petr Mitrichev to this collection On Fri, Jun 24, 2011 at 11:14 AM, rShetty rajeevr...@gmail.comwrote: Collection of Algorithmic Pioneers can be Found here http://openprobe.blogspot.com/2011/06/pioneers-in-algorithm-deisgn-and.html Suggestion for addition of more Pioneers are welcome . -- 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. -- *-Vishnutej Mylavarapu.* -- 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. -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- 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] EOF in Python for SPOJ
while(1): try: # code # # except EOFError: break On Wed, May 25, 2011 at 8:41 PM, Vishnutej mylavarapu.vishnu...@gmail.comwrote: Hello everyone, I'm new to python.How can I check the EOF for inputs in SPOJ? Thanks in advance!! -Vishnutej -- 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] EOF in Python for SPOJ
A Byte of Python - Freely available online. http://docs.python.org/library/; - Python Library Reference. On Wed, May 25, 2011 at 8:52 PM, Vishnutej Mylavarapu mylavarapu.vishnu...@gmail.com wrote: Thnx a lot abhijith.. Do you have any links for tutorials for beginners? On Wed, May 25, 2011 at 8:42 PM, abhijith reddy abhijith200...@gmail.comwrote: while(1): try: # code # # except EOFError: break On Wed, May 25, 2011 at 8:41 PM, Vishnutej mylavarapu.vishnu...@gmail.com wrote: Hello everyone, I'm new to python.How can I check the EOF for inputs in SPOJ? Thanks in advance!! -Vishnutej -- 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. -- *-Vishnutej Mylavarapu.* WebRep Overall rating -- 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] Candy_splitting in GCJ
Let *E(n)* be the *expected* number of hits needed sort *'n'* *misplaced*numbers. The optimal strategy is to hold the numbers that are already in place and shuffle the remaining. Now after a shuffle assume that x numbers are still out of place. Hence we get the following recurrence. E(n) = Sum[ ((nCx * !x)/n!) * E(x) ] x=0 ... N Where !x is the number of de-arrangementshttp://en.wikipedia.org/wiki/Derangementof x. Hope this helps. On Mon, May 9, 2011 at 9:51 PM, Rahul Singal rahulsinga...@gmail.comwrote: abhijith can you explain , how you got E(n) = N , Thanks in advance Rahul Singal -- 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]
O(N^3) DP
-
char str[MAX];
int dp1[MAX][MAX],dp2[MAX][MAX];
int isPalin(int low,int high)
{
if(low=high) return 1;
if(dp1[low][high]!=-1) return dp1[low][high];
return dp1[low][high]=(str[low]==str[high])?isPalin(low+1,high-1):0;
}
int minCuts(int low,int high)
{
if(isPalin(low,high)) return 0;
if(dp2[low][high]!=-1) return dp2[low][high];
int ans=1e9;
for(int i=low;ihigh;i++)
ans=min(ans,1+minCuts(low,i)+minCuts(i+1,high));
return dp2[low][high]=ans;
}
-
On Fri, May 6, 2011 at 4:23 PM, sourabh jakhar sourabhjak...@gmail.comwrote:
You are given a large string. You need to cut the string into chunks such
that each substring that you get is a palindrome. Remember that each 1
length string is always a palindrome. You need to find the minimum number of
cuts that you need to make such that each substring is a palindrome.
http://www.careercup.com/question?id=8972527
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
dp1[i][j] will hold 1/0 depending upon whether string str[i...j] is a
palindrome or not.
Now let dp2[i][j] be the minimum number of cuts required to split it into
palindromes.
if str[i...j] is a palindrome then '0' cuts are required.
To get the number of cuts required for str[i...j] we try all possible
positions between i j and take minimum of all.
On Fri, May 6, 2011 at 8:23 PM, sourabh jakhar sourabhjak...@gmail.comwrote:
can you explain the logic
On Fri, May 6, 2011 at 8:02 PM, abhijith reddy
abhijith200...@gmail.comwrote:
O(N^3) DP
-
char str[MAX];
int dp1[MAX][MAX],dp2[MAX][MAX];
int isPalin(int low,int high)
{
if(low=high) return 1;
if(dp1[low][high]!=-1) return dp1[low][high];
return dp1[low][high]=(str[low]==str[high])?isPalin(low+1,high-1):0;
}
int minCuts(int low,int high)
{
if(isPalin(low,high)) return 0;
if(dp2[low][high]!=-1) return dp2[low][high];
int ans=1e9;
for(int i=low;ihigh;i++)
ans=min(ans,1+minCuts(low,i)+minCuts(i+1,high));
return dp2[low][high]=ans;
}
-
On Fri, May 6, 2011 at 4:23 PM, sourabh jakhar
sourabhjak...@gmail.comwrote:
You are given a large string. You need to cut the string into chunks such
that each substring that you get is a palindrome. Remember that each 1
length string is always a palindrome. You need to find the minimum number of
cuts that you need to make such that each substring is a palindrome.
http://www.careercup.com/question?id=8972527
--
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, 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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reading Huge input from the terminal in least time.
You could read input character by character using getchar_unlocked() untill you hit a space or new line or EOF. Alternatively you read the whole input at once using fread_unlocked() and then process it as per your need. On Wed, Apr 20, 2011 at 7:41 AM, shubham shubh2...@gmail.com wrote: Hello Geeks, Suppose we have a 2-d array arr[1000][1000] capable of storing 10^6 elements in it. Input is supplied one row at a time. Then what is the best possible way to read this much data in the least amount of time as scanf() or cin takes a lot of time? -- 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: prime number using Sieve of Eratosthenes
cont int MAX = 10005;
bool isPrime[MAX];
void sieve()
{
int lim=sqrt(MAX);
/* Initially Mark all numbers as Prime */
for(int i=2;iMAX;i++)
isPrime[i]=1;
for(int i=2;i=lim;i++)
if(isPrime[i])/* for each Prime */
for(int j=2*i;jMAX;j+=i)/* Cross out all multiples of i */
isPrime[j]=false;
}
On Mon, Mar 21, 2011 at 5:41 PM, rohit scofiel...@rediffmail.com wrote:
i just want to know , when we make a program how update array after
deleting alternate element.
On Mar 21, 4:37 pm, Anurag atri anu.anurag@gmail.com wrote:
what did you not understand in this ?
On Mon, Mar 21, 2011 at 4:59 PM, rohit scofiel...@rediffmail.com
wrote:
genrate prime number using Sieve of Eratosthenes method
explanation is herehttp://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
pls help me out
--
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.
--
Regards
Anurag Atri
--
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] Another maths problem
17^13 is odd 13*17 is odd so isn't the answer simply 2 ? On Thu, Mar 17, 2011 at 8:25 PM, saurabh singh saurab...@gmail.com wrote: Find the smallest divisor of 17^13+13*17... PS:please dont say 1 -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- Saurabh Singh B.Tech (Computer Science) 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. -- 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] Link list Problem
copy data from the next node and then delete that next node. Say you need to delete 3 1 - 2 - 3 - 4 - 5 1 - 2 - 4 - 4 - 5 * Now delete node which is next to '*'. On Sun, Mar 13, 2011 at 10:23 PM, UMESH KUMAR kumar.umesh...@gmail.comwrote: hi Given a singly Link list but Head of the List is unknown so my question is that How to delete a given node from the List??? -- 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] SPOJ DP : SUMITR
algorithm isn't required for C++ 4.0.*. The same code will give Compile
Error in C++ 4.3 and above
On Tue, Mar 8, 2011 at 10:42 PM, Logic King crazy.logic.k...@gmail.comwrote:
Well tried,
i have got the correct answer after working on it for almost 2 hours
here is my code
#includeiostream
using namespace std;int a[100][100];main(){int
t,n,i,j;cint;while(t--){cinn;for(i=0;in;i++){for(j=0;j=i;j++)cina[i][j];}for(i=n-2;i=0;i--){for(j=0;j=i;j++){a[i][j]+=max(a[i+1][j],a[i+1][j+1]);}}couta[0][0]\n;}}
246 bytes in c++.i got it AC :)
one amazing thing i found in my code, while reducing number of bytes,
i.e.in my code max function is working even without using Algorithm header
filei dont know why it is working but it is workingif anyone
know the reason for this then please share it
Thank you,
Logic King
On Mon, Mar 7, 2011 at 8:25 PM, Wladimir Tavares wladimir...@gmail.comwrote:
This my code:
#include stdio.h
#define R(i,b) for(i=0;ib;i++)
#define D(i,a) for(i=a;i=0;i--)
#define I(d) scanf(%d,d);
main(){int t,n,i,j,m[100][100];I(t)
while(t--){I(n)R(i,n)R(j,i+1)I(m[i][j]) D(i,n-2)R(j,i+1)m[i][j] += m[i+1][j]
m[i+1][j+1]?m[i+1][j]:m[i+1][j+1];printf(%d\n,m[0][0]);}}
297 bytes!
On Mon, Mar 7, 2011 at 11:45 AM, Wladimir Tavares
wladimir...@gmail.comwrote:
I create some macros like this:
#define R(i,a,b) for(i=a;ib;i++)
#define D(i,a,b) for(i=a;i=b;i--)
#define I(d) scanf(%d,d);
But i don't get the accepted in this problem!
On Sun, Mar 6, 2011 at 1:55 PM, Logic King
crazy.logic.k...@gmail.comwrote:
i solved the problem on spoj based on DP i am getting the solution right
but i am exceeding the following restriction
Take care about your fingers, do not use more than *256* bytes of
code.
http://www.spoj.pl/problems/SUMITR/
My code is--
#includestdio.h
int arr[100][100];
int main()
{
int tc,n,max,i,j;
scanf(%d,tc);
while(tc--)
{
scanf(%d,n);
for(i=0;in;i++)
{
for(j=0;j=i;j++)
scanf(%d,arr[i][j]);
}
for(i=n-2;i=0;i--)
{
for(j=0;j=i;j++)
{
max=(arr[i+1][j]arr[i+1][j+1])?arr[i+1][j]:arr[i+1][j+1];
arr[i][j]=arr[i][j]+max;
}
}
printf(%d\n,arr[0][0]);
}
return 0;
}
how can i reduce my my code length so that it doesn't exceed 256
bytespl help !!
--
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.
--
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: Spoj Problem : Small Factorials
http://zobayer.blogspot.com/2010/03/small-bigint-library.html On Fri, Feb 4, 2011 at 10:24 PM, Rahul Verma rahulverma@gmail.comwrote: @jeeva Can you pls explain me in detail or some link to the tutorial of string manipulation in C++. I googled about it but most of the links are in Python Javascript. On Feb 4, 9:29 pm, subramania jeeva subramaniaje...@gmail.com wrote: Use string multiplication. :) Cheers ~ Jeeva ~ On Fri, Feb 4, 2011 at 9:49 PM, Rahul Verma rahulverma@gmail.com wrote: Hi Group, Let me help to solve this problem of SPOJ https://www.spoj.pl/problems/FCTRL2/ The approach to solve the problem is very easy and I'm confused that how to store such a large no. like 100! in a variable using C++ Language. Thanx Regards, Rahul Verma -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2Bunsubscribe@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.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 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] first larger element in unsorted array...
simple dp
void solve(int *arr,int sz)
{
int ans[sz];
ans[sz-1]=-1;
for(int i=sz-2;i=0;i--)
{
if(arr[i]arr[i+1]) ans[i]=arr[i+1];
else ans[i]=ans[i+1];
}
for(int i=0;isz;i++)
printf(%d ,ans[i]);
}
On Sun, Jan 30, 2011 at 10:00 PM, ritu ritugarg.c...@gmail.com wrote:
You are given an array (unsorted) and for every element i, find the
first occurance of an element j (in the remaining array) that is
greater than or equal to i. If no such j occurs then print -1.
Eg: Input--- A={1,3,5,7,6,4,8}
Output--- 3 5 7 8 8 8 -1
Time Complexity:O(n)
Space Complexity: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.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 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: Good Maths Question
I remember solving this @ spoj Here is an O(1) solution #!/usr/bin/python def solve(n): val=1 for i in range(1,9): val*=(n+i) return float((n+9)/9.0-(40320.0/val)) cases=int(raw_input()) while(cases): cases-=1 n=int(raw_input()) print '%.6f'%(solve(n)) On Tue, Jan 25, 2011 at 6:28 PM, juver++ avpostni...@gmail.com wrote: @Skywalker your solution is ok. But is works only for the small value of n. Cause amount of desired numbers with n=10^6 digits is very big )) After n=27 there is a regularity for the ratio. However, here is more simplified dp - http://codepad.org/9bzFzDtV -- 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.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 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] Complexity Help ??
O(2^n)
On Sat, Jan 22, 2011 at 8:58 PM, Decipher ankurseth...@gmail.com wrote:
fun(n)
{
if(n=2)
return (1);
else
return ((fun(n-1)*fun(n-2));
}
find the order of complexity .
--
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.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 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] power of 3
Below is code for modular exponentation in general
// (a^b)%c
int modexp(int a,int b,int c)
{
int ans=1;
while(b)
{
if(b1) ans=(ans*a)%c;
a=(a*a)%c;
b=1;
}
return ans;
}
On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote:
int l = 0, r = ...;
while (l r) {
int m = (l + r) / 2;
int p = power(3, m);
if (p M) r = m - 1;
else if (p M) l = m + 1;
else print 3^m = M;
}
--
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.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 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] power of 3
O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
M=3^x
We binary search on x and then compute 3^x in log(x) time using
exponentiation. Hence the complexity.
On Fri, Jan 21, 2011 at 5:50 PM, snehal jain learner@gmail.com wrote:
@juvir++
it was mentioned in question not to use log or power. isnt there any
approach using bitwise operators
On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh mans.aus...@gmail.comwrote:
this will be O(log(n) * log(n)) solution
On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy abhijith200...@gmail.com
wrote:
Below is code for modular exponentation in general
// (a^b)%c
int modexp(int a,int b,int c)
{
int ans=1;
while(b)
{
if(b1) ans=(ans*a)%c;
a=(a*a)%c;
b=1;
}
return ans;
}
On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote:
int l = 0, r = ...;
while (l r) {
int m = (l + r) / 2;
int p = power(3, m);
if (p M) r = m - 1;
else if (p M) l = m + 1;
else print 3^m = M;
}
--
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.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 algogeeks@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 algogeeks@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 algogeeks@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 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] power of 3
@snehal .. misread it .. my apologies.
On Fri, Jan 21, 2011 at 5:56 PM, abhijith reddy abhijith200...@gmail.comwrote:
O(lg(n)*lg(n)) is the complexity of the solution ! Not the solution.
M=3^x
We binary search on x and then compute 3^x in log(x) time using
exponentiation. Hence the complexity.
On Fri, Jan 21, 2011 at 5:50 PM, snehal jain learner@gmail.comwrote:
@juvir++
it was mentioned in question not to use log or power. isnt there any
approach using bitwise operators
On Fri, Jan 21, 2011 at 5:24 PM, Manmeet Singh mans.aus...@gmail.comwrote:
this will be O(log(n) * log(n)) solution
On Fri, Jan 21, 2011 at 4:29 PM, abhijith reddy
abhijith200...@gmail.com wrote:
Below is code for modular exponentation in general
// (a^b)%c
int modexp(int a,int b,int c)
{
int ans=1;
while(b)
{
if(b1) ans=(ans*a)%c;
a=(a*a)%c;
b=1;
}
return ans;
}
On Fri, Jan 21, 2011 at 3:27 PM, juver++ avpostni...@gmail.com wrote:
int l = 0, r = ...;
while (l r) {
int m = (l + r) / 2;
int p = power(3, m);
if (p M) r = m - 1;
else if (p M) l = m + 1;
else print 3^m = M;
}
--
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.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 algogeeks@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 algogeeks@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 algogeeks@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 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: Google Question
I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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] value of n
binary search on n On Fri, Apr 30, 2010 at 10:15 PM, Amit Agarwal lifea...@gmail.com wrote: how do I compute n from this equation. n 8lg(n) -- 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.
Re: [algogeeks]
I guess she was asking that the per query complexity should be better that O(n). If that is the case then you can use any of these Simple RMQ O(sqrt(n)) Segment/Interval Trees O(lgn) Binary Indexed Trees O(lgn) On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: With only this info and without preprocessing , you need to scan all the N integers in the list atleast once. Hence cannot be better than O(n). If preprocessing is allowed you can compute the answers for all n^2 pairs of x1,x2 and when some one asks , return the corresponding list. In that case it would be better that O(n). !! -Rohit On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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.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.
Re: [algogeeks] Implementation of Algorithms
First learn a language of your choice and then you can start solving over there On Wed, Mar 31, 2010 at 12:05 AM, scanfile rahul08k...@gmail.com wrote: I am new to the world of programming. I have to solve the problems on the spoj.pl , but I have no idea that how I would implement the algorithms in any programming language. Pls help me. I need a solution of this problem. Thanx scanfile -- 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.
Re: [algogeeks]
@All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? If you want to do the operation just once then it cannot be done faster than O(n) time. Even the mentioned data structures require atleast O(n) amount of preprocessing. All the mentioned algorithms are available here http://www.topcoder.com/tc?d1=tutorialsd2=alg_indexmodule=Static Hope it helps On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee dona.1...@gmail.comwrote: The list of N integers is not sorted. The solution is asked for a particular query. @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment Interval trees*. May be you opted for the correct data structure. Please give the algorithm. @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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.
Re: [algogeeks] You have to count the occurances of all words in a document. You are given a method chat * GetNextWord, that returns the next word from the document.
You can use a TRIE .. Structure can be something like this
struct trie
{
int count; // no of occurences
char *child[SIZE];
};
when ever u insert ( it will take just O(length) time) .. just increment
count by 1
For each query (also O(length) time) the no of occurrences of the word will
be count of the last character
Hope it helps
On Sat, Feb 27, 2010 at 5:35 PM, piyushgoe...@gmail.com wrote:
Maintain a hash of word to freq. Keep adding words and incrementing their
frequencies while reading the documents
Pigol
On Feb 27, 2010, at 5:10 PM, vijay auvija...@gmail.com wrote:
You have to count the occurances of all words in a document. You are
given a method chat * GetNextWord, that returns the next word from the
document.
- Which datastructure can be userd to achieve this
-
--
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.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.
Re: [algogeeks] Re: gcd sum function
Yes i have .. and i have the worst time in the rank page :)
On Fri, Jan 29, 2010 at 8:51 PM, fundoonick fundoon...@yahoo.co.in wrote:
I tried this problem using the method of solving using eulerphi values.
I calculate values of eulerphi in O(nlogn) and then use them to calculate
gcdsum using a similar algorithm in O(nlogn).
For n=10^6, O(nlogn) should work, but I am getting TLE on SPOJ.
Cant figure out why.
Has anyone solved it using values of eulerphi?
On Fri, Jan 29, 2010 at 6:14 AM, ShingRay masterrays...@gmail.com wrote:
https://www.spoj.pl/problems/GCDEX/
#include cstdio
using namespace std;
const int N = 101;
bool sifted[N] = {};
int primes[8], nprimes = 0;
long long gcdsum[N];
int main()
{
int n;
gcdsum[0] = 0;
gcdsum[1] = 1;
for (int i = 2; i N; ++i)
{
if (!sifted[i])
{
primes[nprimes++] = i;
gcdsum[i] = 2*i-1;
}
for (int j = 0; j nprimes i*primes[j] N; ++j)
{
sifted[i*primes[j]] = true;
if (i%primes[j] == 0)
{
int n = i*primes[j], m = 0, nn = 1;
while (n%primes[j] == 0)
n /= primes[j], ++m, nn *=
primes[j];
gcdsum[i*primes[j]] =
((m+1)*nn-m*(nn/primes[j])) * gcdsum[n];
break;
}
gcdsum[i*primes[j]] = gcdsum[i]*gcdsum[primes[j]];
}
}
for (int i = 1; i N; ++i)
gcdsum[i] += gcdsum[i-1]-i;
while (scanf(%d, n), n)
printf(%lld\n, gcdsum[n]);
}
--
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.
Please access the attached hyperlink for an important electronic
communications disclaimer:
http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
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
algogeeks%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.
[algogeeks] gcd sum function
Hello Let gcdsum[n] = gcd(1,1)+gcd(1,2)+gcd(1,3)+ ... +gcd(n,n) Also gcdsum[n] can be evaluated using : gcdsum[n] = n*sum(eulerphi(d)/d) for all d | n Now to compute all gcdsum values upto n we first need to precompute all eulerphi and then use a sieve like algorithm to make a table of all gcdsum . But can any one tell me a way to compute the gcd sum values without computing phi . Since a table of eulerphi could be made without computing prime numbers, but i am unable to extend this idea. Can any one help ? Thanks ! -- 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.
Re: [algogeeks] A MS QUESTION
*TRIE*: Using a trie we would get a linear time solution but i think the memory requirement would be huge .. On Mon, Dec 14, 2009 at 11:02 PM, vicky mehta...@gmail.com wrote: Given a file with a lot of words (10 million) find out the top 10% most frequently occuring words. -- 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.
[algogeeks] Linear time sieve
I heard that there's a sieve algorithm whose complexity is O(n). Can any give me the pseudo code for that ? Thank u ! -- 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.
Re: [algogeeks] Sum of the Sequence
Thank you so much ! :)
On Fri, Nov 6, 2009 at 11:00 AM, Prunthaban Kanthakumar
pruntha...@gmail.com wrote:
On a related note,
The solution I gave you is to find the nth element in the kth series.
If you want to sum the first 'n' elements of the kth series (call the
function s(n,k)), then it is easy to see that,
*s(n,k) = f(n+1, k+1) - 1*
where f(n+1, k+1) is the (n+1)th element in the (k+1)th series.
This can also be easily done using the summation operator of 'finite
calculus'.
On Fri, Nov 6, 2009 at 10:50 AM, Prunthaban Kanthakumar
pruntha...@gmail.com wrote:
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.com
wrote:
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.
--
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] Sum of the Sequence
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.
