Bird wa

[Snip3r]

spoj.pl/problems/BIRD/
the solution to above gives wa I m not sure where my logic goes wrong.can sme1 give a test case for which this fails?thx
ideone.com/nE6w8

[leppyr64]

Post your code inline here. Use the BBone tags to get the same functionality here.

[Snip3r]

here it is

import java.io.*;
class Bird{
        int test;
        int[][][] find;
        int[][][] given;
        boolean[][] isbird;
        int[][] lens;
        public static void main(String[] ar)throws Exception{
                new Bird().go();
        }
        void go()throws Exception{
                readIn();
                int minH,maxH,minW,maxW;
                int lh,rh,lw,rw;
                for(int i=0;i<test;i++){
                        minH=Integer.MAX_VALUE;minW=Integer.MAX_VALUE;maxH=0;maxW=0;
                        for(int j=0;j<lens[i][0];j++){
                                if(isbird[i][j]){
                                        if(given[i][j][0]<minH)
                                                minH=given[i][j][0];
                                        if(given[i][j][0]>maxH)
                                                maxH=given[i][j][0];
                                        if(given[i][j][1]<minW)
                                                minW=given[i][j][1];
                                        if(given[i][j][1]>maxW)
                                                maxW=given[i][j][1];
                                }
                        }
                        System.out.println("Case #"+(i+1)+":");
                        if(maxH!=0){
                                lh=0;rh=Integer.MAX_VALUE;
                                lw=0;rw=Integer.MAX_VALUE;
                                for(int j=0;j<lens[i][0];j++){
                                        if(!isbird[i][j]){
                                                if(given[i][j][0]>lh && given[i][j][0]<minH && given[i][j][1]>=minW && given[i][j][1]<=maxW)
                                                        lh=given[i][j][0];
                                                if(given[i][j][0]>maxH && given[i][j][0]<rh && given[i][j][1]>=minW && given[i][j][1]<=maxW)
                                                        rh=given[i][j][0];
                                                if(given[i][j][1]>lw && given[i][j][1]<minW && given[i][j][0]>=minH && given[i][j][0]<=maxH)
                                                        lw=given[i][j][1];
                                                if(given[i][j][1]>maxW && given[i][j][1]<rw && given[i][j][0]>=minH && given[i][j][0]<=maxH)
                                                        rw=given[i][j][1];
                                        }
                                }
                                for(int j=0;j<lens[i][1];j++){
                                        if(find[i][j][0]>=minH && find[i][j][0]<=maxH && find[i][j][1]>=minW && find[i][j][1]<=maxW)
                                                System.out.println("BIRD");
                                        else if(find[i][j][0]<=lh || find[i][j][0]>=rh || find[i][j][1]<=lw || find[i][j][1]>=rw)
                                                System.out.println("NOT BIRD");
                                        else
                                                System.out.println("UNKNOWN");
                                }
                        }
                        else{
                                boolean notbird;
                                for(int j=0;j<lens[i][1];j++){
                                        notbird=false;
                                        for(int k=0;k<lens[i][0];k++){
                                                if(given[i][k][0]==find[i][j][0] && given[i][k][1]==find[i][j][1]){
                                                        System.out.println("NOT BIRD");
                                                        notbird=true;
                                                        break;
                                                }
                                        }
                                        if(!notbird)
                                                System.out.println("UNKNOWN");
                                }
                        }
                }
        }
        void readIn()throws Exception{
                InputStreamReader in=new InputStreamReader(System.in);
                BufferedReader bf=new BufferedReader(in);
                test=Integer.valueOf(bf.readLine());
                find=new int[test][][];
                isbird=new boolean[test][];
                given=new int[test][][];
                int tot;String s[];
                lens=new int[test][2];
                for(int i=0;i<test;i++){
                        tot=Integer.valueOf(bf.readLine());
                        lens[i][0]=tot;
                        isbird[i]=new boolean[tot];
                        given[i]=new int[tot][2];
                        for(int j=0;j<tot;j++){
                                s=bf.readLine().split(" ");
                                if(s[2].equals("BIRD")){
                                        isbird[i][j]=true;
                                        given[i][j][0]=Integer.valueOf(s[0]);
                                        given[i][j][1]=Integer.valueOf(s[1]);
                                }
                                else{
                                        given[i][j][0]=Integer.valueOf(s[0]);
                                        given[i][j][1]=Integer.valueOf(s[1]);
                                }
                        }
                        tot=Integer.valueOf(bf.readLine());
                        lens[i][1]=tot;
                        find[i]=new int[tot][2];
                        for(int j=0;j<tot;j++){
                                s=bf.readLine().split(" ");
                                find[i][j][0]=Integer.valueOf(s[0]);
                                find[i][j][1]=Integer.valueOf(s[1]);
                        }
                }
        }
}

[leppyr64]

You have defined your "NOT BIRD" range on one variable, not both. For a bird to be "NOT BIRD" it has to satisfy the range of height and width of a "NOT BIRD".

[Snip3r]

For a bird to be "NOT BIRD" it has to satisfy the range of height and width of a "NOT BIRD".

according to u 3rd test case of the 1st sample input 1400 2020 is unknown isn't it?cos 1400 is within range of height of a bird 1000-2000

[leppyr64]

1
8
5 5 BIRD
5 10 BIRD
10 10 BIRD
10 5 BIRD
2 8 NOT BIRD
2 6 NOT BIRD
15 8 NOT BIRD
15 6 NOT BIRD
1
4 9

[leppyr64]

I'm not 100% certain that is the issue, but it's a guess. The problem isn't really clear. I don't know beyond a doubt what defines "NOT BIRD" and "UNKNOWN". judging by the fact that there are only 36 ACs for this, it's a pretty clear indication that the problem is awkward to understand.

[un_loco]

I don't know beyond a doubt what defines "NOT BIRD" and "UNKNOWN". judging by the fact that there are only 36 ACs for this, it's a pretty clear indication that the problem is awkward to understand.

I will try a rather "formal" definition of BIRD, NOTBIRD and UNKNOWN as I understood. Maybe it helps.

X = (hx,wx) is a animal
where hx: height, wx: weight

F = Infos from biologists
R = (Hmin,Hmax,Wmin,Wmax) is the unknown range of Birds.

X is a BIRD
<=> For all (possible) R's that satisfy F, X is (always) in R.

X is a NOTBIRD
<=> For all R's that satisty F, X is not in R.

X is UNKNOWN
<=> otherwise (i.e. You can find two ranges R1 and R2 satisfying F, so that X is in R1 (BIRD) but not in R2)

@Snip3r: I'm looking for a test case which fails...