dhiraj-01's blog

Why TLE :( + Tips on how to avoid TLE :)
By dhiraj-01, 3 years ago, In English

Problem
https://mirror.codeforces.com/contest/1132/problem/C

TLE solution
https://mirror.codeforces.com/contest/1132/submission/124402631

Approach 

n, q <= 5000
We can skip 2 painters, so just iterate through all pairs (i, j) ignore i and jth painter, and maximize the answer.  
Time complexity: O(2 * n + q * q * 3)  
Space complexity: O(3 * n)

Thank you.

Update
AC https://mirror.codeforces.com/contest/1132/submission/124404923
creating a vector in each iteration cause TLE :(

How to avoid TLE
- check time complexity will fit in the problem
- C++ -- use FAST IO, use '\n' instead of endl, use int (if needed)
- make sure your debug statement will not print anything on judge
- recursive dp sometime gives TLE, try iterative
- creating vector, vector.push_back() in nested loop is scary (check this comment for better understanding)

if (nothing works)
  • Vote: I like it
  • +31
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Time complexity is more like O(n*n*q):

For every i (n) take every j > i (/2) and connect q-2 segments () and check if its max.

You see that you have 3 levels of "for" in your code, right?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it
    click here
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      Ah, sorry, now I see what you did in third for-loop. Then question is — do you really need so many slow long longs?

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

        I have changed long long int to int still TLE (check the code again)
        using ll = int;

        → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

Going to help because it's a reasonably written blog.

You're correct about the solution and time complexity, that's not the issue. It's the implementation, and more specifically working heavily with vectors within the inner loop. Not all operations are created equal, so $$$O(q^2)$$$ of straightforward arithmetic will pass easily, but $$$O(q^2)$$$ of allocating new vectors is much, much heavier in practice.

I've done minimal changes to the code — in particular, I've made $$$b$$$ a fixed size and hence avoided allocating any memory within the loop. All the logic is the same but the speed increase is nearly 10x (at least locally for me). Here is your accepted code: AC. You can compare it to yours to see the exact changes.

Edit: I see you've figured it out yourself. Good job.

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

    yes Enchom got it. thank you very much.

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

    But why

    isn't this lines are the same allocations?

    This got AC too, with almost the same time as your's. Thought b is still a vector<vector< int> >. I just thrown out .push_back()'s and written above code of your's. What is the difference?

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

      Whether it's statically allocated array, or a vector with fixed size, it doesn't matter. Both yours and mine are essentially the same

      The important thing is that the lines you mentioned are not allocations, but simple assignments. There is no memory allocation/deallocation happening in the background since the vector does not change its size.

      → Reply