Sprinklers
-
-
shashank21j 10 years ago there has to be a compiler optimization due to -O2 flag.
-
JdPL1990 10 years ago I always hoped the optimization would just do minor changes. Isn't it the job of us programmers to lower the timecomplexity of a problem? How is this even possible if the optimization makes a O(T*M*N)-solution pass?
-
-
porker2008 10 years ago It is due to optimization.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { uint64_t n=1; uint64_t m=1; for(uint64_t i=0; i<50000; i++) { for(uint64_t j=0; j<10000; j++) { for(uint64_t k=0; k<10000; k++) { n+=k; } n+=j; } n+=i; } std::cout << n; }
can be optimized to be
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { uint64_t n=1; uint64_t m=1; for(uint64_t k=0; k<10000; k++) { n += k * (50000 * 10000); } for(uint64_t j=0; j<10000; j++) { n += j * 50000; } for(uint64_t i=0; i<50000; i++) { n += i; } std::cout << n; }
EDIT: If you want to check, you can replace
n += k
in your code withn += rand()
you will see the optimization will fail and the program will timeout-
JdPL1990 10 years ago The n+=rand() worked, thanks. Is there any possibility to find out the time-complexity of a solution? It is quite frustrating not to know what the computer is doing.
-
-
Tawcharowsky 10 years ago Must be some kind of witchcraft. In all seriousness... I have no idea.
-
@Tawcharowsky: Could you please explain, why the following code doesn't get TLE:
Edit: If you want to test: it is written in C++;
Add Reply Preview cancel