[algogeeks] Re: Puzzle
Correct me if i m wrong !!! Number of matches of each team = 14. Let team A,B,C,D qualify for semifinal. 1.maximum number of matches A can win = 14 (all played ) 2.maximum number of matches B can win = 12 (all played except played with team A) 3.maximum number of matches C can win = 10 (all played except played with team A and B) 4.maximum number of matches D can win = 8 (all played except played with team A , B and C) so 8 should be the minimum number of matches to be won to proceed for semis !!! On May 27, 6:10 pm, Aakash Johari aakashj@gmail.com wrote: Is it the minimum required matches to ensure for semifinals? On Fri, May 27, 2011 at 6:06 AM, Rishabh Maurya poofiefoo...@gmail.comwrote: suppose bottom 4 teams have won least matches and upper 4 teams have won equal number of matches ... 1 - x 2 - x 3 - x 4 - x 5 - 6 6 - 4 7 - 2 8 - 0 total matches are 56 and let upper four teams have won x matches each so x = (56-(6+4+2+0))/4 x = 11 so in this way to ensure qualification to semi finals team must win 11 matches ... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT 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] Re: Puzzle
@Arpit Any four team cannot win 12 matches in total. ...Rishabh is wid right answer that is ( 11 ). Hence any team winning its any 11 out of 14 matches ensures its entry to semis. But not below 11 its entry to semi will depend on other team performance. On May 27, 7:11 pm, Arpit Mittal mrmittalro...@gmail.com wrote: @rishabh : in your solution u have taken scores of last 4 teams as 6 4 2 0. what if i take 2 2 2 2 then the ans would be 56-(2+2+2+2)/4 = 12...!!! and i can also take the scores of last 4 teams as 6 4 4 2 then the ans would be 56-(6+4+4+2)/4 = 10!!! so how you can say it would be 11? On Fri, May 27, 2011 at 6:52 AM, Rishabh Maurya poofiefoo...@gmail.comwrote: No , you are wrong .. problem statement says how many matches should a teams win to ensure its qualification , their no word like minimum or maximum ... 8 gets wrong if following situation arises 1 - 9 2 - 9 3 - 9 4 - 9 5 - 8 6 - 6 7 - 4 8 - 2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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: Puzzle
so here we go Let A loses two of its matches to (one to B and one to C). Let B loses two of its matches to(one to A and one to C) Then C loses two of its matches to(one to A and one to C). Now. team D, if it ever plays with (A,B,C) will loses..hence minimum number o matches it is going to loses is 6. Hence, D could only won 8 matches... A--12 B--12 C--12 D--8 The same thing goes to if the above team instead of loosing its two matches to two different team loses to a same team. Hence (12,12,12,12) cannot be feasible !!! I hope it is clear. On May 27, 7:27 pm, Arpit Mittal mrmittalro...@gmail.com wrote: @Vishwakarma it is now ok that 11 should be the answer, but why any 4 teams cannot win 12 matches in total... for that they have to score 12*4 = 48 points out of 56. then wats the problem. i know how it is coming 11 now, but i am replying back for the doubt i have in a line u just mentioned in your post... :) On Fri, May 27, 2011 at 7:23 AM, vishwakarma vishwakarma.ii...@gmail.comwrote: @Arpit Any four team cannot win 12 matches in total. ...Rishabh is wid right answer that is ( 11 ). Hence any team winning its any 11 out of 14 matches ensures its entry to semis. But not below 11 its entry to semi will depend on other team performance. On May 27, 7:11 pm, Arpit Mittal mrmittalro...@gmail.com wrote: @rishabh : in your solution u have taken scores of last 4 teams as 6 4 2 0. what if i take 2 2 2 2 then the ans would be 56-(2+2+2+2)/4 = 12...!!! and i can also take the scores of last 4 teams as 6 4 4 2 then the ans would be 56-(6+4+4+2)/4 = 10!!! so how you can say it would be 11? On Fri, May 27, 2011 at 6:52 AM, Rishabh Maurya poofiefoo...@gmail.com wrote: No , you are wrong .. problem statement says how many matches should a teams win to ensure its qualification , their no word like minimum or maximum ... 8 gets wrong if following situation arises 1 - 9 2 - 9 3 - 9 4 - 9 5 - 8 6 - 6 7 - 4 8 - 2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send emailtoalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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: Puzzle
correction---it was typo mistake ... Team C loses to(one to A and one to B) On May 27, 7:44 pm, vishwakarma vishwakarma.ii...@gmail.com wrote: so here we go Let A loses two of its matches to (one to B and one to C). Let B loses two of its matches to(one to A and one to C) Then C loses two of its matches to(one to A and one to C). Now. team D, if it ever plays with (A,B,C) will loses..hence minimum number o matches it is going to loses is 6. Hence, D could only won 8 matches... A--12 B--12 C--12 D--8 The same thing goes to if the above team instead of loosing its two matches to two different team loses to a same team. Hence (12,12,12,12) cannot be feasible !!! I hope it is clear. On May 27, 7:27 pm, Arpit Mittal mrmittalro...@gmail.com wrote: @Vishwakarma it is now ok that 11 should be the answer, but why any 4 teams cannot win 12 matches in total... for that they have to score 12*4 = 48 points out of 56. then wats the problem. i know how it is coming 11 now, but i am replying back for the doubt i have in a line u just mentioned in your post... :) On Fri, May 27, 2011 at 7:23 AM, vishwakarma vishwakarma.ii...@gmail.comwrote: @Arpit Any four team cannot win 12 matches in total. ...Rishabh is wid right answer that is ( 11 ). Hence any team winning its any 11 out of 14 matches ensures its entry to semis. But not below 11 its entry to semi will depend on other team performance. On May 27, 7:11 pm, Arpit Mittal mrmittalro...@gmail.com wrote: @rishabh : in your solution u have taken scores of last 4 teams as 6 4 2 0. what if i take 2 2 2 2 then the ans would be 56-(2+2+2+2)/4 = 12...!!! and i can also take the scores of last 4 teams as 6 4 4 2 then the ans would be 56-(6+4+4+2)/4 = 10!!! so how you can say it would be 11? On Fri, May 27, 2011 at 6:52 AM, Rishabh Maurya poofiefoo...@gmail.com wrote: No , you are wrong .. problem statement says how many matches should a teams win to ensure its qualification , their no word like minimum or maximum ... 8 gets wrong if following situation arises 1 - 9 2 - 9 3 - 9 4 - 9 5 - 8 6 - 6 7 - 4 8 - 2 -- You received this message because you are subscribed to the Google GroupsAlgorithm Geeks group. To post to this group, send emailtoalgoge...@googlegroups.com.To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send emailtoalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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: Puzzle
correction--Then C loses two of its matches to(one to A and one to C). to Then C loses two of its matches to(one to A and one to B) . On May 27, 7:44 pm, vishwakarma vishwakarma.ii...@gmail.com wrote: so here we go Let A loses two of its matches to (one to B and one to C). Let B loses two of its matches to(one to A and one to C) Then C loses two of its matches to(one to A and one to C). Now. team D, if it ever plays with (A,B,C) will loses..hence minimum number o matches it is going to loses is 6. Hence, D could only won 8 matches... A--12 B--12 C--12 D--8 The same thing goes to if the above team instead of loosing its two matches to two different team loses to a same team. Hence (12,12,12,12) cannot be feasible !!! I hope it is clear. On May 27, 7:27 pm, Arpit Mittal mrmittalro...@gmail.com wrote: @Vishwakarma it is now ok that 11 should be the answer, but why any 4 teams cannot win 12 matches in total... for that they have to score 12*4 = 48 points out of 56. then wats the problem. i know how it is coming 11 now, but i am replying back for the doubt i have in a line u just mentioned in your post... :) On Fri, May 27, 2011 at 7:23 AM, vishwakarma vishwakarma.ii...@gmail.comwrote: @Arpit Any four team cannot win 12 matches in total. ...Rishabh is wid right answer that is ( 11 ). Hence any team winning its any 11 out of 14 matches ensures its entry to semis. But not below 11 its entry to semi will depend on other team performance. On May 27, 7:11 pm, Arpit Mittal mrmittalro...@gmail.com wrote: @rishabh : in your solution u have taken scores of last 4 teams as 6 4 2 0. what if i take 2 2 2 2 then the ans would be 56-(2+2+2+2)/4 = 12...!!! and i can also take the scores of last 4 teams as 6 4 4 2 then the ans would be 56-(6+4+4+2)/4 = 10!!! so how you can say it would be 11? On Fri, May 27, 2011 at 6:52 AM, Rishabh Maurya poofiefoo...@gmail.com wrote: No , you are wrong .. problem statement says how many matches should a teams win to ensure its qualification , their no word like minimum or maximum ... 8 gets wrong if following situation arises 1 - 9 2 - 9 3 - 9 4 - 9 5 - 8 6 - 6 7 - 4 8 - 2 -- You received this message because you are subscribed to the Google GroupsAlgorithm Geeks group. To post to this group, send emailtoalgoge...@googlegroups.com.To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send emailtoalgoge...@googlegroups.com. To unsubscribe from this group, send email toalgogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Arpit Mittal 6th Semester, Indian Institute of Information Technology,Allahabad Email : arpitmittal.ii...@gmail.com rit2008...@iiita.ac.in Contact : +91-8853049787 Let every man be respected as an individual and no man idolized. -- 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: Round Robin Schedulling Problem
@Anshuman sir
There is mistake in above code :
u wrote -- ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i -
L[IN[i]] + 1);
I think it should be -- ans[IN[i]] = curtime + (D[i] - last - 1) *
rem + (IN[i]- L[IN[i]] + 1);
correct me if i m wrong
On May 26, 9:17 am, anshu mishra anshumishra6...@gmail.com wrote:
L[i] tells how many elements D[j] less than D[i] such that j i ;
for this u have to use BIT, segment tree, or any balanced BST(balanced
implies to avoid the worst case that is o(n^2));
rem = n;
curtime = 0;
last = 0;
for (i = 0; i n;)
ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
curtime += (D[i] - last) * rem;
i++;
rem--;
while (i n D[i] == D[i-1])
{
ans[IN[i]] = ans[IN[i-1]] + 1; i++;
rem--;
}
last = d[i-1];
}
curtime = total time till the iteration in which last event(which has burst
time just less than current event) has been completed.
--
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: Round Robin Schedulling Problem
wait !! wait !!
@Anshuman sir...u have left few case ;
I corrected ur code and got accepted at spoj.
Here is the correct code;
//here F[] is array which got 3 fields ( element value(same as ur D[]
array) , its index in original input(same as ur IN[] array) , number
of elements less than it till its poistion in original array(same as
ur L[] array) )
long long int rem = n;
long long int curtime = 0;
long long int last = 0;
long long int *Ans = new long long int[n];
for(int i=0;in;){
Ans[F[i].idx] = curtime + ((long long
int)(F[i].data-last-1))*rem +
(long long int)(F[i].idx-F[i].rep+1);
curtime += ((long long int)(F[i].data - last))*rem;
i++;
rem--;
while(in F[i].data == F[i-1].data){
Ans[F[i].idx] = Ans[F[i-1].idx] + (long long
int)(F[i].idx -
F[i-1].idx - (F[i].rep - F[i-1].rep));
i++;
rem--;
}
last = (long long int)F[i-1].data;
}
On May 26, 8:15 pm, vishwakarma vishwakarma.ii...@gmail.com wrote:
@Anshuman sir
There is mistake in above code :
u wrote -- ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i -
L[IN[i]] + 1);
I think it should be -- ans[IN[i]] = curtime + (D[i] - last - 1) *
rem + (IN[i]- L[IN[i]] + 1);
correct me if i m wrong
On May 26, 9:17 am, anshu mishra anshumishra6...@gmail.com wrote:
L[i] tells how many elements D[j] less than D[i] such that j i ;
for this u have to use BIT, segment tree, or any balanced BST(balanced
implies to avoid the worst case that is o(n^2));
rem = n;
curtime = 0;
last = 0;
for (i = 0; i n;)
ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
curtime += (D[i] - last) * rem;
i++;
rem--;
while (i n D[i] == D[i-1])
{
ans[IN[i]] = ans[IN[i-1]] + 1; i++;
rem--;
}
last = d[i-1];
}
curtime = total time till the iteration in which last event(which has burst
time just less than current event) has been completed.
--
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: number of inversions
u can use BIT(Binary Indexed Tree) to count inversions. I prefer this becoz it is much easier to code BIT than merge sort. On Apr 24, 4:25 am, سهراب ابوالفتحی sohrab.abolfa...@gmail.com wrote: Let A[1..n] be an array of n distinct numbers. If i j and A[i] A[j], then the pair (i,j) is called an inversion of A. Give an algorithm that determines the number of inversions in any permutation on n elements in tetta(n lg n) worst-case time. (with Modify merge sort.) -- 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: Need help on Divide and Conquer Algorithm
complexity : O(n) + O(nlogn)
Sweety wrote:
Question :Let A[1..n] be an array of integers. Design an efficient
divide and conquer algorithm to determine if A contains a majority
element, i.e an element appears more than n/2 times in A. What is the
time complexity of your algorithm?
Answer:
a[1..n] is an array
int majorityElement(int a[], int first, int last)
{
If (first = = last)
{
return a[first]; // Array has one element and its count = 1
and it is major element
}
mid= (first+last)/2;
(majorL,countL)= majorityElement(a,first,mid);
(majorR,countR)= majorityElement(a,mid
+1,last);
n = total elements in an array;
If(majorL==majorR)
return(countL+countR);
else
{
If(countLcountR)
return(majorL,countL);
elseif(countL countR)
return(majorR,countR);
else
return(majorL,majorR);
}
if(countLn/2)
temp1=majorL;
if(countRn/2)
temp2=majorR;
If(temp1 = = temp2)
return temp1;
elseif(countLcountR)
return temp1;
else (countRcountL)
return temp2;
else
return -1;
}
int main()
{
int a[8] = {2,3,2,2,4,2,2,2};
int first =1;
int last=8; //change the value of last when the array
increases or decreases in size
int x = majorityElement(a,first,last);
if(x= = -1)
printf(“No Majority Element”)
else
Majority element = 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.
[algogeeks] Re: Need help on Divide and Conquer Algorithm
I can post solution of this complexity if you want !!
On Apr 15, 12:19 am, vishwakarma vishwakarma.ii...@gmail.com wrote:
complexity : O(n) + O(nlogn)
Sweety wrote:
Question :Let A[1..n] be an array of integers. Design an efficient
divide and conquer algorithm to determine if A contains a majority
element, i.e an element appears more than n/2 times in A. What is the
time complexity of your algorithm?
Answer:
a[1..n] is an array
int majorityElement(int a[], int first, int last)
{
If (first = = last)
{
return a[first]; // Array has one element and its count = 1
and it is major element
}
mid= (first+last)/2;
(majorL,countL)= majorityElement(a,first,mid);
(majorR,countR)= majorityElement(a,mid
+1,last);
n = total elements in an array;
If(majorL==majorR)
return(countL+countR);
else
{
If(countLcountR)
return(majorL,countL);
elseif(countL countR)
return(majorR,countR);
else
return(majorL,majorR);
}
if(countLn/2)
temp1=majorL;
if(countRn/2)
temp2=majorR;
If(temp1 = = temp2)
return temp1;
elseif(countLcountR)
return temp1;
else (countRcountL)
return temp2;
else
return -1;
}
int main()
{
int a[8] = {2,3,2,2,4,2,2,2};
int first =1;
int last=8; //change the value of last when the array
increases or decreases in size
int x = majorityElement(a,first,last);
if(x= = -1)
printf(“No Majority Element”)
else
Majority element = 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.
[algogeeks] Re: Need help on Divide and Conquer Algorithm
Let A be the input array;
Now algorithm is follows;
struct leave{
int cand;
int count;
};
struct leave tree[120];
void build(int s,int e,int node ,int *A)
{
if(s == e){
tree[node].cand = A[s];
tree[node].count = 1;
return;
}
else{
int mid = (s+e)1;
build(s,mid,2*node,A);
build(mid+1,e,2*node+1,A);
if(tree[2*node].cand == tree[2*node+1].cand){
tree[node].cand = tree[2*node].cand;
tree[node].count = tree[2*node].count +
tree[2*node+1].count;
}
else{
if(tree[2*node].count tree[2*node+1].count){
tree[node].cand = tree[2*node].cand;
tree[node].count = tree[2*node].count -
tree[2*node+1].count;
}
else{
tree[node].cand = tree[2*node+1].cand;
tree[node].count = tree[2*node+1].count -
tree[2*node].count;
}
}
}
}
int main()
{
//read Array A
build(1,n,1);
//sort array A
int val = Tree[1].cand;
//perform binary search on sorted array A
//if its count is strictly greater than n/2 then yes else no
On Apr 15, 12:28 am, LALIT SHARMA lks.ru...@gmail.com wrote:
Yes , I also need the same...Thanks for the help .
On Fri, Apr 15, 2011 at 12:52 AM, vishwakarma
vishwakarma.ii...@gmail.comwrote:
I can post solution of this complexity if you want !!
On Apr 15, 12:19 am, vishwakarma vishwakarma.ii...@gmail.com wrote:
complexity : O(n) + O(nlogn)
Sweety wrote:
Question :Let A[1..n] be an array of integers. Design an efficient
divide and conquer algorithm to determine if A contains a majority
element, i.e an element appears more than n/2 times in A. What is the
time complexity of your algorithm?
Answer:
a[1..n] is an array
int majorityElement(int a[], int first, int last)
{
If (first = = last)
{
return a[first]; // Array has one element and its count = 1
and it is major element
}
mid= (first+last)/2;
(majorL,countL)= majorityElement(a,first,mid);
(majorR,countR)= majorityElement(a,mid
+1,last);
n = total elements in an array;
If(majorL==majorR)
return(countL+countR);
else
{
If(countLcountR)
return(majorL,countL);
elseif(countL countR)
return(majorR,countR);
else
return(majorL,majorR);
}
if(countLn/2)
temp1=majorL;
if(countRn/2)
temp2=majorR;
If(temp1 = = temp2)
return temp1;
elseif(countLcountR)
return temp1;
else (countRcountL)
return temp2;
else
return -1;
}
int main()
{
int a[8] = {2,3,2,2,4,2,2,2};
int first =1;
int last=8; //change the value of last when the array
increases or decreases in size
int x = majorityElement(a,first,last);
if(x= = -1)
printf(“No Majority Element”)
else
Majority element = x;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group. To post to this group, send email
toalgoge...@googlegroups.com.
To unsubscribe from this group, send email
toalgogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Lalit Kishore Sharma,
IIIT Allahabad (Amethi Capmus),
6th Sem.
--
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: Need help on Divide and Conquer Algorithm
example : let the array be { a,b,a,b,c,d,e,d,d,e,f};
now...
step 1 :pick any 2 different element and remove from the array till
array contains only same elements or any single element ...// dis
is implemented wid the above mentioned funtion build()
if there is any element whose occurence is greater than n/2 than u ll
always get an unique value left after step 1 , it wont depend on the
way u select 2 different element n removing them.
On Apr 15, 12:43 am, vishwakarma vishwakarma.ii...@gmail.com wrote:
Let A be the input array;
Now algorithm is follows;
struct leave{
int cand;
int count;};
struct leave tree[120];
void build(int s,int e,int node ,int *A)
{
if(s == e){
tree[node].cand = A[s];
tree[node].count = 1;
return;
}
else{
int mid = (s+e)1;
build(s,mid,2*node,A);
build(mid+1,e,2*node+1,A);
if(tree[2*node].cand == tree[2*node+1].cand){
tree[node].cand = tree[2*node].cand;
tree[node].count = tree[2*node].count +
tree[2*node+1].count;
}
else{
if(tree[2*node].count tree[2*node+1].count){
tree[node].cand = tree[2*node].cand;
tree[node].count = tree[2*node].count -
tree[2*node+1].count;
}
else{
tree[node].cand = tree[2*node+1].cand;
tree[node].count = tree[2*node+1].count -
tree[2*node].count;
}
}
}
}
int main()
{
//read Array A
build(1,n,1);
//sort array A
int val = Tree[1].cand;
//perform binary search on sorted array A
//if its count is strictly greater than n/2 then yes else no
On Apr 15, 12:28 am, LALIT SHARMA lks.ru...@gmail.com wrote:
Yes , I also need the same...Thanks for the help .
On Fri, Apr 15, 2011 at 12:52 AM, vishwakarma
vishwakarma.ii...@gmail.comwrote:
I can post solution of this complexity if you want !!
On Apr 15, 12:19 am, vishwakarma vishwakarma.ii...@gmail.com wrote:
complexity : O(n) + O(nlogn)
Sweety wrote:
Question :Let A[1..n] be an array of integers. Design an efficient
divide and conquer algorithm to determine if A contains a majority
element, i.e an element appears more than n/2 times in A. What is the
time complexity of your algorithm?
Answer:
a[1..n] is an array
int majorityElement(int a[], int first, int last)
{
If (first = = last)
{
return a[first]; // Array has one element and its count =
1
and it is major element
}
mid= (first+last)/2;
(majorL,countL)= majorityElement(a,first,mid);
(majorR,countR)= majorityElement(a,mid
+1,last);
n = total elements in an array;
If(majorL==majorR)
return(countL+countR);
else
{
If(countLcountR)
return(majorL,countL);
elseif(countL countR)
return(majorR,countR);
else
return(majorL,majorR);
}
if(countLn/2)
temp1=majorL;
if(countRn/2)
temp2=majorR;
If(temp1 = = temp2)
return temp1;
elseif(countLcountR)
return temp1;
else (countRcountL)
return temp2;
else
return -1;
}
int main()
{
int a[8] = {2,3,2,2,4,2,2,2};
int first =1;
int last=8; //change the value of last when the array
increases or decreases in size
int x = majorityElement(a,first,last);
if(x= = -1)
printf(“No Majority Element”)
else
Majority element = x;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group. To post to this group, send
emailtoalgoge...@googlegroups.com. To unsubscribe from this group,
send email toalgogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Lalit Kishore Sharma,
IIIT Allahabad (Amethi Capmus),
6th Sem.
--
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: Dp problem
Here i proposed an algorithm. correct me if i am wrong !!
int main()
{
int N; //number of boards
int W; // number of workers
int smax = 0;
cin N W;
int *A = new int[N];
for(int i=0;iN;i++){
cin A[i];
smax += A[i];
}
int m = *max_element(A ,A+N);
for(int i=m;i=smax;i++){
int sum = 0;
int w = 1;
for(int j=0;jN;j++){
if(sum+A[j] = i){
sum += A[j];
}
else{
sum = A[j];
w++;
}
}
if(w=W){
cout i \n;
break;
}
}
return 0;
}
rajat ahuja wrote:
You have to paint N boards of length {B1, B2, B3… BN}. There are K painters
available and you are also given how much time a painter takes to paint 1
unit of board. You have to get this job done as soon as possible under the
constraints that any painter will only paint continuous sections of board,
say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 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.
