My accepted solution is this and I have told you my logic #include<stdio.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->data>temp->data) { temp->next=front; front=temp; //c++; } else if(front->data==temp->data) { flag=1; return 1; } else { p=front; while(p->next!=NULL&&p->next->data<temp->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->data&&p->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!=NULL&&q->next->data<temp2->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!=NULL&&q->next->data<temp2->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->data<front->data) { temp->next=front; front=temp; temp2=(struct node*)malloc(sizeof(struct node)); temp2->data=p->data+item; temp2->next=NULL; rear->next=temp2; rear=rear->next; free(temp2); } else if(temp->data==front->data) { flag=1; } // p=front; temp2=(struct node*)malloc(sizeof(struct node)); temp2->data=p->data+item; temp2->next=NULL; rear->next=temp2; rear=rear->next; free(temp2); while(p->next!=r&&p->next->data<temp->data) { temp2=(struct node*)malloc(sizeof(struct node)); temp2->data=p->data+item; temp2->next=NULL; rear->next=temp2; rear=rear->next; p=p->next; free(temp2); } if(p->next==r) { if(p->next->data<temp->data) { temp->next=r->next; r->next=temp; temp2=(struct node*)malloc(sizeof(struct node)); temp2->data=r->data+item; temp2->next=NULL; rear->next=temp2; rear=rear->next; free(p); } else if(p->next->data==temp->data) { flag=1; } else { temp->next=p->next; p->next=temp; temp2=(struct node*)malloc(sizeof(struct node)); temp2->data=r->data+item; temp2->next=NULL; rear->next=temp2; rear=rear->next; } } else { temp->next=p->next; p->next=temp; temp2=(struct node*)malloc(sizeof(struct node)); temp2->data=p->data+item; temp2->next=NULL; rear->next=temp2; rear=rear->next; while(p->next!=r) { temp2=(struct node*)malloc(sizeof(struct node)); temp2->data=p->data+item; temp2->next=NULL; rear->next=temp2; rear=rear->next; p=p->next; } } } */ main() { int i,n,k,t,y; scanf("%d",&t); while(t--) { scanf("%d",&n); front=NULL; flag=0; c=0; rear=NULL; for(i=1;i<=n;i++) { scanf("%d",&y); if(flag!=1) fun(y); } if(flag==1) printf("YES\n"); else printf("NO\n"); } return 0; } On Sat, Aug 6, 2011 at 11:11 AM, Amol Sharma <amolsharm...@gmail.com> wrote: > 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 it....i 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 matrix b[ ][ ] 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. > -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.