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 <[email protected]> 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 <[email protected]>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 <[email protected]> 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 <[email protected]> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
