I was trying to solve Wormholes (Problem Code: ZCO12002) on CodeChef. I am getting AC on test-cases 0,9 and 15. All others are giving RE (NZEC). I am iterating over the contests and then searching for the best wormhole through modified Binary Search.
Here is my code -
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws IOException{
Main m = new Main();
m.start();
}
public void start() throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line1 = br.readLine().split(" ");
int n = Integer.parseInt(line1[0]);
int x = Integer.parseInt(line1[1]);
int y = Integer.parseInt(line1[2]);
Contest[] contests = new Contest[n];
for(int i = 0;i<n;i++){
String[] line = br.readLine().split(" ");
Contest c = new Contest(Integer.parseInt(line[0]),Integer.parseInt(line[1]));
contests[i] = c;
}
int[] entries = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] exits = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Arrays.sort(entries);
Arrays.sort(exits);
int least_time_spent = Integer.MAX_VALUE;
for(int i = 0;i<n;i++) {
Contest c= contests[i];
int start = searchA(entries,0,x-1,c.start);
int end = searchB(exits,0,y-1,c.end);
least_time_spent = Math.min(least_time_spent,end-start+1);
}
System.out.println(least_time_spent);
}
class Contest{
int start;
int end;
public Contest(int s, int e){
start = s;
end = e;
}
}
public int searchA(int[] a,int left,int right, int o){//BinarySearch for max value less than or equal o
int mid = (left+right)/2;
if(left-right==0){
if(a[left-1]>o){
return -1;
}
return a[left-1];
}else if(a[mid]==o){
return a[mid];
}else if(o>a[mid]){
return searchA(a,mid+1,right,o);
}else if(o<a[mid]){
return searchA(a,left,mid,o);
}else{
return 0;
}
}
public int searchB(int[] a,int left,int right, int o){//BinarySearch for min value greater than or equal o
int mid = (left+right)/2;
if(right-left==0){
if(a[left]<o){
return Integer.MAX_VALUE;
}
return a[left];
}else if(a[mid]==o){
return a[mid];
}else if(o>a[mid]){
return searchB(a,mid+1,right,o);
}else if(o<a[mid]){
return searchB(a,left,mid,o);
}else{
return 0;
}
}
}
Feel free to ask for any clarifications. It would be a great help if you can tell me the test-case where my code is throwing exception.