lazy_wallflower's blog

Why is my code giving a TLE?
By lazy_wallflower, history, 3 months ago, In English

In the problem D of recent Edu round, I used binary search to solve the problem, but i'm not able to figure out where the TLE is, please help me find out.

276695555 2004D - Colored Portals

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

For this problem, O(nlogn) with bad constant factor could TLE. However, if you add this line of code right after you declare main(): ios_base::sync_with_stdio(false); cin.tie(NULL); Using the above code will make the input factor and can make the code significantly faster.

Take a look at my submission of your code with the added line: 277182525 It gets 1842ms with AC.

Feel free to also look at my O(n) solution which passes relatively comfortably (since 1842 ms is still a lot): 276595217

Note that the pragma that I include in the top could also make your code faster. These things might be a good idea for you to include in your template.

Hope this helps!

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much for this! Will make sure about this in the future, also the O(n) solution is great too! Thanks a lot!!

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You may also want to add this line at the very top of your code #pragma GCC optimize("O3"). It helped an O(√n^3) code pass when it shouldn't have.

      → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also rangerscowboys I find this to be very interesting as my $$$O(n$$$ $$$log$$$ $$$n)$$$ code is faster than your $$$O(n)$$$ code. I wonder why?

    My submission: 276624358 AC in 280ms

    → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Do not use map. Instead use vector of vector for the mp variable.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, this optimisation was amazing, reduced the time to nearly 1 second. Thanks a lot!!!

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I just realized that. This is because map lookup times is O(logn), which means you are doing an additional O(logn) to the O(nlogn) which makes constant factor much worse.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The number of keys in the map in this case is constant (6). But map has a high constant factor, so it'll still affects accessing times by a lot.

        → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your O(n) solution is surprisingly avoiding both the log n factors, wow

        → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I provide you with this unhackable(or supposedly unhackable) unordered map template:

      mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
      static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
        x = (x^(x>>30))*0xbf58476d1ce4e5b9;
        x = (x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
      }

      size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = rng();
        return splitmix64(x+FIXED_RANDOM);
      }
};

template<typename T, typename V> using safe_map = unordered_map<T, V, custom_hash>;
      → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Replacing endl with \n also improves performance. I had to do it some times to not get TLE. I have seen reductions as big as 8x with this (from 1130ms to 134ms), but it'll vary on problems and tests.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it? Never knew about this. Thank You!!

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is because endl flushes the output as well as prints a new line. You need to make sure to flush the output (by doing endl or "\n"+cout.flush();) for interactive problems, but "\n" is better for anything that isn't interactive.

      I would recommend reading this for more detail: https://usaco.guide/general/fast-io

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, so much information with just one simple doubt, codeforces community is just amazing. Learned a lot from this. Thank you!!

        → Reply