Mountains TLE

Debugging Help
#1

Problem Info

This one.

Question

Is my algorithm wrong, or is Java just slow? Oddly enough, it seems to pass the last test case.

What I’ve Tried

I’ve downloaded the test data to see how many times the inner while loop in my code runs, and it’s never gone over the single-digit millions.

My Work

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

public class Mountains {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int mtnNum = Integer.parseInt(read.readLine());
        int[] mtns = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        assert mtns.length == mtnNum;

        int pairNum = 0;
        TreeSet<Slope>[] slopes = new TreeSet[mtnNum];
        for (int m = 0; m < mtnNum; m++) {
            slopes[m] = new TreeSet<>();
            for (int next = m + 1; next < mtnNum; next++) {
                double slope = (double) (mtns[next] - mtns[m]) / (next - m);
                if (next == m + 1 || slope >= slopes[m].last().slope) {
                    slopes[m].add(new Slope(next, slope));
                    pairNum++;
                }
            }
        }

        long total = 0;
        int queryNum = Integer.parseInt(read.readLine());
        StringBuilder ans = new StringBuilder();
        for (int q = 0; q < queryNum; q++) {
            StringTokenizer query = new StringTokenizer(read.readLine());
            int ind = Integer.parseInt(query.nextToken()) - 1;
            int amt = Integer.parseInt(query.nextToken());
            mtns[ind] += amt;

            pairNum -= slopes[ind].size();
            // yes, this is the exact same loop used just 10 lines above
            slopes[ind] = new TreeSet<>();
            for (int next = ind + 1; next < mtnNum; next++) {
                double slope = (double) (mtns[next] - mtns[ind]) / (next - ind);
                if (next == ind + 1 || slope >= slopes[ind].last().slope) {
                    slopes[ind].add(new Slope(next, slope));
                }
            }
            pairNum += slopes[ind].size();

            for (int m = 0; m < ind; m++) {
                double slope = (double) (mtns[ind] - mtns[m]) / (ind - m);
                Slope obj = new Slope(ind, slope);
                Slope compTo = slopes[m].lower(obj);
                if (compTo != null && compTo.slope > slope) {
                    continue;
                }
                pairNum -= slopes[m].size();
                slopes[m].remove(obj);  // because of how the treeset works
                slopes[m].add(obj);

                while (true) {
                    compTo = slopes[m].higher(obj);
                    if (compTo == null || compTo.slope >= slope) {
                        break;
                    }
                    slopes[m].remove(compTo);
                    total++;
                }
                pairNum += slopes[m].size();
            }
            ans.append(pairNum).append('\n');
        }

        System.out.print(ans);
        System.out.println(total);
    }

    private static class Slope implements Comparable<Slope> {
        public int to;
        public double slope;

        public Slope(int to, double slope) {
            this.to = to;
            this.slope = slope;
        }

        @Override
        public int compareTo(Slope o) { return to - o.to; }

        @Override
        public String toString() { return String.format("(%d,%f)", to, slope); }
    }
}

It maintains a monotonic set of slopes for each mountain.

#2

It’s likely that Java is just slow; we observed the same with our TreeSet solution.

#3

Nevermind- even with C++, my solution still TLEs:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

// #include "debugging.hpp"

using namespace std;  // too many lol

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int mtn_num;
    cin >> mtn_num;
    vector<int> mtns(mtn_num);
    for (int& m : mtns) {
        cin >> m;
    }

    int pair_num = 0;
    vector<set<pair<int, double>>> slopes(mtn_num);
    for (int m = 0; m < mtn_num; m++) {
        for (int next = m + 1; next < mtn_num; next++) {
            double slope = (double) (mtns[next] - mtns[m]) / (next - m);
            if (slopes[m].empty() || slope >= slopes[m].rbegin()->second) {
                slopes[m].insert({next, slope});
                pair_num++;
            }
        }
    }

    int query_num;
    cin >> query_num;
    for (int q = 0; q < query_num; q++) {
        int ind, amt;
        cin >> ind >> amt;
        int prev = mtns[--ind];
        mtns[ind] += amt;

        pair_num -= slopes[ind].size();
        // yes, this is the exact same loop used just 10 lines above
        slopes[ind].clear();
        for (int next = ind + 1; next < mtn_num; next++) {
            double slope = (double) (mtns[next] - mtns[ind]) / (next - ind);
            if (slopes[ind].empty() || slope >= slopes[ind].rbegin()->second) {
                slopes[ind].insert({next, slope});
            }
        }
        pair_num += slopes[ind].size();

        
        for (int m = 0; m < ind; m++) {
            double new_ = (double) (mtns[ind] - mtns[m]) / (ind - m);
            pair<int, double> obj{ind, new_};
            auto comp = slopes[m].lower_bound(obj);
            if (comp != slopes[m].begin() && (--comp)->second > new_) {
                continue;
            }

            pair_num -= slopes[m].size();
            double old = (double) (prev - mtns[m]) / (ind - m);
            slopes[m].erase({ind, old});

            auto higher = slopes[m].upper_bound(obj);
            while (higher != slopes[m].end() && new_ > higher->second) {
                higher = slopes[m].erase(higher);
            }
            slopes[m].insert(obj);

            pair_num += slopes[m].size();
        }

        cout << pair_num << '\n';
    }
}

The complexity should be correct though- I can’t figure out what’s taking so much time.

#4

The analysis solution that uses sets takes more than half the time limit despite being relatively optimized, so that’s not too surprising. You may need one of the optimizations from that solution.