You are not logged in. Please login at www.codechef.com to post your questions!

×

Problem with ICPC16B Beautiful Arrays

0
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.

asked 22 Oct '16, 22:17

raunak_parijat's gravatar image

4★raunak_parijat
8726
accept rate: 0%

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.

(22 Oct '16, 22:21) dpraveen ♦♦4★

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.

(22 Oct '16, 22:25) raunak_parijat4★
4

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.

(22 Oct '16, 22:30) dpraveen ♦♦4★

Okay, thank you. Perfectly fine :)

(22 Oct '16, 23:14) raunak_parijat4★

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"

link

answered 23 Oct '16, 07:52

saeedjassani's gravatar image

3★saeedjassani
41
accept rate: 0%

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)

link

answered 23 Oct '16, 11:10

ssaxena36's gravatar image

5★ssaxena36
7665
accept rate: 28%

You can refer to my answer above

(23 Oct '16, 11:12) naksh96194★

Yeah!Thanks.

(23 Oct '16, 18:07) ssaxena365★

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

https://en.wikipedia.org/wiki/Vacuous_truth

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

link

answered 23 Oct '16, 15:32

epsilonalpha's gravatar image

4★epsilonalpha
10516
accept rate: 25%

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

link

answered 23 Oct '16, 10:55

naksh9619's gravatar image

4★naksh9619
6196
accept rate: 12%

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

link

answered 23 Oct '16, 11:29

tumblehead's gravatar image

2★tumblehead
11
accept rate: 0%

wow.... Great.... the intricacies of knowledge.. !! "Vacuously" ... shaandaar

link

answered 22 Oct '16, 22:37

chari407's gravatar image

2★chari407
44827
accept rate: 0%

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

link

answered 23 Oct '16, 01:02

deepanshu_'s gravatar image

3★deepanshu_
1
accept rate: 0%

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.

link

answered 23 Oct '16, 07:11

abishek_k's gravatar image

4★abishek_k
611
accept rate: 50%

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

link

answered 23 Oct '16, 10:27

ksut28's gravatar image

3★ksut28
313
accept rate: 0%

edited 23 Oct '16, 10:28

can anyone tell the way to solve this problem..

link

answered 23 Oct '16, 11:17

shivam_sri08's gravatar image

2★shivam_sri08
1
accept rate: 0%

1

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

(09 Apr '17, 13:26) pankajkhan5★

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

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

link

answered 09 Apr '17, 00:32

gshivam63's gravatar image

2★gshivam63
1
accept rate: 0%

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

link

answered 24 Apr '17, 10:06

akhii1998's gravatar image

1★akhii1998
1
accept rate: 0%

@akhii1998 The reason you got WA is because you are storing the product of a[i] & 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-%E2%80%9CTime-Limit-Exceeded%E2%80%9D-response-for-several-problems-on-Codechef-How-should-I-optimize-my-code/answer/Vaibhav-Tulsyan ) You are running two loops to choose a[i] 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 .

link

answered 24 Apr '17, 10:52

pankajkhan's gravatar image

5★pankajkhan
1.2k10
accept rate: 15%

edited 24 Apr '17, 10:53

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\n",&a); start:scanf("%d\n",&b); d=b-1; y=b; while(b!=0) {

scanf("%d",&c);
j[i]=c;

i++;
b--;
}
for(i=1;d>=1;d--,i++)
{
    k=j[i];
    k=k*j[i+1];
}
for(i=1;i<=y;i++)
{

    if(k==j[i])
    {
        h++;

    }
}
if(h!=0)
{
    printf("yes\n");
    a--;
}
else if(h>0)
{
    printf("no\n");
    a--;
}
if(a!=0)
{
    goto start;
}
return 0;

}

link

answered 28 Apr '17, 01:31

amitkumar66's gravatar image

0★amitkumar66
1
accept rate: 0%

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[i] > max) {max = tab[i] ;}
        }
        return max;
    }


public static int min(int[] tab){
        int min = tab[0]; 
        for(int i=0 ; i< tab.length ;i++){
            if(tab[i] < min) {min = tab[i] ;}
        }
        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();
}

}

link

answered 05 May '17, 20:27

procoder007's gravatar image

2★procoder007
1
accept rate: 0%

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?

link

answered 10 May '17, 13:06

eliminated1's gravatar image

0★eliminated1
1
accept rate: 0%

include <iostream>

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[i];
}
for(i=0;i<n;i++)
{
    sum*=a[i];
}
    for(i=0;i<n;i++){
if(sum==a[i])
{
   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..

link

answered 21 May '17, 18:13

sreeshu's gravatar image

0★sreeshu
01
accept rate: 0%

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[i]=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[i]%a[j]==0){
                       for(k=j+1;k<=i;k++){
                           if(a[i]/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?
link

answered 26 Jul '17, 00:14

veda_19's gravatar image

2★veda_19
11
accept rate: 0%

edited 26 Jul '17, 00:26

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

1

For n=1, array is beautiful. AFter accounting for this, you will get TLE. Make some observations on when an array can be beautiful. Take an array of-

only 0, 0 and 1 0,1 and >=2 elements with abs(arr[i])>1

These 3 will give you a direction to think.

(26 Jul '17, 00:27) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,427
×1,112

question asked: 22 Oct '16, 22:17

question was seen: 7,839 times

last updated: 26 Jul '17, 00:28