Please Provide Editorial of Beautiful Array Problem

help
, , ,
1

Problem Statement-
An array a is called beautiful if for every pair of numbers ai, aj, (i ≠ j), there exists an ak such that ak = ai * aj. Note that k can be equal to i or j too.

Find out whether the given array a is beautiful or not

Please Provide the explanation for this
Problem.
Link-https://www.codechef.com/problems/ICPC16B

2

This problem is testing if you are able to come up with cases and explore various possibilities.

There are some key observations which will make the problem simple-

  1. An array of length 1 (n=1) is ALWAYS BEAUTIFUL (Contest admin’s clarification here )
  2. The question says array is beautiful if and only if we find a suitable Ak (such that Ak= Ai x Aj) for EVERY PAIR of i and j (and i!=j). This case is never possible if there are more than 2 elements such that their absolute value is more than 1. Take this example- {1,1,1,2,3}. Its not possible to find Ak for pair (2,3). Lets say we include 6 in the array, then array is {1,1,1,2,3,6} , now there is no Ak for (2,6) and (3,6). But arrays such as {0,0,1,1,6} or {0,0,0,3} etc. are beautiful.
  3. In view of above, we can conclude that the SECOND largest element should its value be one of these- {0,1}. If its not, then we can use theory of point 2 to prove that its not beautiful.
  4. What if we include -1 and one element whose absolute value is more than 1? Lets take {0,1,1,-1,3}. We can prove that this array is also, not beautiful.
  5. A simple solution is to keep 4 counter variables - Zero, one, minus_one, other. They will count the number of respective elements. Now we start making conditions
  6. If other>1 (meaning more than 1 number which has absolute value more than 1), then array isnt beautiful.
  7. If there is one element whose value is more than 1, and there is atleast one “-1” in the array, its not beautiful (refer to point 4)
  8. We also see that there is one corner case. What if Zero>0 , one==0 and minus_one>0 , other==0. I.e. for array where elements are only 0 and -1. We prove that for this case, if there are two or more “-1” in array, it wont be beautiful (as -1 x -1=1. But the array has only 0 and -1, so not beautiful).
  9. Based on point 8, we say that if one==0 and minus_one>1, then its not beautiful.
  10. Any other array is beautiful. We have covered all the possibilities where array is not beautiful, hence if no condition above holds, then array is beautiful.
3 Likes