Google Kickstart 2020 - Round A - Problem C - WorkOut

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 ?

this is the same mistake, I made initially.
please check with input -
1
2 3
1 121
correct output - 40

I understood the mistake. The above case seems valid considering my code as we can arrange sessions as “1 31 61 91 121” output should be 30 but considering the case 1 121 where we need to add 2 sessions only my output will fail as we can arrange sessions as “1 41 81 120” output will be 40 but my code gives output as 60. Thanks a lot @sunil5798 for your response.


Here is my approach.Find the maximum difference and insert middle number between it.
Got AC in 1st subtask and TLE in 2nd.