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.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | cry | 161 |
2 | maomao90 | 160 |
3 | awoo | 159 |
4 | atcoder_official | 157 |
5 | -is-this-fft- | 155 |
5 | nor | 155 |
7 | adamant | 154 |
8 | maroonrk | 152 |
8 | Um_nik | 152 |
10 | djm03178 | 146 |
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.
Name |
---|
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!
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!!
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.bro just copied me skull
whoops, didn't see mb
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
Well I didn't focus on constant factor so like
:) you focused on speed.
Do not use map. Instead use vector of vector for the mp variable.
Wow, this optimisation was amazing, reduced the time to nearly 1 second. Thanks a lot!!!
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.
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.
Your O(n) solution is surprisingly avoiding both the log n factors, wow
I provide you with this unhackable(or supposedly unhackable) unordered map template:
Use
gp_hash_table
, it's 2-3x faster (see https://judge.yosupo.jp/submission/227599, https://judge.yosupo.jp/submission/229909)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.Is it? Never knew about this. Thank You!!
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
Wow, so much information with just one simple doubt, codeforces community is just amazing. Learned a lot from this. Thank you!!