HI. I am a beginner in CP. and know only python. While solving the given problem https://codeforces.me/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?
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
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
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.
Imagine n is 200000
your code will approximately iterate more than 200000^2 = 40000000000 and this number is so big you will stay forever
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?
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
269956483
oh ok yeah. got the logic. thx