TLE IN C++, AC in Python3.6, Jan Long Challenge ISBIAS

help
,
1

I was solving ISBIAS from January Long Challenge, I came up with a dynamic programming approach where I simply calculated the count of increasing and decreasing subsequences for each index and stored the (count of increasing - count of decreasing) in an array for each index.
I first calculated all values of this array for given length N .
Did it in O(n) timecomplexity.
Then for each query, i had answer ready which could be fetched in O(1) complexity.
So total complexity was O(n+q) .

I implemented this in c++ 14
Here’s my code CodeChef: Practical coding for everyone

It was showing me TLE , then I wrote the exact same logic in Python3.6 , and got it accepted with just 0.65s time.
My Python3.6 Code-
https://www.codechef.com/viewsolution/28767171
So what is stopping my c++ code from being accepted? Why is it showing TLE for exact same logic?
Need help !

2 
bool solve(int n,int q,vi a,int l, int r){

You’re passing a copy of a (takes O(N)) to the solve function for all O(Q) queries, resulting in an O(N \times Q) algorithm. Pass it by reference-to-const instead:

bool solve(int n,int q, const vi& a,int l, int r){
4 Likes
3

Oh wow okay, Thanks a lot. :smiley:
I understand now, I learnt alot in this Jan Long and am very grateful. :slight_smile:

1 Like
4

i would recommend use global variables and use resize and memset to reset the size according to need to avoid mistakes in future

1 Like