• JdPL1990 10 years ago + 3 comments

    @Tawcharowsky: Could you please explain, why the following code doesn't get TLE:

    #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;
    }
    

    Edit: If you want to test: it is written in C++;

    Add Reply Preview cancel

    Sorry, you do not have a permission to answer to this question.

    • shashank21j 10 years ago + 1 comment

      there has to be a compiler optimization due to -O2 flag.

      Add Reply Preview cancel

      Sorry, you do not have a permission to answer to this question.

      • JdPL1990 10 years ago + 0 comments

        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?

        Add Reply Preview cancel

        Sorry, you do not have a permission to answer to this question.

      • porker2008 10 years ago + 1 comment

        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 with n += rand() you will see the optimization will fail and the program will timeout

        Add Reply Preview cancel

        Sorry, you do not have a permission to answer to this question.

        • JdPL1990 10 years ago + 0 comments

          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.

          Add Reply Preview cancel

          Sorry, you do not have a permission to answer to this question.

        • Tawcharowsky 10 years ago + 0 comments

          Must be some kind of witchcraft. In all seriousness... I have no idea.

          Add Reply Preview cancel

          Sorry, you do not have a permission to answer to this question.

        1. Challenge Walkthrough
          Let's walk through this sample challenge and explore the features of the code editor.1 of 6
        2. Review the problem statement
          Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
        3. Choose a language
          Select the language you wish to use to solve this challenge.3 of 6
        4. Enter your code
          Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
        5. Test your code
          You can compile your code and test it for errors and accuracy before submitting.5 of 6
        6. Submit to see results
          When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
        1. Check your score