Why is my code giving a TLE?

Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

lazy_wallflower's blog

By lazy_wallflower, history, 2 years 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

lazy_wallflower
2 years ago
19

Comments (17)

Show archived | Write comment?

rangerscowboys

2 years ago, hide # |

+13

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

lazy_wallflower

2 years ago, hide # ^ |

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

bricked_

2 years ago, hide # ^ |

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

rangerscowboys

2 years ago, hide # ^ |

bro just copied me skull

→ Reply

bricked_

2 years ago, hide # ^ |

whoops, didn't see mb

→ Reply

bricked_

2 years ago, hide # ^ |

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

rangerscowboys

2 years ago, hide # ^ |

Well I didn't focus on constant factor so like

→ Reply

bricked_

2 years ago, hide # ^ |

:) you focused on speed.

→ Reply

cbertake

2 years ago, hide # |

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

→ Reply

lazy_wallflower

2 years ago, hide # ^ |

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

→ Reply

rangerscowboys

2 years ago, hide # ^ |

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

yoshi_likes_e5

2 years ago, hide # ^ |

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

bricked_

2 years ago, hide # ^ |

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

yoshi_likes_e5

2 years ago, hide # ^ |

Use gp_hash_table, it's 2-3x faster (see https://judge.yosupo.jp/submission/227599, https://judge.yosupo.jp/submission/229909)

→ Reply

yoshi_likes_e5

2 years ago, hide # |

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

lazy_wallflower

2 years ago, hide # ^ |

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

→ Reply

rangerscowboys

2 years ago, hide # ^ |

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