[algogeeks] Re: Tug of War
hey utkarsh i can't understand your algorithm cn u explain it
again
On Aug 6, 11:34 pm, UTKARSH SRIVASTAV usrivastav...@gmail.com wrote:
My accepted solution is this and I have told you my logic
#includestdio.h
struct node
{
int data;
int add;
struct node *next;}*front,*rear;
int flag,c;
int fun(int item)
{
struct node *temp,*temp2,*r,*p,*q;
int k,i;
r=(struct node*)malloc(sizeof(struct node));
temp=(struct node*)malloc(sizeof(struct node));
r-next=NULL;
temp-data=item;
temp-add=0;
temp-next=NULL;
c++;
//rear-next=r;
//printf(hi);
// scanf(%d,k);
if(front==NULL)
{
front=temp;
rear=front;
// rear-next=r;
// c++;
// temp2=(struct node *)malloc(sizeof(struct node));
// temp-
}
else if(front-datatemp-data)
{
temp-next=front;
front=temp;
//c++;
}
else if(front-data==temp-data)
{
flag=1;
return 1;
}
else
{
p=front;
while(p-next!=NULLp-next-datatemp-data)
{
p=p-next;
}
if(p-next(p-next-data==temp-data))
{
flag=1;
return 1;
}
if(p-next==NULL)
{
temp-next=p-next;
p-next=temp;
rear=temp;
//c++;
//r=rear;
}
else
{
temp-next=p-next;
p-next=temp;
//c++;
}
}
p=front;
//printf(hi);
// scanf(%d,k);
while(p!=NULL)
{
if(p-data!=temp-datap-add==0)
{
temp2=(struct
node*)malloc(sizeof(struct node));
temp2-data=p-data+item;
temp2-next=NULL;
temp2-add=1;
q=p;
while(q-next!=NULLq-next-datatemp2-data)
{
q=q-next;
}
if(q-next==NULL)
{
temp2-next=q-next;
q-next=temp2;
rear=temp2;
}
else
if(q-data==temp2-data)
{
flag=1;
return 1;
}
else
{
temp2-next=q-next;
q-next=temp2;
}
}
p=p-next;
}
/*for(i=1;i=c;i++)
{
if(p-data!=item)
{
temp2=(struct node*)malloc(sizeof(struct node));
temp2-data=p-data+item;
temp2-next=NULL;
q=p;
while(q-next!=NULLq-next-datatemp2-data)
{
q=q-next;
}
if(q-next==NULL)
{
temp2-next=q-next;
q-next=temp2;
rear=temp2;
}
else
{
temp2-next=q-next;
q-next=temp2;
}
//rear-next=temp2;
//rear=rear-next;
//free(temp2);
}
p=p-next;
}*/
//printf(hiii);
//scanf(%d,k);
p=front;
while(p!=NULL)
{
p-add=0;
p=p-next;
// p=p-next;
//scanf(%d,k);
}
p=front;
while(p!=NULL)
{
if(p-next(p-data==p-next-data))
flag=1;
// printf(%d ,p-data);
p=p-next;
// p=p-next;
//scanf(%d,k);
}}
/*void fun(int item)
{
struct noode *temp,*temp2,*r;
temp=(struct node*)malloc(sizeof(struct node));
temp-data=item;
temp-next=NULL;
r=rear;
if(front==NULL)
{
front=temp;
Re: [algogeeks] Re: Tug of War
http://www.spoj.pl/SPOJ/problems/TUG/
earlier i thought it would be easy to do it knapsack...but when i started
coding iti feel lost.i have failed to relate it with 0/1
knapsack..
plz tell me how this problem can be solved using dp solution of
knapsack..i mean in knapsack you form a matrixb[ ][ ] in which
b[n][w] denotes the maximum benefit with n items available having weight
exactly w...
.in tug of war how can we use this matrix ??
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Thu, Aug 4, 2011 at 9:55 PM, Don dondod...@gmail.com wrote:
As some have said, this is NP, so for larger values of N it takes a
very long time. For N=20 it runs quite quickly.
// True if some set of strengths from s[n] sum to t
bool divide(unsigned int *s, int n, int t)
{
if (t == 0) return true; // We reached the goal
if (n == 0) return false;// No people left to assign
if (*s t) return false;// Smallest person exceeds goal
if (*s * n t) return false;// Everyone else can not total
to goal
if (divide(s+1,n-1,t)) return true; // Consider not including first
person in line
return divide(s+1,n-1,t-*s); // Consider including first
person in line
}
int main(int argc, char* argv[])
{
const int MAX=50;
int N;
unsigned int strength[MAX];
int sum = 0;
int i,j;
printf(How many people are playing?);
scanf(%d,N);
for(i = 0; i N; ++i)
{
printf(Enter strength of person %d:, i+1);
scanf(%d, strength[i]);
sum += strength[i];
}
if (sum % 2 == 1)
{
printf(NO\n);
}
else
{
// Sort from high to low
for(i = 0; i N; ++i)
for(j = 1; j N; ++j)
{
if (strength[j] strength[j-1])
{
strength[j] ^= strength[j-1];
strength[j-1] ^= strength[j];
strength[j] ^= strength[j-1];
}
}
if (divide(strength+1,N-1,sum/2)) printf(YES\n);
else printf(NO\n);
}
return 0;
}
On Jul 30, 4:44 am, sylvester abeygau...@gmail.com wrote:
input consists of N integers, separated by a space. The ith integer
indicates the strength of the ith person.
For each case, output YES if it is possible to pick some people from
the group and separate into two teams of equal strengths else NO
--
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: Tug of War
anyone plz give hint how to solve this problem !!
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Sat, Aug 6, 2011 at 2:53 PM, Amol Sharma amolsharm...@gmail.com wrote:
http://www.spoj.pl/SPOJ/problems/TUG/
earlier i thought it would be easy to do it knapsack...but when i started
coding iti feel lost.i have failed to relate it with 0/1
knapsack..
plz tell me how this problem can be solved using dp solution of
knapsack..i mean in knapsack you form a matrixb[ ][ ] in which
b[n][w] denotes the maximum benefit with n items available having weight
exactly w...
.in tug of war how can we use this matrix ??
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Thu, Aug 4, 2011 at 9:55 PM, Don dondod...@gmail.com wrote:
As some have said, this is NP, so for larger values of N it takes a
very long time. For N=20 it runs quite quickly.
// True if some set of strengths from s[n] sum to t
bool divide(unsigned int *s, int n, int t)
{
if (t == 0) return true; // We reached the goal
if (n == 0) return false;// No people left to assign
if (*s t) return false;// Smallest person exceeds
goal
if (*s * n t) return false;// Everyone else can not total
to goal
if (divide(s+1,n-1,t)) return true; // Consider not including
first
person in line
return divide(s+1,n-1,t-*s); // Consider including first
person in line
}
int main(int argc, char* argv[])
{
const int MAX=50;
int N;
unsigned int strength[MAX];
int sum = 0;
int i,j;
printf(How many people are playing?);
scanf(%d,N);
for(i = 0; i N; ++i)
{
printf(Enter strength of person %d:, i+1);
scanf(%d, strength[i]);
sum += strength[i];
}
if (sum % 2 == 1)
{
printf(NO\n);
}
else
{
// Sort from high to low
for(i = 0; i N; ++i)
for(j = 1; j N; ++j)
{
if (strength[j] strength[j-1])
{
strength[j] ^= strength[j-1];
strength[j-1] ^= strength[j];
strength[j] ^= strength[j-1];
}
}
if (divide(strength+1,N-1,sum/2)) printf(YES\n);
else printf(NO\n);
}
return 0;
}
On Jul 30, 4:44 am, sylvester abeygau...@gmail.com wrote:
input consists of N integers, separated by a space. The ith integer
indicates the strength of the ith person.
For each case, output YES if it is possible to pick some people from
the group and separate into two teams of equal strengths else NO
--
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: Tug of War
My accepted solution is this and I have told you my logic
#includestdio.h
struct node
{
int data;
int add;
struct node *next;
}*front,*rear;
int flag,c;
int fun(int item)
{
struct node *temp,*temp2,*r,*p,*q;
int k,i;
r=(struct node*)malloc(sizeof(struct node));
temp=(struct node*)malloc(sizeof(struct node));
r-next=NULL;
temp-data=item;
temp-add=0;
temp-next=NULL;
c++;
//rear-next=r;
//printf(hi);
// scanf(%d,k);
if(front==NULL)
{
front=temp;
rear=front;
// rear-next=r;
//c++;
//temp2=(struct node *)malloc(sizeof(struct node));
// temp-
}
else if(front-datatemp-data)
{
temp-next=front;
front=temp;
//c++;
}
else if(front-data==temp-data)
{
flag=1;
return 1;
}
else
{
p=front;
while(p-next!=NULLp-next-datatemp-data)
{
p=p-next;
}
if(p-next(p-next-data==temp-data))
{
flag=1;
return 1;
}
if(p-next==NULL)
{
temp-next=p-next;
p-next=temp;
rear=temp;
//c++;
//r=rear;
}
else
{
temp-next=p-next;
p-next=temp;
//c++;
}
}
p=front;
//printf(hi);
// scanf(%d,k);
while(p!=NULL)
{
if(p-data!=temp-datap-add==0)
{
temp2=(struct
node*)malloc(sizeof(struct node));
temp2-data=p-data+item;
temp2-next=NULL;
temp2-add=1;
q=p;
while(q-next!=NULLq-next-datatemp2-data)
{
q=q-next;
}
if(q-next==NULL)
{
temp2-next=q-next;
q-next=temp2;
rear=temp2;
}
else
if(q-data==temp2-data)
{
flag=1;
return 1;
}
else
{
temp2-next=q-next;
q-next=temp2;
}
}
p=p-next;
}
/*for(i=1;i=c;i++)
{
if(p-data!=item)
{
temp2=(struct node*)malloc(sizeof(struct node));
temp2-data=p-data+item;
temp2-next=NULL;
q=p;
while(q-next!=NULLq-next-datatemp2-data)
{
q=q-next;
}
if(q-next==NULL)
{
temp2-next=q-next;
q-next=temp2;
rear=temp2;
}
else
{
temp2-next=q-next;
q-next=temp2;
}
//rear-next=temp2;
//rear=rear-next;
//free(temp2);
}
p=p-next;
}*/
//printf(hiii);
//scanf(%d,k);
p=front;
while(p!=NULL)
{
p-add=0;
p=p-next;
// p=p-next;
//scanf(%d,k);
}
p=front;
while(p!=NULL)
{
if(p-next(p-data==p-next-data))
flag=1;
// printf(%d ,p-data);
p=p-next;
// p=p-next;
//scanf(%d,k);
}
}
/*void fun(int item)
{
struct noode *temp,*temp2,*r;
temp=(struct node*)malloc(sizeof(struct node));
temp-data=item;
temp-next=NULL;
r=rear;
if(front==NULL)
{
front=temp;
rear=front;
//temp2=(struct node *)malloc(sizeof(struct node));
// temp-
}
else
{
p=front;
r=rear;
if(temp-datafront-data)
{
Re: [algogeeks] Re: Tug of War
@saurabh: see this case input 100, 1, 1, 1,1 your algo - group 1 - 100 group 2 - 1 1 1 1 but the group with 2 equal strength can be formed as G1 - 1 1 G2 - 1 1 or 1 1 each... i mean it is not necessary to take all the people.but your algo takes the the person with max strength at startwhich is not correct..there will be many cases where it will fail it might be correct if it is compulsory to take all the persons in the two groups a knapsack dp solution will be the best for this particular problem...if u can thin of any other approach then suggest !! P.S : Sorry for replying after such a long time :P -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Mon, Aug 1, 2011 at 2:00 AM, Nitish Garg nitishgarg1...@gmail.comwrote: Can you explain a bit more? Thanks Nitish Garg -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-LiQq0dHHksJ. 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: Tug of War
Hence shown never play cricket when someone in the group is stronger than the whole team together,,,:D Anyways my original solution was not taking into account that players can be excluded.(Thats unfair in a real scenario ryt?) Its a classical 0/1 knapsack problem which can be implemented either as a greedy solution or dp On Thu, Aug 4, 2011 at 7:26 PM, Amol Sharma amolsharm...@gmail.com wrote: @saurabh: see this case input 100, 1, 1, 1,1 your algo - group 1 - 100 group 2 - 1 1 1 1 but the group with 2 equal strength can be formed as G1 - 1 1 G2 - 1 1 or 1 1 each... i mean it is not necessary to take all the people.but your algo takes the the person with max strength at startwhich is not correct..there will be many cases where it will fail it might be correct if it is compulsory to take all the persons in the two groups a knapsack dp solution will be the best for this particular problem...if u can thin of any other approach then suggest !! P.S : Sorry for replying after such a long time :P -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Mon, Aug 1, 2011 at 2:00 AM, Nitish Garg nitishgarg1...@gmail.comwrote: Can you explain a bit more? Thanks Nitish Garg -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-LiQq0dHHksJ. 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. -- 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.
Re: [algogeeks] Re: Tug of War
On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote: Its a classical 0/1 knapsack problem which can be implemented either as a greedy solution or dp It has been stated earlier in the thread that this is an 'NP-Complete' problem. [0] It means, there is no known polynomial-time algorithm for this problem. If you think you have a greedy solution to this problem, think again. The DP solution is also, 'pseudo-polynomial-time' [0] http://en.wikipedia.org/wiki/Partition_problem -- Gaurav Menghani -- 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: Tug of War
On Thu, Aug 4, 2011 at 7:42 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote: Its a classical 0/1 knapsack problem which can be implemented either as a greedy solution or dp It has been stated earlier in the thread that this is an 'NP-Complete' problem. [0] It means, there is no known polynomial-time algorithm for this problem. If you think you have a greedy solution to this problem, think again. The DP solution is also, 'pseudo-polynomial-time' Just adding, greedy solutions are always possible, but the thing to ponder over is, whether they give optimal solutions _for_every_case_ or not. -- Gaurav Menghani -- 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: Tug of War
@gaurav: agree...greedy wouldn't work in this case..even 0-1 knapsack is a DP problem...which can't be done by greedy !! -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Thu, Aug 4, 2011 at 7:46 PM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: On Thu, Aug 4, 2011 at 7:42 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote: Its a classical 0/1 knapsack problem which can be implemented either as a greedy solution or dp It has been stated earlier in the thread that this is an 'NP-Complete' problem. [0] It means, there is no known polynomial-time algorithm for this problem. If you think you have a greedy solution to this problem, think again. The DP solution is also, 'pseudo-polynomial-time' Just adding, greedy solutions are always possible, but the thing to ponder over is, whether they give optimal solutions _for_every_case_ or not. -- Gaurav Menghani -- 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: Tug of War
@amol knapsack is originaly a greedy problem onlyThe spirit remains the same,selecting the best at each stepDp helps in defining the best in the particular case. @Gaurav I think its NP complete once the number of teams become varaible, corrct me if wrong i am weak with the theoritical stuffs... On Thu, Aug 4, 2011 at 8:06 PM, Amol Sharma amolsharm...@gmail.com wrote: @gaurav: agree...greedy wouldn't work in this case..even 0-1 knapsack is a DP problem...which can't be done by greedy !! -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Thu, Aug 4, 2011 at 7:46 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Thu, Aug 4, 2011 at 7:42 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Thu, Aug 4, 2011 at 7:37 PM, saurabh singh saurab...@gmail.com wrote: Its a classical 0/1 knapsack problem which can be implemented either as a greedy solution or dp It has been stated earlier in the thread that this is an 'NP-Complete' problem. [0] It means, there is no known polynomial-time algorithm for this problem. If you think you have a greedy solution to this problem, think again. The DP solution is also, 'pseudo-polynomial-time' Just adding, greedy solutions are always possible, but the thing to ponder over is, whether they give optimal solutions _for_every_case_ or not. -- Gaurav Menghani -- 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. -- 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.
Re: [algogeeks] Re: Tug of War
On Thu, Aug 4, 2011 at 8:13 PM, saurabh singh saurab...@gmail.com wrote: think its NP complete once the number of teams become varaible, corrct me if wrong i am weak with the theoritical stuffs... Err, it is NP-complete, the thing is when the set of integers is small, a DP solution runs in reasonable time. When you increase the set size, the time taken increases. -- Gaurav Menghani Stony Brook University -- 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: Tug of War
original knapsack is called fractional knapsack in which greedy works...but we were talking abt 0-1 knapsack :P -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Thu, Aug 4, 2011 at 8:19 PM, Gaurav Menghani gaurav.mengh...@gmail.comwrote: On Thu, Aug 4, 2011 at 8:13 PM, saurabh singh saurab...@gmail.com wrote: think its NP complete once the number of teams become varaible, corrct me if wrong i am weak with the theoritical stuffs... Err, it is NP-complete, the thing is when the set of integers is small, a DP solution runs in reasonable time. When you increase the set size, the time taken increases. -- Gaurav Menghani Stony Brook University -- 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: Tug of War
I told you the spirit is greedy backed up by DP for creating correct optimal substructuresA pure greedy solution wont create the right substructure... On Thu, Aug 4, 2011 at 9:06 PM, Amol Sharma amolsharm...@gmail.com wrote: original knapsack is called fractional knapsack in which greedy works...but we were talking abt 0-1 knapsack :P -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Thu, Aug 4, 2011 at 8:19 PM, Gaurav Menghani gaurav.mengh...@gmail.com wrote: On Thu, Aug 4, 2011 at 8:13 PM, saurabh singh saurab...@gmail.comwrote: think its NP complete once the number of teams become varaible, corrct me if wrong i am weak with the theoritical stuffs... Err, it is NP-complete, the thing is when the set of integers is small, a DP solution runs in reasonable time. When you increase the set size, the time taken increases. -- Gaurav Menghani Stony Brook University -- 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. -- 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.
[algogeeks] Re: Tug of War
As some have said, this is NP, so for larger values of N it takes a
very long time. For N=20 it runs quite quickly.
// True if some set of strengths from s[n] sum to t
bool divide(unsigned int *s, int n, int t)
{
if (t == 0) return true; // We reached the goal
if (n == 0) return false;// No people left to assign
if (*s t) return false;// Smallest person exceeds goal
if (*s * n t) return false;// Everyone else can not total
to goal
if (divide(s+1,n-1,t)) return true; // Consider not including first
person in line
return divide(s+1,n-1,t-*s); // Consider including first
person in line
}
int main(int argc, char* argv[])
{
const int MAX=50;
int N;
unsigned int strength[MAX];
int sum = 0;
int i,j;
printf(How many people are playing?);
scanf(%d,N);
for(i = 0; i N; ++i)
{
printf(Enter strength of person %d:, i+1);
scanf(%d, strength[i]);
sum += strength[i];
}
if (sum % 2 == 1)
{
printf(NO\n);
}
else
{
// Sort from high to low
for(i = 0; i N; ++i)
for(j = 1; j N; ++j)
{
if (strength[j] strength[j-1])
{
strength[j] ^= strength[j-1];
strength[j-1] ^= strength[j];
strength[j] ^= strength[j-1];
}
}
if (divide(strength+1,N-1,sum/2)) printf(YES\n);
else printf(NO\n);
}
return 0;
}
On Jul 30, 4:44 am, sylvester abeygau...@gmail.com wrote:
input consists of N integers, separated by a space. The ith integer
indicates the strength of the ith person.
For each case, output YES if it is possible to pick some people from
the group and separate into two teams of equal strengths else NO
--
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: Tug of War
Can you explain a bit more? Thanks Nitish Garg -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-LiQq0dHHksJ. 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: Tug of War
To Solve This Problem, I would 1. Sort the given list S by their respective strengths. 2. Then I would create two other lists A and B for respective partitions. 3. (a) Remove First and Last from S add them both to A (b) Remove First and Last from S add them both to B 4. Repeat Step 3 until there is 1 or 0 people left in which if there is 1 person left we would print NO 0 people we successfully partitioned the teams into equal strengths. This is just off the top of my head though, so not sure if it will completely work :) On Jul 30, 8:37 am, Amol Sharma amolsharm...@gmail.com wrote: @saurabh- your algo has very high probability of failure take the case 9,7,8,4,3,1 acc to ur algo group 1 is 9,8,3 strength =20 group 2 is 7,4,2 strength =13 but it is possible to divide them into 2 equal grp's take G1 - 9,4,3 total =16 G2 - 7,8,1 total =16 so we have to think of some better algo -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sat, Jul 30, 2011 at 5:51 PM, shubham shubh2...@gmail.com wrote: hey sylvester, just clarify the problem .. Is it such that in forming the group some people can be left out or the sum of the number of people in both partitions is equal to the total number of people -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/gVAGoc_nYhAJ. 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: Tug of War
@Amol according to my algo group 1=9 4 3 group 2= 7 8 1 Think again On Sat, Jul 30, 2011 at 6:27 PM, Gary Drocella gdroc...@gmail.com wrote: To Solve This Problem, I would 1. Sort the given list S by their respective strengths. 2. Then I would create two other lists A and B for respective partitions. 3. (a) Remove First and Last from S add them both to A (b) Remove First and Last from S add them both to B 4. Repeat Step 3 until there is 1 or 0 people left in which if there is 1 person left we would print NO 0 people we successfully partitioned the teams into equal strengths. This is just off the top of my head though, so not sure if it will completely work :) On Jul 30, 8:37 am, Amol Sharma amolsharm...@gmail.com wrote: @saurabh- your algo has very high probability of failure take the case 9,7,8,4,3,1 acc to ur algo group 1 is 9,8,3 strength =20 group 2 is 7,4,2 strength =13 but it is possible to divide them into 2 equal grp's take G1 - 9,4,3 total =16 G2 - 7,8,1 total =16 so we have to think of some better algo -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sat, Jul 30, 2011 at 5:51 PM, shubham shubh2...@gmail.com wrote: hey sylvester, just clarify the problem .. Is it such that in forming the group some people can be left out or the sum of the number of people in both partitions is equal to the total number of people -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/gVAGoc_nYhAJ. 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. -- 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.
Re: [algogeeks] Re: Tug of War
when i said pick elements in descending order,it meant sorting them.Sorry for being unclear. But i am open to any discussion about my logic because its pure intuition based algo,so it may be having lots of loop holes. On Sun, Jul 31, 2011 at 7:02 AM, saurabh singh saurab...@gmail.com wrote: @Amol according to my algo group 1=9 4 3 group 2= 7 8 1 Think again On Sat, Jul 30, 2011 at 6:27 PM, Gary Drocella gdroc...@gmail.com wrote: To Solve This Problem, I would 1. Sort the given list S by their respective strengths. 2. Then I would create two other lists A and B for respective partitions. 3. (a) Remove First and Last from S add them both to A (b) Remove First and Last from S add them both to B 4. Repeat Step 3 until there is 1 or 0 people left in which if there is 1 person left we would print NO 0 people we successfully partitioned the teams into equal strengths. This is just off the top of my head though, so not sure if it will completely work :) On Jul 30, 8:37 am, Amol Sharma amolsharm...@gmail.com wrote: @saurabh- your algo has very high probability of failure take the case 9,7,8,4,3,1 acc to ur algo group 1 is 9,8,3 strength =20 group 2 is 7,4,2 strength =13 but it is possible to divide them into 2 equal grp's take G1 - 9,4,3 total =16 G2 - 7,8,1 total =16 so we have to think of some better algo -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sat, Jul 30, 2011 at 5:51 PM, shubham shubh2...@gmail.com wrote: hey sylvester, just clarify the problem .. Is it such that in forming the group some people can be left out or the sum of the number of people in both partitions is equal to the total number of people -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/gVAGoc_nYhAJ. 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. -- 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.
Re: [algogeeks] Re: Tug of War
Classic problem of DP + bit´s...like knapsack 2011/7/30 saurabh singh saurab...@gmail.com when i said pick elements in descending order,it meant sorting them.Sorry for being unclear. But i am open to any discussion about my logic because its pure intuition based algo,so it may be having lots of loop holes. On Sun, Jul 31, 2011 at 7:02 AM, saurabh singh saurab...@gmail.comwrote: @Amol according to my algo group 1=9 4 3 group 2= 7 8 1 Think again On Sat, Jul 30, 2011 at 6:27 PM, Gary Drocella gdroc...@gmail.comwrote: To Solve This Problem, I would 1. Sort the given list S by their respective strengths. 2. Then I would create two other lists A and B for respective partitions. 3. (a) Remove First and Last from S add them both to A (b) Remove First and Last from S add them both to B 4. Repeat Step 3 until there is 1 or 0 people left in which if there is 1 person left we would print NO 0 people we successfully partitioned the teams into equal strengths. This is just off the top of my head though, so not sure if it will completely work :) On Jul 30, 8:37 am, Amol Sharma amolsharm...@gmail.com wrote: @saurabh- your algo has very high probability of failure take the case 9,7,8,4,3,1 acc to ur algo group 1 is 9,8,3 strength =20 group 2 is 7,4,2 strength =13 but it is possible to divide them into 2 equal grp's take G1 - 9,4,3 total =16 G2 - 7,8,1 total =16 so we have to think of some better algo -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sat, Jul 30, 2011 at 5:51 PM, shubham shubh2...@gmail.com wrote: hey sylvester, just clarify the problem .. Is it such that in forming the group some people can be left out or the sum of the number of people in both partitions is equal to the total number of people -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/gVAGoc_nYhAJ. 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. -- 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. -- Victor Manuel Grijalva Altamirano Universidad Tecnologica de La Mixteca -- 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: Tug of War
@victor +1 On Sun, Jul 31, 2011 at 8:12 AM, Victor Manuel Grijalva Altamirano kavic1.mar...@gmail.com wrote: Classic problem of DP + bit´s...like knapsack 2011/7/30 saurabh singh saurab...@gmail.com when i said pick elements in descending order,it meant sorting them.Sorry for being unclear. But i am open to any discussion about my logic because its pure intuition based algo,so it may be having lots of loop holes. On Sun, Jul 31, 2011 at 7:02 AM, saurabh singh saurab...@gmail.comwrote: @Amol according to my algo group 1=9 4 3 group 2= 7 8 1 Think again On Sat, Jul 30, 2011 at 6:27 PM, Gary Drocella gdroc...@gmail.comwrote: To Solve This Problem, I would 1. Sort the given list S by their respective strengths. 2. Then I would create two other lists A and B for respective partitions. 3. (a) Remove First and Last from S add them both to A (b) Remove First and Last from S add them both to B 4. Repeat Step 3 until there is 1 or 0 people left in which if there is 1 person left we would print NO 0 people we successfully partitioned the teams into equal strengths. This is just off the top of my head though, so not sure if it will completely work :) On Jul 30, 8:37 am, Amol Sharma amolsharm...@gmail.com wrote: @saurabh- your algo has very high probability of failure take the case 9,7,8,4,3,1 acc to ur algo group 1 is 9,8,3 strength =20 group 2 is 7,4,2 strength =13 but it is possible to divide them into 2 equal grp's take G1 - 9,4,3 total =16 G2 - 7,8,1 total =16 so we have to think of some better algo -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Sat, Jul 30, 2011 at 5:51 PM, shubham shubh2...@gmail.com wrote: hey sylvester, just clarify the problem .. Is it such that in forming the group some people can be left out or the sum of the number of people in both partitions is equal to the total number of people -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/gVAGoc_nYhAJ. 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. -- 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. -- Victor Manuel Grijalva Altamirano Universidad Tecnologica de La Mixteca -- 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. -- Ankur Khurana Computer Science Netaji Subhas Institute Of Technology Delhi. -- 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.
