Блог пользователя wish_me

Автор wish_me, история, 7 лет назад, По-английски

Given an array of n integers, count all different triplets whose sum is equal to the perfect cube i.e, for any i, j, k(i < j < k) satisfying the condition that a[i] + a[j] + a[j] = X3 where X is any integer. 3 ≤ n ≤ 1000, 1 ≤ a[i, j, k] ≤ 5000

Input:

N = 5

2 5 1 20 6

Output:

3

Explanation:

There are only 3 triplets whose total sum is a perfect cube.

Indices Values SUM

0 1 2 2 5 1 8

0 1 3 2 5 20 27

2 3 4 1 20 6 27

Since 8 and 27 are prefect cube of 2 and 3.

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

The maximum possible value of a[i]+a[j]+a[k] can be 15000. There are 24 perfect cubes less than 15000. You can check if there exists (i,j,k) for a given perfect cube in O(n*n) using two pointers. The overall complexity will be O(24*n*n).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did this.I am looking for better approach?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      There's an O(m*logm) solution using FFT where m is the maximum sum. Let A be the polynomial where a[i] = frequency of i, the answer for each sum will be on the coeficients of something like:

      A^3 — polynomial of choosing 3 of the same index — polynomial of choosing 2 of the same index

      I won't explain further, if you want to know more details solve FFT problems and maybe read this: http://codeforces.net/blog/entry/43499

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you further describe the two pointer approach @TooDumbToWin? And I assume that the array must be sorted before using such an approach?