Getting WA in problem code STACKS

CodeChef-DSA-learners
, , ,
1

MY APPROACH
I have an array which stores the top disk of each stack. If the max of this array < new disk, a new stack is created. If max > new disk size, I do a binary search in the array to find the index of disk just greater than the new disk and then replace that with the new disk.

CODE

   static int lowest_just_greater(ArrayList<Integer> ar, int k){
      int l=0, r=ar.size()-1;
      int ans=0;
      while(l<=r){
        int mid= l+(r-l)/2;
        // if(ar.get(mid)==k) return mid+1;
        if(ar.get(mid)>k) {
          ans=mid;
          r=mid-1;
        }
        else l=mid+1;
      }
      return ans;
    }
    public void solveTheProblem(InputReader in,OutputWriter out, NumberTheory nt){
      int test=in.nextInt();
      while(test-- >0){
        int n=in.nextInt();
        int ar[]= new int[n];
        // for(int i=0;i<n;i++) ar[i]=Integer.MAX_VALUE;
        int max=-1;
        int size=0;
        ArrayList<Integer> stacks= new ArrayList<>();
        stacks.add(in.nextInt());
        max=stacks.get(0);
        // ar[size++]=in.nextInt();
        // max=ar[0];
        for(int i=1;i<n;i++){
          int temp=in.nextInt();
          // int k=lowest_just_greater(stacks, temp);
          // if(stacks.get(k)>temp) stacks.set(k, temp);
          // else stacks.add(temp);
          if(temp>=max){
            max=temp;
            stacks.add(max);
            // ar[size++]=temp;
          }
          else{
            int k= lowest_just_greater(stacks, temp);
            // System.out.printf("temp: %d\n", temp);
            // int k=lowest_just_greater_array(ar, temp);
            if(stacks.get(k)==max) max=temp;
            // if(ar[k]==max) max=temp;
            // System.out.println("--- max: "+max);
            // System.out.println("no: "+temp+" pos: "+k);
            stacks.set(k, temp);
            // ar[k]=temp;
          }
        }
        // out.print(size+" ");
        // String s=stacks.size()+"";
        // String s=stacks.size()+"";
        // for(int i:stacks) s+=" "+i;
        out.print(stacks.size());
        for(int i:stacks) out.print(" "+i);
        // for(int i=0;i<size;i++) s+=ar[i]+" ";
        out.println();
      }
    }

The submission link:

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

Any help appreciated.

2

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

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

Can anyone tell me the difference between the two approaches. I think they are both the same but one is getting WA.

3

Instead of the commented part, if I do this

for(int i=1;i<n;i++){
          int temp=in.nextInt();
          int k=lowest_just_greater(stacks, temp);
          if(stacks.get(k)>temp) stacks.set(k, temp);
          else stacks.add(temp);
          // if(temp>=max){
          //   max=temp;
          //   stacks.add(max);
          //   // ar[size++]=temp;
          // }
          // else{
          //   int k= lowest_just_greater(stacks, temp);
          //   // System.out.printf("temp: %d\n", temp);
          //   // int k=lowest_just_greater_array(ar, temp);
          //   if(stacks.get(k)==max) max=temp;
          //   // if(ar[k]==max) max=temp;
          //   // System.out.println("--- max: "+max);
          //   // System.out.println("no: "+temp+" pos: "+k);
          //   stacks.set(k, temp);
          //   // ar[k]=temp;
          // }
        }

I am getting AC. What is the difference?