coding_is_fun's blog

Counting Triplets

By coding_is_fun, 7 years ago, In English

I found a similar type of problem as last csacademy problem Sum of Triplets but slightly different :

Here they said find triplets such as A[i] + A[j] = A[k] where i<j<k . 1 <= Array size is <= 10^5 . 1 <= Array values < 2^16 .

Time limit : 12 second .

problem link : https://toph.co/p/counting-triplets

How to solve this problem without n^2 loop ? I am getting TLE .

My solution :

here

Since they said "A[i] + A[j] = A[k] where i<j<k " so i can not sort the data . I have to work as the given input .

At first I declare a map<int,int> mxIndex ; Then i store the maximum index of each data in this map .

Then I run a n^2 loop for every A[i] + A[j] , i search this sum in map . If found then i check the maximum index of A[i] + A[j] . If that index >= j+1 . That means found a triplet i < j < k so , ans++ . I know i will get WA . But i am getting TLE for n^2 loop . How can i do it efficiently ?

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

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

Can be done with FFT. You create a polynomial A(x), such that the coefficient before xi is the number of occurrences of value i in the array.

Now we find A2 which will give us the number of pairs with every possible sum. Well now the answer will be . As we can choose the last number in the triple in A[i] ways. By A[i] I mean the coefficient before xi.

The complexity will be .

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi! How does this solution ensure that selected numbers will definitely satisfy the constraint i < j < k?

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

Split the array into size B blocks and process each block separately. Keep two arrays: pref[] (frequency array of all processed blocks) and active[] (frequency array of the block being processed). There are two cases:

  • Index j doesn't belong to current block. For this, run FFT on the pref[] array (square it) and iterate over the index k in current block. Update answers.

  • Index j belongs to current block. In that case run loop over j, k and update answers using the frequency arrays.

Total n / B blocks, so complexity: which is minimized at , getting us a solution of .

Code: https://ideone.com/L5n6Yl

→ Reply