[algogeeks] Re: SPOJ problem code:MAJOR

2011-03-16 Thread .bashrc 
its a simple hashing problem i suppose.Beware there are some traps
though.It took me 9 submissions to get it fixed.
Just remember there are 1000 numbers so the array would be a[1001]

-- 
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 problem code:MAJOR

2011-02-15 Thread Balaji Ramani 
@Akshata

I managed to get AC with majority algorithm.

suggestions:

1) You can try to read input and find candidate in same loop
2) Use scanf and printf

Thanks,
Balaji.

On Tue, Feb 15, 2011 at 4:30 PM, jai gupta sayhelloto...@gmail.com wrote:

 #includestdio.h
 #includestring.h
 #includemalloc.h
 void work() {
 int n,max,maxpos,x,i;
 scanf(%d,n);
 int *arr=(int*) malloc(sizeof(int)*2005);
 memset(arr,0,2005);
 max=maxpos=0;

 for(i=0;in;i++)
 {
 scanf(%d,x);
 arr[x+1000]++;
 if(arr[x+1000]max)
 {
 max=arr[x+1000];
 maxpos=x;
 }
 }
 if(maxn/2)
 printf(YES %d\n,maxpos,max);
 else
 printf(NO\n);
 }
 int main() {
 int t;

 scanf(%d,t);
 while(t--)
 work();

 return 0;
 }

  --
 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.

[algogeeks] Re: SPOJ problem code:MAJOR

2011-02-14 Thread Akshata Sharma 
link to problem: http://www.spoj.pl/problems/MAJOR/

On Feb 14, 5:03 pm, Akshata Sharma akshatasharm...@gmail.com wrote:
 I am trying to submit my solution but its giving TLE. My implemetation is
 O(n).. and i am not able to think a faster algo than this for the problem.
 The problem is based on finding the majority element concept. Please help

 My code:

 #includeiostream
 #includestring.h

 using namespace std;

 struct res{
 string boo;
 int key;

 };

 long Majoritycount(int a[], int n)
 {
 int ctr=1;
 int candidate = a[0];
 int mindex=0;

 for(int i=0;in;i++){
 if(a[i]==a[mindex]) ctr++; //match - incr counter
 else ctr--; //mismatch - dec counter

 if(ctr==0) {
 ctr=1;
 mindex=i;
 candidate=a[i];

 }
 }
 return candidate;
 }

 int main()
 {
 struct res result[100];
 int t,n,count=0;
 int tt,cnt=0;
 cint;
 tt=t;

 while(t0)
 {
 cinn;
 int *arr=new int[n];
 for(int i=0;in;i++)
 cinarr[i];
 int a=Majoritycount(arr,n);

 for(int i=0;in;i++)
 if(arr[i]==a)
 count++;

 if(count(n/2))
 {
 result[t].boo=YES;
 result[t].key=a;}

 else
 {
 result[t].boo=NO;
 result[t].key=;}

 t--;
 count=0;

 }

 for(int i=tt;i0;i--)
 {
         if(result[i].key!=)
 coutresult[i].boo result[i].key\n;
 else
 coutresult[i].boo\n;

 }

 return 0;

 }

-- 
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 problem code:MAJOR

2011-02-14 Thread sunny agrawal 
try replacing cin, cout by printf,scanf

On Mon, Feb 14, 2011 at 5:39 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:

 link to problem: http://www.spoj.pl/problems/MAJOR/

 On Feb 14, 5:03 pm, Akshata Sharma akshatasharm...@gmail.com wrote:
  I am trying to submit my solution but its giving TLE. My implemetation is
  O(n).. and i am not able to think a faster algo than this for the
 problem.
  The problem is based on finding the majority element concept. Please help
 
  My code:
 
  #includeiostream
  #includestring.h
 
  using namespace std;
 
  struct res{
  string boo;
  int key;
 
  };
 
  long Majoritycount(int a[], int n)
  {
  int ctr=1;
  int candidate = a[0];
  int mindex=0;
 
  for(int i=0;in;i++){
  if(a[i]==a[mindex]) ctr++; //match - incr counter
  else ctr--; //mismatch - dec counter
 
  if(ctr==0) {
  ctr=1;
  mindex=i;
  candidate=a[i];
 
  }
  }
  return candidate;
  }
 
  int main()
  {
  struct res result[100];
  int t,n,count=0;
  int tt,cnt=0;
  cint;
  tt=t;
 
  while(t0)
  {
  cinn;
  int *arr=new int[n];
  for(int i=0;in;i++)
  cinarr[i];
  int a=Majoritycount(arr,n);
 
  for(int i=0;in;i++)
  if(arr[i]==a)
  count++;
 
  if(count(n/2))
  {
  result[t].boo=YES;
  result[t].key=a;}
 
  else
  {
  result[t].boo=NO;
  result[t].key=;}
 
  t--;
  count=0;
 
  }
 
  for(int i=tt;i0;i--)
  {
  if(result[i].key!=)
  coutresult[i].boo result[i].key\n;
  else
  coutresult[i].boo\n;
 
  }
 
  return 0;
 
  }

 --
 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.




