Problem with ICPC16B Beautiful Arrays

acm-icpc
admin

#1

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.


#2

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


#3

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


#4

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.


#5

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”


#6

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…


#7

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:


#8

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)


#9

can anyone tell the way to solve this problem…


#10

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…


#11

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. :)


#12

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

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


#13

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


#14

@akhii1998 The reason you got WA is because you are storing the product of a* & a[j] in the integer variable whereas integer limit is 2 * 10^9 and product can go about 10^18. However, that is not you should be worried about. Since you are beginner I think you are not yet aware of the term Time Complexity .( check this links or search on web to know about Time Complexity: https://www.quora.com/What-are-some-easy-ways-to-understand-and-calculate-the-time-complexity-of-algorithms https://www.quora.com/I-am-getting-“Time-Limit-Exceeded”-response-for-several-problems-on-Codechef-How-should-I-optimize-my-code/answer/Vaibhav-Tulsyan ) You are running two loops to choose a* and a[j] and size of the array can be upto 10^5 . Then 2 select every 2 combination you are using 10^5 Choose 2 iteration which is in the order of 10^10. And again you are linear searching , suppose the product is not present in array, then you have to again traverse 10^5 elements. So your complexity can go up-to 10^15 iterations which can take years to execute because normally PC executes 10^8 to 10^9 iterations per second of C/C++ code.

Hence, to reduce the time complexity you need to think about other logic, better logic than needs few number of iterations. So try your best to come up with better approach by making some observations(Use pen and notebook :P). And, if stuck can have a look at working solution here : https://www.codechef.com/viewsolution/ .

Cheers , happy coding and learning .


#15

anbody can help me why my code is wrong?

#include<stdio.h>
int main()
{
int a,b,c,d,k,h=0,y,i=1,j[100000];
scanf("%d
“,&a);
start:scanf(”%d
",&b);
d=b-1;
y=b;
while(b!=0)
{

scanf("%d",&c);
j*=c;
	
i++;
b--;
}
for(i=1;d>=1;d--,i++)
{
	k=j*;
	k=k*j[i+1];
}
for(i=1;i<=y;i++)
{
	
	if(k==j*)
	{
		h++;
	
	}
}
if(h!=0)
{
	printf("yes

");
a–;
}
else if(h>0)
{
printf("no
");
a–;
}
if(a!=0)
{
goto start;
}
return 0;
}


#16

I have a problem with this task !
I have another solution more complicated

i have tested for several examples and it works , but every time i submitt , it gives “wrong answer” , i don’t know why ?!!

package beginner;

import java.io.;
import java.util.
;

import java.lang.*;

public class BeautifulArraysICPC16B {

// static int max ;
// static int min;
// static int occMax ;
// static int occMin ;

static class InputReader {
	public BufferedReader buff;
	public StringTokenizer token;

	public InputReader(InputStream stream) {
		buff = new BufferedReader(new InputStreamReader(stream), 32768);
		token = null;
	}

	public String next() {
		while (token == null || !token.hasMoreTokens()) {
			try {
				token = new StringTokenizer(buff.readLine());
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

		}
		return token.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

}


public static int max(int[] tab){
		int max = tab[0]; 
		for(int i=0 ; i< tab.length ;i++){
			if(tab* > max) {max = tab* ;}
		}
		return max;
	}

	
public static int min(int[] tab){
		int min = tab[0]; 
		for(int i=0 ; i< tab.length ;i++){
			if(tab* < min) {min = tab* ;}
		}
		return min;
	}
	
	
public static  int firstocc(int[] tab  , int a){
		int j = -1 ; 
		do{
			j++;
			
		}while(tab[j]!=a && j <tab.length);
		
		if(j< tab.length) return j ;
		else return -1;
	}
	

public static void main(String[] args) {
	// TODO Auto-generated method stub

	InputStream inputStream = System.in;
	OutputStream outputStream = System.out;
	InputReader in = new InputReader(inputStream);
	PrintWriter out = new PrintWriter(outputStream);

	int T = in.nextInt();
	for (int i = 0 ; i < T ; i++){
		int n = in.nextInt();
		int[] tab = new int[n];

		for(int j=0 ; j< tab.length ; j++){
			tab[j] = in.nextInt();
		}
		
		int max = max(tab);
		
		int min = min(tab);
		
		int occMax = firstocc(tab, max);
		
		int occMin = firstocc(tab, min);
		
		boolean t = true ;

// if(n==1) {
// out.println(“no”);
// }else

			if(max>1){
			int l = 0 ;
			while(l < tab.length && t){
				if(l!=occMax){t=(tab[l]==1 || tab[l]==0);}
				if(!t){out.println("no");break;}
				l++;
			}
			if (l==tab.length) out.println("yes");
			
			
		}else if(min<-1){
			int l = 0 ;
			while(l < tab.length && t){
				if(l!=occMin){t=(tab[l]==1 || tab[l]==0);}
				if(!t){out.println("no");break;}
				l++;
			}
			if (l==tab.length) out.println("yes");
			
		}else if(min==-1 && max==-1){
			out.println("no");
		}else{
			out.println("yes");
		}
		
	}
	


	out.close();
}

}


#17

well i have a doubt in this problem,shouldn’t the array for example {1,-1,2} be not beautiful as -1*2 = -2 as there is no such element therefore {1,-1,2} should not be beautiful but in few of the successful submissions this array comes out to be a beautiful array and i submitted both mine(which shows the above example to be not beautiful) and the other codechef seemed to accept the other one.I think there is a problem in the solution from there end MAYBE.So pls somebody help and pls tell where i am going wrong?


#18

#include

using namespace std;

int main() {
int k;
cin>>k;
for(int j=1;j<=k;j++)
{
int n;
cin>>n;
int a[n],sum=1,i,count=0;

for(i=0;i<n;i++)
{
    cin>>a*;
}
for(i=0;i<n;i++)
{
    sum*=a*;
}
	for(i=0;i<n;i++){
if(sum==a*)
{
   count++;
}
}
if(count>=1)
{
    cout<<"yes"<<endl;
}
else
{
    cout<<"no";
    
}
}
return 0;

}
pls…Anyone look at this code…pls tell me what is wrong with this… I an getting the correct answer in all other compilers.But code chef states it as wrong answer… PLS HELP ANYONE…PLS…PLS…PLS…


#19

import java.util.;
import java.lang.
;
import java.io.;
class BeautifulArray {
public static void main(String args[])throws java.lang.Exception{
Scanner in=new Scanner(System.in);
int testc=in.nextInt();
for(int c=0;c<testc;c++){
int n=in.nextInt();
int i,j,temp=0,k,flag=0,fflag=0;
int a[]=new int[n];
for(i=0;i<n;i++){
a
=in.nextInt();
}
for(i=0; i < n; i++){
for(j=1; j < (n-i); j++){
if(a[j-1] > a[j]){
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
fflag=0;
for(i=1;i<n;i++){
flag=0;
for(j=0;j<=i;j++){
if(a[j]!=0){
if(a*%a[j]==0){
for(k=j+1;k<=i;k++){
if(a*/a[j]==a[k]){
flag=1;
break;
}
}
if(flag==1)
break;
}
}
}
if(flag==0){
fflag=1;
break;
}
}
if(fflag==1)
System.out.println(“no”);
else
System.out.println(“yes”);
}

    }
}


What is wrong in my code?

#20

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.