Please refer to the problem statement from here
My approach to the above problem was, have a max heap where each node has structure
INTERVAL<difficullty,low,high>
and ordering of each interval is based on difficulty. For each additional insertion I peek the maximum, split it and remove max and add two nodes to heap, if at any point while peeking the maximum the difficulty is 1, I stop my code and print the optimal difficulty by peeking the maximum available in heap. The language used for coding is JAVA. instead of heap I used TreeSet, so the time complexity would be O(K log N) where K could be up to 10^5 and a few N could be up to 10^5
Code
package googlekickstart.rounda2020.workout;
// coded by Krishna Sundar //
import java.lang.*;
import java.io.*;
import java.util.*;
public class Solution {
private static class Interval {
private int weight;
private int low;
private int high;
public Interval(int weight, int low, int high) {
this.weight = weight;
this.low = low;
this.high = high;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Interval interval = (Interval) o;
return weight == interval.weight &&
low == interval.low &&
high == interval.high;
}
@Override
public int hashCode() {
return Objects.hash(weight, low, high);
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getLow() {
return low;
}
public void setLow(int low) {
this.low = low;
}
public int getHigh() {
return high;
}
public void setHigh(int high) {
this.high = high;
}
}
public void solve(Read input, Write output) throws Exception {
int cases = input.readInt(), k=1;
while (cases-->0) {
int N = input.readInt();
int K = input.readInt();
int[] arr = new int[N];
for (int i=0;i<N;i++) {
arr[i] = input.readInt();
}
TreeSet<Interval> max = new TreeSet<Interval>(new Comparator<Interval>() {
@Override
public int compare(Interval interval1, Interval interval2) {
int result = Integer.compare(interval1.getWeight(), interval2.getWeight());
if (result != 0) {
return -result;
} else {
result = Integer.compare(interval1.getLow(), interval2.getLow());
if (result != 0) {
return -result;
} else {
result = Integer.compare(interval1.getHigh(), interval2.getHigh());
return -result;
}
}
}
});
for (int i=1;i<N;i++) {
max.add(new Interval(arr[i]-arr[i-1], arr[i-1], arr[i]));
}
for (int i=0;i<K;i++) {
Interval maximum = max.first();
if (maximum.getWeight()==1) {
break;
}
int l = maximum.getLow();
int h = maximum.getHigh();
int mid = ((l+h)>>1);
max.pollFirst();
max.add(new Interval(mid-l, l, mid));
max.add(new Interval(h-mid, mid, h));
}
output.printLine("Case #"+k+": "+max.first().getWeight());
output.flush();
k++;
}
}
public static void main(String[] args) throws Exception {
Read input = new Read();
Write output = new Write();
Solution D = new Solution();
D.solve(input, output);
output.flush();
output.close();
}
// java fast io reader and writer
// taken from various sources and customized
static class Read {
private byte[] buffer =new byte[10*1024];
private int index;
private InputStream input_stream;
private int total;
public Read() {
input_stream = System.in;
}
public int read()throws IOException {
if(total<0)
throw new InputMismatchException();
if(index>=total) {
index=0;
total= input_stream.read(buffer);
if(total<=0)
return -1;
}
return buffer[index++];
}
public long readLong() throws IOException {
long number=0;
int n= read();
while(isWhiteSpace(n))
n= read();
long neg=1l;
if(n=='-') {
neg=-1l;
n= read();
}
while(!isWhiteSpace(n)) {
if(n>='0'&&n<='9') {
number*=10l;
number+=(long)(n-'0');
n= read();
}
else throw new InputMismatchException();
}
return neg*number;
}
public int readInt() throws IOException {
int integer=0;
int n= read();
while(isWhiteSpace(n))
n= read();
int neg=1;
if(n=='-') {
neg=-1;
n= read();
}
while(!isWhiteSpace(n)) {
if(n>='0'&&n<='9') {
integer*=10;
integer+=n-'0';
n= read();
}
else throw new InputMismatchException();
}
return neg*integer;
}
public double readDouble()throws IOException {
double doub=0;
int n= read();
while(isWhiteSpace(n))
n= read();
int neg=1;
if(n=='-') {
neg=-1;
n= read();
}
while(!isWhiteSpace(n)&&n!='.') {
if(n>='0'&&n<='9') {
doub*=10;
doub+=n-'0';
n= read();
}
else throw new InputMismatchException();
}
if(n=='.') {
n= read();
double temp=1;
while(!isWhiteSpace(n)) {
if(n>='0'&&n<='9') {
temp/=10;
doub+=(n-'0')*temp;
n= read();
}
else throw new InputMismatchException();
}
}
return doub*neg;
}
public String readString()throws IOException {
StringBuilder sb = new StringBuilder();
int n = read();
while (isWhiteSpace(n))
n = read();
while (!isWhiteSpace(n)) {
sb.append((char)n);
n = read();
}
return sb.toString();
}
private boolean isWhiteSpace(int n) {
if(n==' '|| n=='\n'|| n=='\r'|| n=='\t'|| n==-1)
return true;
return false;
}
}
static class Write {
private final BufferedWriter bw;
public Write() {
bw = new BufferedWriter(new OutputStreamWriter(System.out));
}
public void print(String str) throws IOException {
bw.append(str);
}
public void printLine(String str) throws IOException {
print(str);
bw.append("\n");
}
public void close()throws IOException {
bw.close();
}
public void flush()throws IOException {
bw.flush();
}
}
}
Verdict for small test cases all passed
Verdict for large test cases WA
I’ve read the analysis for the problem for alternate ideas but I want to know what is wrong with the approach mentioned above ?
