@keyan...that solves my problem...got AC...thanks :)
On Sun, Jun 12, 2011 at 1:15 AM, nicks <[email protected]> wrote:
> forgot to attach the code...here is the modified code..
>
> #include<vector>
> #include<iostream>
> #include<algorithm>
> #include<cstdio>
> #include<cmath>
>
> using namespace std;
>
> int main()
> {
> int num,ans=0,value,i,j,k,t,a,b,c,d,e,f;
> scanf("%d",&num);
> vector<int> val,a1,a2;
> for(i=0;i<num;i++)
> {
> scanf("%d",&t);
> val.push_back(t);
> }
> for(i=0;i<num;i++)
> {
> a=val[i];
> for(j=0;j<num;j++)
> {
> b=val[j];
> for(k=0;k<num;k++)
> {
> c=val[k];
> t=a*b+c;
> a1.push_back(t);
> }
> }
> }
> for(i=0;i<num;i++)
> {
> d=val[i];
> for(j=0;j<num;j++)
> {
> e=val[j];
> for(k=0;k<num;k++)
> {
> f=val[k];
> t=(f+e)*d;
> a2.push_back(t);
> }
> }
> }
>
> sort(a2.begin(),a2.end());
> vector<int>::iterator itr;
> for(itr=a1.begin();itr!=a1.end();itr++)
> {
> value=*itr;
> //ans+=count(a2.begin(),a2.end(),value);
>
>
> ans+=upper_bound(a2.begin(),a2.end(),value)-lower_bound(a2.begin(),a2.end(),value);
> }
>
> printf("%d",ans);
> return 0;
> }
>
>
>
>
>
>
> On Sun, Jun 12, 2011 at 1:07 AM, nicks <[email protected]> wrote:
>
>> @keyan..your advice was really very helpful...the time limit has come
>> under control ...1.4s but now i am getting WA though my code is giving right
>> ans for the test cases...can you plz help me in figuring out where it fails
>> ..
>>
>>
>> On Sun, Jun 12, 2011 at 12:59 AM, keyan karthi <[email protected]
>> > wrote:
>>
>>>
>>> hint: u ve commented some vital part of ur code ;)
>>>
>>> On Sun, Jun 12, 2011 at 12:46 PM, saurabh singh <[email protected]>wrote:
>>>
>>>>
>>>> I did used the library functions but I am getting sigsegv after 0.03 s.I
>>>> cant understand why?I am presuming sumthing wrong about the implemenatation
>>>> of bsearch?
>>>> I am assuming bsearch is returning a pointer to the first found element.
>>>>
>>>>
>>>> On Sun, Jun 12, 2011 at 12:41 PM, keyan karthi <
>>>> [email protected]> wrote:
>>>>
>>>>> upper_bound and lower_bound does a binary search to get count of alike
>>>>> terms.. which u tend to sum of to get the ans..
>>>>> out of the two arrays, u need to sort one array.. this will be teh
>>>>> vector in which u do the binary search wit every element of un sorted
>>>>> array..
>>>>> this is the approach i used... :) hope this helps...
>>>>>
>>>>> the above functions defined in "algorithm"
>>>>>
>>>>>
>>>>> On Sun, Jun 12, 2011 at 12:34 PM, nicks <[email protected]>wrote:
>>>>>
>>>>>> and here is my code I'm Getting TLE.... i tried to implement binary
>>>>>> search but failed bcoz how will i be able to trace the value from one
>>>>>> vector
>>>>>> into another vector if there are any multiple occureneces of any value(i
>>>>>> mean i have count them).....in this code i i have used count of algorithm
>>>>>> which may be expensive...suggest a better way plz...thnx in advance !!
>>>>>>
>>>>>>
>>>>>>
>>>>>> #include<vector>
>>>>>> #include<iostream>
>>>>>> #include<algorithm>
>>>>>> #include<cstdio>
>>>>>> #include<cmath>
>>>>>> using namespace std;
>>>>>> int main()
>>>>>> {
>>>>>> int num,ans=0,value,i,j,k,t,a,b,c,d,e,f;
>>>>>> scanf("%d",&num);
>>>>>> vector<int> val,a1,a2;
>>>>>> for(i=0;i<num;i++)
>>>>>> {
>>>>>> scanf("%d",&t);
>>>>>> val.push_back(t);
>>>>>> }
>>>>>> for(i=0;i<num;i++)
>>>>>> {
>>>>>> a=val[i];
>>>>>> for(j=0;j<num;j++)
>>>>>> {
>>>>>> b=val[j];
>>>>>> for(k=0;k<num;k++)
>>>>>> {
>>>>>> c=val[k];
>>>>>> t=a*b+c;
>>>>>> a1.push_back(t);
>>>>>> }
>>>>>> }
>>>>>> }
>>>>>> for(i=0;i<num;i++)
>>>>>> {
>>>>>> d=val[i];
>>>>>> for(j=0;j<num;j++)
>>>>>> {
>>>>>> e=val[j];
>>>>>> for(k=0;k<num;k++)
>>>>>> {
>>>>>> f=val[k];
>>>>>> t=(f+e)*d;
>>>>>> a2.push_back(t);
>>>>>> }
>>>>>> }
>>>>>> }
>>>>>>
>>>>>> vector<int>::iterator itr;
>>>>>> for(itr=a1.begin();itr!=a1.end();itr++)
>>>>>> {
>>>>>> value=*itr;
>>>>>> ans+=count(a2.begin(),a2.end(),value);
>>>>>> }
>>>>>>
>>>>>> printf("%d\n",ans);
>>>>>> return 0;
>>>>>> }
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Sat, Jun 11, 2011 at 11:57 PM, saurabh singh <
>>>>>> [email protected]> wrote:
>>>>>>
>>>>>>>
>>>>>>> OK here is my code
>>>>>>> #include<stdio.h>
>>>>>>> #include<algorithm>
>>>>>>> #include<utility>
>>>>>>> using namespace std;
>>>>>>> int compareints (const void * a, const void * b)
>>>>>>> {
>>>>>>> return ( *(long*)a - *(long*)b );
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> int main()
>>>>>>> {
>>>>>>> int n,s[101],a,b,c,d,e,f;
>>>>>>> long p1[100009],p2[100009];
>>>>>>> int i,j,k;
>>>>>>> scanf("%d",&n);
>>>>>>> for(i=0;i<n;i++) scanf("%d",&s[i]);
>>>>>>> //sort(s,s+i);
>>>>>>> k=0;
>>>>>>> for(i=0;i<n;i++)
>>>>>>> {
>>>>>>> for(j=0;j<n;j++)
>>>>>>> {
>>>>>>> for(int l=0;l<n;l++)
>>>>>>> {
>>>>>>> if(s[l])
>>>>>>> p1[k++]=(s[i]+s[j])*s[l];
>>>>>>> }
>>>>>>> }
>>>>>>> }
>>>>>>> //sort(p1,p1+k);
>>>>>>> int x=0;
>>>>>>> for(i=0;i<n;i++)
>>>>>>> {
>>>>>>> for(j=0;j<n;j++)
>>>>>>> {
>>>>>>> for(int l=0;l<n;l++)
>>>>>>> {
>>>>>>> //if(s[l]!=0)
>>>>>>> p2[x++]=(s[i]*s[j])+s[l];
>>>>>>> }
>>>>>>> }
>>>>>>> }
>>>>>>> sort(p2,p2+x);
>>>>>>> long *pItem;
>>>>>>> long count=0;
>>>>>>> for(i=0;i<k;i++)
>>>>>>> {
>>>>>>> pItem = (long*) bsearch (&p1[i], p2, x, sizeof (long),
>>>>>>> compareints);
>>>>>>> if(pItem){
>>>>>>>
>>>>>>> long *tmp=pItem;
>>>>>>> if(pItem==p2)while(*(tmp)==p1[i]&&tmp<p2+x){
>>>>>>> count++;tmp++;}
>>>>>>> else
>>>>>>> if(pItem==(p2+(x-1))) {
>>>>>>> while(pItem>=p2&&*(pItem)==p1[i]){count++;pItem--;}}
>>>>>>> else{
>>>>>>> tmp++;
>>>>>>> while(*(tmp)==p1[i]&&tmp<p2+x){
>>>>>>> count++;tmp++;}
>>>>>>>
>>>>>>> while(pItem>=p2&&*(pItem)==p1[i]){count++;pItem--;}
>>>>>>> }
>>>>>>> //count++;
>>>>>>> }
>>>>>>> }
>>>>>>> printf("%ld\n",count);
>>>>>>>
>>>>>>> //for(i=0;i<k;i++) printf("%ld ",p1[i]);printf("\n");
>>>>>>> //for(i=0;i<x;i++) printf("%ld ",p2[i]);printf("\n");
>>>>>>> return 0;
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>> Why is it getting segmentation fault?
>>>>>>>
>>>>>>> --
>>>>>>> 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.
>>>>>>
>>>>>
>>>>> --
>>>>> 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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> 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 [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.
>>>
>>
>>
>
--
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.
