Problem with ICPC16B Beautiful Arrays

The problem goes as follows :
“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.”
So for n==1, there do not exist any pairs and hence the array is not supposed to be “Beautiful”.
But the way test cases turned out, the array was supposed to be “Not Beautiful”
Kindly check into it the same.

1 Like

man, you gave me a shock for a minute. “But the way test cases turned out, the array was supposed to be “Not Beautiful” Kindly check into it the same.” It is wrong. Test cases doesn’t say that n = 1 is not beautiful. n = 1 is beautiful by definition.

An array a is called beautiful if for every pair of numbers ai, aj, (i ≠ j). There does not exist any pair in the first place, and for a n==1, we cannot have i!=j. So wouldn’t the default answer for n==1 be “Not Beautiful”.
Didn’t mean to shock you but kindly look into this.

An application of some definition should work in this way, take the definition, apply on your object (in this case array), if it violates the conditions, then the array is bad, otherwise it is good. Now, our example for n = 1, there are no two i, j such that i != j, so the array is good implicitly. This type of statements are called vacuously true.

2 Likes

wow… Great… the intricacies of knowledge… !! “Vacuously” … shaandaar

Okay, thank you. Perfectly fine :slight_smile:

answer for n=1 should be “no” because it is clearly stated in question that for pair (i,j) i!=j

yes . the answer should be “no” for n=1 , because we cannot have a pair (i,j) such that i!=j. Kindly look into this please.

The problem clearly says that “for every pair of numbers…”. For n = 1, no pair exists, hence there is no need to check for the second condition. Hence the answer is “yes”

4 Likes

The answer for n=1, should be “no”… Vacuous True cases are when we don’t have any condition that rejects the case, but here it is clearly stated that i! =j, so it is a “no” here… Please look into this…

The question clearly states that “if there exists pairs and those are not beautiful then output no”…But for n=1,there are no pairs to violate the above condition… Hence the answer will be “Yes”… :slight_smile:

2 Likes

I just cannot believe this. I made -5 submissions in this questions having total faith that for n=1 the answer must be no. I guess the basic definition is being rejected “i!=j” (1st index!=1st index)

3 Likes

You can refer to my answer above

can anyone tell the way to solve this problem…

Why was time not extended???I submitted at 14 minutes left and got result when 20 seconds were left and That too a compilation error…
Should not they have extended the time by 15 minutes???They often do it in cook off !!
I missed a chance to go to Amritapuri…

1 Like

As mentioned above, it’s a vacuous truth statement.

It uses the fact that whenever an implication p=>q is given, and if p itself is false, it doesn’t matter whether q is true or not and the statement is considered true.

In our case, p = “if there exists a pair”, which is false for n=1, making the assertion true by default.

You can also use the equivalent relation ~p+q for p=>q, meaning either of ~p or q being true for the statement to be true;

This statement, when viewed in it’s equivalent terms, would be read as:

“If there doesn’t exist any pair (i,j) OR there exists an ak…”

Since the first condition holds for n=1, the statement is implicitly true.

P.S I didn’t know about vacuous truth statements either and I submitted the answer with a “no” as well. Learnt something new, and I hope you did too now. :slight_smile:

3 Likes

Yeah!Thanks.

Please review my code i am new in coding.I am getting time limit exceeded error

https://www.codechef.com/viewsolution/13239918

https://www.codechef.com/viewsolution/13226331 the code is readable and logic is surely easy to understand.

1 Like

Can SomeOne plz tell me that what is the problem with my solution.
https://www.codechef.com/viewsolution/13382532