CSACADEMY : Sum of triplets

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
7	cnnfls_csy	3569
9	ecnerwala	3494
10	Um_nik	3396

#	User	Contrib.
1	Um_nik	164
2	maomao90	160
3	-is-this-fft-	159
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	maroonrk	152

I am getting Wrong answer . Please help .

code

#include<bits/stdc++.h>

using namespace std;

//#define debug(...) printf( VA_ARGS )

#define debug(...) /****nothing****/

#define pb push_back

#define mp make_pair

#define mem(ar,val) memset(ar,val,sizeof(ar))

int ar[5007],frq[10007][5007],n;

int main() {

while(cin>>n)
{

    mem(frq,0);

   for(int i=1; i<=n; i++)
   {

   scanf("%d",&ar[i]);

   frq[ar[i]][i]=1;

   }

    for(int i=0; i<=10000; i++)
        for(int j=1; j<=n; j++)
            frq[i][j]+=frq[i][j-1];

    sort(ar+1,ar+n+1);

    long long ans=0;

    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {
            int sum=ar[i]+ar[j];
            ans+=frq[sum][n]-frq[sum][j];
        }

    cout<<ans<<endl;
}

return 0;

}

My logic is :

first sort the array , then run a n^2 for loop . For every ar[i]+ar[j] , i find out the frequency of ar[i]+ar[j] from index j+1 to n in array ar[] . Then i add this frequency to the answer .

To evaluate "frequency of ar[i]+ar[j] from index j+1 to n in array ar[] " i precalculated frq[X][Y] = "frequency of value X , from index 1 to Y " . For instance frq[5][2] means frequency of 5 from index 1 to 2 in arayy ar[] . I did it as like as partial sum technique .

So for every ar[i] + ar[j] I add this => sum=ar[i]+ar[j] ; ans += frq[sum][n] — frq[sum][j] ;

frq[sum][n] — frq[sum][j] means frequency from (j+1) to n = frequency(from 1 to n ) — frequency(from 1 to j ) ;

whats wrong in my logic or code ?

Problem link : https://csacademy.com/contest/archive/task/sum-triplets/

Comments (2)

Show archived | Write comment?

geniucos

7 years ago, # |

← Rev. 2 →

+11

After looking for a while, I found your mistake. You can look at my last submission for the problem. The problem is that you create the matrix f before you sort and positions changed in the meantime. I've tried to find how to give you a link to the submission because I know it's possible but I can't seem to figure it out:)) Anyway, that was, your only mistake. As a general note, I'm not sure whether it's actually ok to read with cin and scanf in the same time.

→ Reply

RedNextCentury

7 years ago, # ^ |

I think it's fine to use cin and scanf as long as you don't use sync_with_stdio(0);

coding_is_fun's blog