TLE at Target Complexity

#1

Hi everyone,
I’ve been doing this problem and used a \mathcal{O}(N \log N) 2P sort of approach to do it. It’s very similar to that described in the editorial, but it still seems to TLE.

#include <iostream>
#include <cassert>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;  // too many things to use, i give up

// https://codeforces.com/contest/1627/problem/E (sample omitted due to length)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int test_num;
    cin >> test_num;
    for (int t = 0; t < test_num; t++) {
        int floor_num, room_num;
        int ladder_num;
        // cout << "init done" << endl;

        cin >> floor_num >> room_num >> ladder_num;
        vector<long long> floors(floor_num);
        for (long long& f : floors) {
            cin >> f;
        }

        // cout << "floors done" << endl;

        vector<vector<int>> floor_starts(floor_num);
        vector<vector<int>> floor_ends(floor_num);
        map<pair<int, int>, vector<pair<pair<int, int>, int>>> ladders;
        for (int l = 0; l < ladder_num; l++) {
            int s_floor, s_room;
            int e_floor, e_room;
            int health;
            cin >> s_floor >> s_room >> e_floor >> e_room >> health;
            assert(s_floor < e_floor);

            floor_starts[--s_floor].push_back(--s_room);
            floor_ends[--e_floor].push_back(--e_room);
            ladders[{s_floor, s_room}].push_back({{e_floor, e_room}, health});
        }
        floor_starts[floor_num - 1].push_back(room_num - 1);
        floor_ends[0].push_back(0);

        // cout << "ladders done" << endl;
        
        for (int f = 0; f < floor_num; f++) {
            sort(floor_starts[f].begin(), floor_starts[f].end());
            sort(floor_ends[f].begin(), floor_ends[f].end());
        }

        vector<map<int, long long>> min_cost(floor_num);
        min_cost[0][0] = 0;
        for (int f = 0; f < floor_num; f++) {
            map<int, long long>& curr = min_cost[f];
            if (curr.empty()) {
                continue;
            }
            vector<int> ends;
            for (int e : floor_ends[f]) {
                if (curr.count(e)) {
                    ends.push_back(e);
                }
            }

            vector<long long> pref_min(ends.size());
            pref_min[0] = curr[ends[0]];
            for (int e = 1; e < ends.size(); e++) {
                pref_min[e] = std::min(
                    curr.count(ends[e]) ? curr[ends[e]] : INT64_MAX,
                    pref_min[e - 1] + floors[f] * (ends[e] - ends[e - 1])
                );
            }

            vector<long long> suff_min(ends.size());
            suff_min[ends.size() - 1] = curr[ends[ends.size() - 1]];
            for (int e = ends.size() - 2; e >= 0; e--) {
                suff_min[e] = std::min(
                    curr.count(ends[e]) ? curr[ends[e]] : INT64_MAX,
                    suff_min[e + 1] + floors[f] * (ends[e + 1] - ends[e])
                );
            }
            
            int end_at = 0;
            for (int s : floor_starts[f]) {
                while (end_at < ends.size() && ends[end_at] <= s) {
                    end_at++;
                }
                
                curr[s] = INT64_MAX;
                if (end_at > 0) {
                    curr[s] = 
                        pref_min[end_at - 1] + floors[f] * (s - ends[end_at - 1]);
                }
                if (end_at < ends.size()) {
                    curr[s] = std::min(
                        curr[s],
                        suff_min[end_at] + floors[f] * (ends[end_at] - s)
                    );
                }
                
                if (f != floor_num || s != room_num) {
                    for (auto [next, hp] : ladders[{f, s}]) {
                        if (!min_cost[next.first].count(next.second)) {
                            min_cost[next.first][next.second] = INT64_MAX;
                        }
                        long long& dest = min_cost[next.first][next.second];
                        dest = std::min(dest, curr[s] - hp);
                    }
                }
            }
        }

        if (!min_cost[floor_num - 1].count(room_num - 1)) {
            cout << "NO ESCAPE" << '\n';
        } else {
            cout << min_cost[floor_num - 1][room_num - 1] << '\n';
        }
    }
}

The thing is, I added the debug prints that are commented out in the example code, and it seems that the majority of the time is taken on IO! Is there any reason for this? Or is adding these debug prints just a bad way to profile my code?

#2

If the problem is actually the IO, you can try this to speed it up.

#3

Is there any method to see if it’s actually the IO though? Or do I just plug that in and find out?

#4

It shouldn’t take long to plug in, since everything is already packaged nicely into functions.

#5

Actually no- I tried aborting the program after reading the IO, and it gave me a WA instead of a TLE. I’m still not sure what’s so slow about my actual algorithm though.
Could my code possibly be running into an infinite loop? It’s really unlikely though. Is there a way to detect if that’s happening or no?

#6
  • replace push_back with emplace_back
  • replace pair<int, int> with array<int, 2>
  • replace some of the vectors/maps with arrays if possible
#7

I tried that, but sadly it doesn’t seem to have any affect on the runtime.

#8

From https://usaco.guide/general/debugging-general?lang=cpp#time-limit-exceeded:

Time Limit Exceeded

  • What is the complexity of your algorithm?

It took me a while to realize it, but your code is not actually O(N\log N) when many ladders have the same start / endpoints.

#9

Why? Is it the part where I’m iterating through all the possible ladders an endpoint can go to?

#10

You will get AC if you remove duplicates from floor_starts and floor_ends.

#11

Ah, I see now. Thanks for the help!