[algogeeks] Re: Array Problem
@amrit,@Pranav and others : Thanks a lot.. On Feb 15, 11:35 am, amrit harry dabbcomput...@gmail.com wrote: @tushar lower bound for sorting an array is nlogn.http://www.bowdoin.edu/~ltoma/teaching/cs231/fall11/Lectures/6-moreso... On Wed, Feb 15, 2012 at 11:16 AM, TUSHAR tusharkanta.r...@gmail.com wrote: That means,,,we have to sort the array first in O(n). Is there any way to sort the array inplace in 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. -- AMRIT -- 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: Array Problem
I think for count it should be count=(int)(k/N), instead of (int)k/5... On Wed, Feb 15, 2012 at 6:00 PM, TUSHAR tusharkanta.r...@gmail.com wrote: @amrit,@Pranav and others : Thanks a lot.. On Feb 15, 11:35 am, amrit harry dabbcomput...@gmail.com wrote: @tushar lower bound for sorting an array is nlogn. http://www.bowdoin.edu/~ltoma/teaching/cs231/fall11/Lectures/6-moreso... On Wed, Feb 15, 2012 at 11:16 AM, TUSHAR tusharkanta.r...@gmail.com wrote: That means,,,we have to sort the array first in O(n). Is there any way to sort the array inplace in 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. -- AMRIT -- 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. -- *Priyatosh Tiwari* *B. Tech. Third Year(CSE)* *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.
[algogeeks] Bread Butter Brain
The mega event Bread, Butter and Brain is going to be held tonight at 7.30pm. This is an individual online event. There will be 15 levels with one question per level The difficulty of the questions increases as you advance to the next level. Questions will involve puzzles, logic, programming, mathematics or a combination of all the above. For further details do visit, http://prayatna.org.in/BB_brain/ Cheers ~ Jeeva ~ -- 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: Bread Butter Brain
Registration Started.1 Rs at stake.Event starts at 7.30 PM today. -- 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: Array Problem
@Pranav: This could fail if N sqrt(maxint) and a sufficient number of A[i] have the same value so that A[A[i]] N*N, which overflows. Dave On Feb 15, 1:08 am, Pranav meetpranav...@gmail.com wrote: Array 'A' contains N elements st A[i] =k N Now, Iterate over the array. Let k=A[i] If A[i] N then k=A[i] mod N go to A[k] and write A[k] = A[k] + N So, lets take a sample array of size 5: 1,2,1,0,4 i=0: k=A[i]=1; A[i] 5; A[1] = A[1] + 5 = A[1] = 7 = A = 1,7,1,0,4 i=1: k=A[i]=7; A[i] 5; k=A[i] mod N = k=2 = A[2] = A[2] + 5 = A=1,7,6,0,4 i=2: k=A[i]=6; A[i] 5; k=A[i] mod N = k=1 = A[1] = A[1] + 5 = A=1,12,6,0,4 i=3: k=A[i]=0; A[i] 5; k=0 = A[0] = A[0] + 5 = A=6,12,6,0,4 i=4: k=A[i]=4; A[i] 5; k=4 = A[4] = A[4] + 5 = A=6,12,6,0,9 I'm using the fact that: (c*n + a) mod n =a Now, while searching, for say i=1, k=A[i] = k=12 count=int(k/5) Let me know if any test case fails. -- 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: spoj
@Utkarsh: yeah it is josephsus problem with a slight change.using a linked list will give u TLE i guess. On Feb 14, 10:36 pm, vickywiz vickywiz...@gmail.com wrote: in 1 2 3 4 5 6...o/p ll b 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
heres a O(n) solution.. correct me if am wrong..
1. In order to get the count in O(1) we need to place the count of each
number in their respective index.So before storing the count we need to
swap the nos. in such a way that all k=n are at their respective
index.This can be done in O(n)
int arr[]={1,2,1,0,4};
int sz=sizeof(arr)/sizeof(int);
int x,y;
for(int i=0;isz;i++)
{
while(arr[i]!=arr[arr[i]])
{
x=arr[i];
y=arr[arr[i]];
arr[i]=y;
arr[x]=x;
}
}
This will take O(n) time ...as for every loop we are setting one number to
its respective index and then moving to the next number.
2. Now set the count to -1 for all i..such that arr[i] equal to i.
for(int i=0;isz;i++)
{
if(arr[i]==i)
arr[i]=-1;
}
3. Now for all the numbers that are 0 ,we need to increment the count in
their respective index.And set their count =0 as there is no such number
for which arr[i]==i.
for(int i=0;isz;i++)
{
if(arr[i]0)
{
arr[arr[i]]--;
arr[i]=0;
}
}
4.Now this array contains the count at their respective index.
int fun(int arr[],int x)
{
return -arr[x];
}
On Wed, Feb 15, 2012 at 10:48 PM, Dave dave_and_da...@juno.com wrote:
@Tushar: If we are going to use A[i] as an index into the array A[],
we must have 0 = A[i] N.
We can use a negative in A[i] to indicate that i occurs -A[i] times.
The code would look something like this:
//preprocessing...
int i, j, m;
for( i = 0 ; i N, ++i )
{
j = A[i];
while( j = 0 )
{
if( A[j] = 0 )
{
m = A[j];
A[j] = -1;
j = m;
if( j = i ) break;
}
else
{
A[j]--;
break;
}
}
}
Here is how this works: For each value of i, if A[i] 0, we already
have processed it, so nothing more is required. Otherwise, suppose
that A[i] has the value j. Then if A[j] 0 then we already have
processed at least one occurrence of j, so we just decrement A[j] to
indicate that an additional value j has occurred in A. But if A[j] =
0, this is the first time j has occurred. We set the value of A[j] to
-1 to indicate that j has occurred once, but before we lose the value
of A[j], we have to process its value. This results in the while loop
to run through the chain of numbers until we get to an entry we
already have processed.
Prerocessing is O(N) because the statement A[j] = -1 in the while loop
can be executed at most k times and A[j]-- can be executed at most N-1
times during all iterations of the for loop. And since one of these is
executed on every iteration of the while loop, the while loop itself
can be executed no more than N+k-1 2*N times during all iterations
of the for loop.
//determining count of number of original A[i] == x...
count = A[x] 0 ? -x : 0;
Dave
On Feb 14, 10:10 pm, TUSHAR tusharkanta.r...@gmail.com wrote:
Given an array of size N having numbers in the range 0 to k where
k=N, preprocess the array inplace and in linear time in such a way
that after preprocessing you should be able to return count of the
input element in O(1).
Please give some idea !!
Thanks..
--
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.
--
*Dheeraj Sharma*
--
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
yeah..we need to calculate some formula On Wed, Feb 15, 2012 at 10:21 PM, pavan pavankri...@gmail.com wrote: @Utkarsh: yeah it is josephsus problem with a slight change.using a linked list will give u TLE i guess. On Feb 14, 10:36 pm, vickywiz vickywiz...@gmail.com wrote: in 1 2 3 4 5 6...o/p ll b 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Dheeraj Sharma* -- 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: TRIE problem
i am getting WA by implementing TRIE .can anyone help me with the test
cases for which the following code is failing.
#includestdio.h
#includestdlib.h
#includestring.h
#includeiostream
#define MAX 26
#define LEN 1000
using namespace std;
struct node
{
char c;
int isterminal;
int no_children;
struct node* children[MAX];
};
struct node* createnode(char ch)
{
struct node* nl=(struct node*)malloc(sizeof(struct node));
if(nl==NULL)
printf(memory allocation error);
else
{
nl-c=ch;
nl-no_children=0;
nl-isterminal=-1;
}
return nl;
}
struct node* insert(char* str,int i,int len,struct node* root)
{
char ch=str[i];
if(i==len)
{
root-isterminal=1;
return root;
}
if(root-children[ch-'a']==NULL || root-children[ch-'a']-
isterminal==-1)
{
struct node* nl=createnode(ch);
root-children[ch-'a']=nl;
root-children[ch-'a']-isterminal=0;
root-no_children++;
}
root-children[ch-'a']=insert(str,i+1,len,root-children[ch-'a']);
return root;
}
int countchildren(struct node* root,char* buffer,int len)
{
int index=0;
static int count=0;
if(root-isterminal==1)
{
printf(%s\n,buffer);
count++;
}
for(int i=0;iMAX;i++)
{
if(root-children[i]!=NULL)
{
buffer[len]=root-children[i]-c;
buffer[len+1]='\0';
countchildren(root-children[i],buffer,len+1);
}
}
return count;
}
int solve(char* str,int i,int len,struct node* root)
{
int c;
char ch=str[i];
char buffer[LEN];
if(ilen)
{
if(root==NULL || root-children[ch-'a']==NULL)
return 0;
else
{
return solve(str,i+1,len,root-children[ch-'a']);
}
}
else
{
strcpy(buffer,str);
c=countchildren(root,buffer,strlen(str));
//printf(count %d\n,c);
return 1;
}
}
int main()
{
struct node* trie=createnode('$');
char str[1000];
int t,k;
scanf(%d,t);
while(t--)
{
scanf(%s,str);
trie=insert(str,0,strlen(str),trie);
}
scanf(%d,k);
for(int i=1;i=k;i++)
{
scanf(%s,str);
printf(Case #%d:\n,i);
if(!solve(str,0,strlen(str),trie))
printf(No match.\n);
}
return 0;
}
On Feb 15, 11:56 am, shady sinv...@gmail.com wrote:
will TRIE be the best solution for this problem ?
Linkhttp://www.spoj.pl/problems/DICT/
--
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.
