dhiraj-01's blog

By dhiraj-01, 2 months ago, In English

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

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

please help if you can find why I am getting TLE :)
thank you.

update
AC https://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

»
2 months 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?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it
    click here
    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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;

»
2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes Enchom got it. thank you very much.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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.