ApaarGulati's blog

NEED help with TLE. Is my approach correct?
By ApaarGulati, history, 4 months ago, In English

HI. I am a beginner in CP. and know only python. While solving the given problem https://mirror.codeforces.com/contest/1992/problem/C i was able to write the given code 269990236. but i got a TLE on test 5. i looked at the tutorial and found that my way of thinking and the tutorial's approach were the same. But i am still not sure if the orders of the 'numbers in the middle' matters or not. can someone please look into my code and tell if what i am doing with 'the numbers in the middle' is ok?

link to tutorial: https://youtu.be/9Vv2ZukG1CM?t=2685

also, if his and my methods are the same, am i getting TLE just because of python? or is my method just longer than his is?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

sorting takes O(nlogn) so when you are sorting each time you iterate you it will be n^2 *logn and this is so large

and also this code

for x in p:

    an+=str(x)

    an+=' '

the complexity of this will be len(p)^2 because of adding strings just append them into a list and join them in the last

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

    uh well. i did not get it completely but i understood that the way i am iterating to sort, it is taking a lot of time and so is the conversion to string and then concatenation.

    i got the answer on how to reduce time by just adding in list and joining at last but

    Please suggest how i can reduce time while iterating(for sorting) also.

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

      Imagine n is 200000

      your code will approximately iterate more than 200000^2 = 40000000000 and this number is so big you will stay forever

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

    also is it correct that the "numbers in middle"(i.e. the ones that appear to be shuffled after the decreasing subsegment of integers) can they be in any order?

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

      Yes, the numbers in the middle can be in any order since they do not influence the values of f(i) and g(i) in any way since these numbers do not fall in the >=k or <=m range required in the question. You can check this out

      my submission
      → Reply