Miraacle's blog

By Miraacle, history, 7 weeks ago, In English

Hey, I've been trying to solve the following problem. Given an array of $$$n \leq 2*10^5$$$ distinct positive integers $$$a_1, a_2, \dots, a_n$$$ find the number of triplets ($$$i$$$, $$$j$$$, $$$k$$$) and $$$i < j < k$$$ such that $$$a_j - a_i = a_k - a_j$$$ (so $$$a_i$$$, $$$a_j$$$, $$$a_k$$$ form an arithmetic progression). Additionally, the test cases were made such that the answer is not greater than $$$10^6$$$.

I could only come up with a $$$O(n^2)$$$ solution and have no idea how to go further (maybe some FFT/Convolutions?). Any hints/help would be appreciated, thanks in advance!

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why would you need FFT/convolutions? An $$$O(nlogn)$$$ solution is easy to think of & implement.

Sort the array first. Then enumerate through all $$$j$$$ s. Therefore the formula is transformed into $$$2\times a_j=a_i+a_k$$$. The left part is determined; the right can be solved using binary search.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    How would you solve it with binary search? Also, remember that the order of given integers matters (for $$$1$$$, $$$2$$$, $$$3$$$ answer is $$$1$$$ while for $$$2$$$, $$$3$$$, $$$1$$$ answer is $$$0$$$).

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But I guess this problem is different because array elements ai is not a permutation of numbers from 1 to n.

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

    It's not the same problem as in my problem you need to find number of different triples, while in the problem you've posted you need to check whether there exists any triple.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I'm sorry I can't help you.:(

      When the sequence is arranged, the difficulty of determining the existence is * 2700, and the difficulty of counting may be greater than 3000

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

You can find this problem on CodeChef. https://www.codechef.com/problems/COUNTARI

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, didn't know about this problem! The problem is that values in that problem are up to $$$3*10^4$$$ while mine can be up to $$$10^5$$$. Maybe it will fit TL, but I'm wondering whether there is any way to use the fact that answer is not greater than $$$10^6$$$.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excuse me, but I think this is a variant of 3SUM? If this is true, then there would be no easy way to reduce it to under $$$O(n^2)$$$ time. Can we know the range of the array's elements? It may give a hint on whether FFT works or not.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yes, the only way to do it in O(nlogn) is using FFT, and that can be optimized a little more with blocks, like than we find the number of primes in the interval.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The input array $$$a_1, a_2, a_3, \dots, a_n$$$ is a permutation of $$$1, 2, \dots, n$$$ so all elements are distinct and $$$1 \leq a_i \leq n$$$.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now I am thinking if this problem may be some usage of prefix sum + suffix sum + DP, but I am not very sure on how. Can anyone help me on this approach?