hg333's blog

making functions inline can get the TLE code accepted
By hg333, history, 5 years ago, In English

This is my solution with inline function.

This is without inline keyword.(TLE)

making the function inline shortened execution time drastically.

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

Comments Comments (13)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem:https://codeforces.net/contest/1287/problem/B

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hg333, problem in memory allocations on heap. Easy fix with runtime 1075ms.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    dmkz, that works. But the time complexity O(n*n*k) should not be affected by such things, still they can cause a TLE.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      hg333, you have $$$n^2\cdot \log(k)$$$ queries to heap manager. Of course, this is TLE, heap manager works very slow and total runtime of these queries greater than 2 seconds. Try to read how heap manager works.

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

        I understand that changing function argument from :

        f ( string s ) to f ( string &s ) makes difference.

        Is there something beneficial to even add "const" before it and writing f ( const string &s ) with respect to execution time ?

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

          It guarantees that you are not allowed to change arguments in function body, but it is not significant improvement for runtime, only 0.3s.

          Main part is static string a; a.clear();: decreases runtime by 1.7s.

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

    Are you sure the OP's original code allocated objects on the heap? His string variable is declared with automatic storage duration (i.e. local variable with no new keyword). I think it is allocated on the stack.

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

      std::string class has a pointer to allocated on the heap memory, if string isn't small

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

        Where’s the source of this? I would like to read more.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          I think this is just common knowledge, probably mentioned in good C++ books. C++ objects have compile-time constant sizes, so std::string must store longer strings separately on the heap.

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          This is example. When we tried to add char 'p', operator new was called for the first time. And yes, looks like for original problem not $$$n^2 \cdot \log(k)$$$ calls, but only $$$n^2$$$ queries to heap manager.

          It can be found in source code of C++ STL, I think.

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

            I read through the STL docs. I think the same can be said for any STL container such as vector, set, list, etc. They all have pointers to their underlying elements (whose space is dynamically allocated by an allocator).

            So I guess the lesson here is, for a function that has many local variables which are STL containers and is called many times, always put a static storage specifier in front of those variables?

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

              For competitive programming there is a two another solutions: 1) create own memory buffer and rewrite operator new/delete: solution, 1169 ms; 2) use C++17 monotonic buffer resourse (memory pool), when it will be supported by codeforces. Because your program will end by 2-3 seconds and you can ignore memory releases.

              → Reply