-- 
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee

-- 
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 problem code:MAJOR

2011-02-14 Thread Terence 

Try scanf/printf instead of cin/cout.
For huge data set, the IO time matters.

On 2011-2-14 20:09, Akshata Sharma wrote:

link to problem: http://www.spoj.pl/problems/MAJOR/

On Feb 14, 5:03 pm, Akshata Sharmaakshatasharm...@gmail.com  wrote:

I am trying to submit my solution but its giving TLE. My implemetation is
O(n).. and i am not able to think a faster algo than this for the problem.
The problem is based on finding the majority element concept. Please help

My code:

#includeiostream
#includestring.h

using namespace std;

struct res{
string boo;
int key;

};

long Majoritycount(int a[], int n)
{
int ctr=1;
int candidate = a[0];
int mindex=0;

for(int i=0;in;i++){
if(a[i]==a[mindex]) ctr++; //match - incr counter
else ctr--; //mismatch - dec counter

if(ctr==0) {
ctr=1;
mindex=i;
candidate=a[i];

}
}
return candidate;
}

int main()
{
struct res result[100];
int t,n,count=0;
int tt,cnt=0;
cint;
tt=t;

while(t0)
{
cinn;
int *arr=new int[n];
for(int i=0;in;i++)
cinarr[i];
int a=Majoritycount(arr,n);

for(int i=0;in;i++)
if(arr[i]==a)
count++;

if(count(n/2))
{
result[t].boo=YES;
result[t].key=a;}

else
{
result[t].boo=NO;
result[t].key=;}

t--;
count=0;

}

for(int i=tt;i0;i--)
{
 if(result[i].key!=)
coutresult[i].booresult[i].key\n;
else
coutresult[i].boo\n;

}

return 0;

}


--
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 problem code:MAJOR

2011-02-14 Thread sankalp srivastava 
A few problems with your code :

1)Very Unclear (sorry !):- Either use a camelCase like java or use the
c++ underscores style .Paste ur code on pastebin etc.
2)Too many loops :- It is O(n)  , but perhaps O(4000*n) , much worse
than O(n^2) in this case.
3)The problem is based on majority element concept :- No it's not !
It's a simple hashing problem .
4)Use scanf and printf , never ever use cin and cout , they are too
slow .(Same holds for java , use printwriter , never scanner etc. )


5)AC code :-http://pastebin.com/FkBiS6S3

PS:Nice practice problem , it's been 2 months since I opened spoj
(Increased my points by .6 :D):P

-- 
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 problem code:MAJOR

2011-02-14 Thread NEERAJ ARORA 
I simply used arrays to count the frequency of each numberMy
accepted solution is:
#includestdio.h
int main()
{
int t,n,i,p,x,chk,k;
int pos[1000];
int neg[1000];
int nos[100];
scanf(%d,t);
while(t--)
{
chk=0;
p=0;
n=0;
scanf(%d,n);
for(i=0;i1000;i++)
{
pos[i]=0;
neg[i]=0;
}
for(i=0;in;i++)
{
scanf(%d,x);
nos[i]=x;
if(x=0)
{
pos[x]++;

}
else
{
neg[-1*x]++;
}

}
for(i=0;in;i++)
{
if(nos[i]=0)
{
if(pos[nos[i]]n/2)
{
k=nos[i];
chk=1;
}
}
else
{
if(pos[-1*nos[i]]n/2)
{
k=nos[i];
chk=1;
}
}
}
if(chk==0)
{
printf(NO\n);
}
else
{
printf(YES %d\n,k);
}
}
return 0;
}

-- 
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.