coding_is_fun's blog

CSACADEMY : Sum of triplets
By coding_is_fun, 7 years ago, In English

I am getting Wrong answer . Please help .

code

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/

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply