plz make a video on this contest because the problem are difficult and many people are not able to solve as you can see the submissions
How is this code getting AC ? Problem: EURON
As far as I know, it is O(n*n) ,
list.insert(index, value) is O(n)
from bisect import bisect_right n = int(input()) k =  ans = 0 for i in map(int,input().split()): x = bisect_right(k,i) ans += len(k)-x k.insert(x,i) print(ans)
Are the test-cases weak, or am I missing something ?
How are codes like this getting passed ?
use the following code as test generator, and it gives different answer than given by official solution
MoreOver, Time limit seem to be too strict to allow the solution hinted by you to pass in languages like python submitted code
test = 1 k = 20000 q = 1 A = [i for i in range(1, k+1)] B = [1 for i in range(1, k+1)] print(test) print(k, q) print(*A) print(*B) print(600)
Here is my approcah for the LOWSUM problem exactly as mentioned in the hints.
Still it gives a TLE…
Any suggestions to optimise it…?
The multiset solution/hint for STACKS doesn’t work. It gives TLE. My hint: try with vector itself.
Edit: My bad, the multiset solution does work. Thanks @rishup_nitdgp !
I have used pbds data structure for this problem, but it is giving WA.
Can anyone check my code for error.
ll ans = 0;
ans += (o_set.size()-1-o_set.order_of_key(a[i]));
@srij_kh I added one more hint under the problem. This will help you.
@harshraj22 Thanks for pointing out. I think the test data is weak for both the problems. Also added a hint in LOWSUM.
@stardust_123 I went through your code and I find that you are using std:: upper on multiset which cause TLE. Actually the worst-case time complexity of std:: upper or similar is O(N) in case of ordered containers. II is better to use set:: upper which gives O(log N) worst-case complexity.
@nomansid08 Please mention the submission link to your code.
@rishup_nitdgp I see. Thanks for the info ! I am gaining a lot of insight and knowledge from this DSA learning series ! I thank you and other volunteers for doing this !
As I replied to @harshraj22. Test cases are weak for the problem.
Worst case time complexity for std::distance function is O(N). For more information, visit here.
then how is @harshraj22 answer in python, having the same complexity as mine, gets accepted even in 1.22 sec of runtime ??
I would like to say a few things:
- Rishup already pointed out, test cases are weak. Given the constraints, a O(n2) solution should not pass.
- The Python3 Solution is not mine.
- Python has different time multiplier (which might have given edge over cpp solution)
- Finally, the constants, they are ignored while calculating time complexity, but still play a major role. Read here
I know, it is strange for the same complexity to be accepted in one language and rejected in another, but maybe you should focus on improving the complexity from O(n2)
Your solution complexity is roughly O(N^2 + N*Log N), that’s why you are getting TLE.
P.S: Log N factor due to std::multiset.
Did you mean O(n * (n + logn)) ?