Doubt in maximum possible sweetness problem of starters 7

So , what I did for this problem was sort on basis of price first , otherwise sort on basis of sweetness , and then fix one candy , and then find other candy using binary search , but the code is giving WA , any help will be appreciated

Problem statement : Contest Page | CodeChef

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter wr = new PrintWriter(System.out);
		String temp = br.readLine();
		if(temp!=null){
		    long tc = Long.parseLong(temp);
		    while(tc>0){
		        temp = br.readLine();
		        if(temp!=null){
		            String split[] = temp.split(" ");
		            long n = Long.parseLong(split[0]);
		            long d = Long.parseLong(split[1]);
		            temp = br.readLine();
		            if(temp!=null){
		                split = temp.split(" ");
		                Pair arr[] = new Pair[split.length];
		                for(int i =0;i<arr.length;i++) arr[i] = new Pair();
		                for(int i = 0;i<arr.length;i++) arr[i].price = Long.parseLong(split[i]);
		                temp = br.readLine();
		                if(temp!=null){
		                    split = temp.split(" ");
		                    for(int i =0;i<arr.length;i++) arr[i].sweet = Long.parseLong(split[i]);
		                    Arrays.sort(arr);
		                    long max = 0;
		                    for(int i = arr.length-1;i>=0;i--){
		                        if(arr[i].price>d) continue;
		                        max = Math.max(max,arr[i].sweet+binarySearch(arr,i-1,d,arr[i].price));
		                    }
		                    wr.println(max);
		                    wr.flush();
		                    tc--;
		                }
		            }
		        }
		    }
		}
	}
	private static long binarySearch(Pair arr[] , int high , long dollar , long val){
	    int low = 0;
	    long ans = 0;
	    while(low<=high){
	        int mid = low + (high-low)/2;
	        if((arr[mid].price+val)<=dollar){
	            ans = arr[mid].sweet;
	            low = mid+1;
	        }else high = mid-1;
	    }
	    return ans;
	}
}
class Pair implements Comparable<Pair>{
    long sweet;
    long price;
    
    public Pair(long sweet ,long price){
        this.sweet = sweet;
        this.price = price;
    }
    public Pair(){
        
    }
    
    public int compareTo(Pair other){
        if(this.price!=other.price){
            if(this.price>other.price) return 1;
            return -1;
        }
        if(this.sweet>other.sweet) return 1;
        if(this.sweet<other.sweet) return -1;
        return 0;
    }
}

@darshancool25 can u provide a testcase where this will give WA ? I tried doing it using your approach but not using multi set

Finding a test case will be tough, though you can stress test by generating random cases and using setters code for getting correct answers !

1 Like

i was using binary search when function was not monotonic , thanks though !