dca's blog

Some idea regarding this problem
By dca, history, 4 years ago, In English

I am given an integer array $$$A$$$ of size $$$N$$$. I want to make a multiset from $$$A$$$ such that, if any two elements of the multiset are multiplied, the product should not be a perfect cube. What is the maximum size of the multiset? I can only think of the bruteforce approach. Can we solve it in some efficient way? For example, if A=[1,2,4]. We can create a multiset M=[1,2]. As multiplication of 1*2 is not a cube. Similarly, M can also be [1,4], but not [1,2,4] as 2*4=8, is a cubic number. $$$N<=1000$$$, $$$1$$$ $$$<=Ai<=$$$ $$$10^6$$$

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

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is an integer A of size N? How can we make a multiset of that integer?

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

    I think he meant integer array of size N.

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

      Ok. And there are some rules how to "make a multiset" from A. Isn't these rules the core of the problem?

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

        Maybe its about picking up numbers from array A and putting them in a bucket ( multiset in this case ) which is technically again like choosing a sub-sequence from array A without the "order" rule.

        → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What are the limits on N ?

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

Factorize the numbers from $$$A$$$. Now, in order for the product of two numbers to be a perfect cube, that means that every prime number must appear a number of times multiple of $$$3$$$ in the factorization of their product.

This means that it makes sense to elliminate triplets of $$$3$$$ equal primes from the representations of each number. Afterwards, in this reduced form, for a number $$$x$$$ there is only one other number $$$y$$$ such that $$$x y$$$ is a perfect cube (try to understand why, and how this number $$$y$$$ looks like). So, if you take number $$$x$$$, you must not take $$$y$$$ (and vice versa).

To solve the actual problem, just compute a frequency map of all numbers $$$x$$$ in reduced form and take the maximum of $$$cnt(x), cnt(rev(x))$$$ ($$$rev(x)$$$ is the unique other number such that $$$x \cdot rev(x)$$$ is a cube).

Numbers that are perfect cubes in the input have to be treated separately.

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

    Thank you. I too tried in a similar approach, but got partial points there and rest TLE. The ones who appeared for the test, they said, they solved this using Maximum Independent Set. But I am not getting the idea of how can we deduce this problem to graph.

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

      Probably your implementation had some bugs or the idea was different in some aspect, thus solution is $$$O(N sqrt(max(A))$$$ or $$$O((N + A) log(max(A)))$$$ depending on how you implement the factorization, which is more that enough to fit the TL.

      → Reply