link to the question: https://codeforces.net/contest/1339/problem/C

link to submission: https://codeforces.net/contest/1339/submission/76490327

After I read the question, I realised the following:

step-1. if a number of the array is smaller than the previous one, then we will add-in powers of 2 to make it greater than equal to the previous number; and we need to choose those seconds or those iterations only so that we get the minimum possible number that will be greater than equal to the previous number.

Step-2. having realised the above, I calculated the difference whenever a number was smaller than the previous one and simply found till when shall I add in powers of 2 so that the number gets greater than equal to the difference calculated(i.e 1+2+4+8+16......); do note here I have iterated in consecutive seconds, i.e if I got 5 seconds then it means it requires the previous 4 additions of powers of 2.

step-3.now the number which I got from the previous operation will not be the minimum number required at that position. so, to minimise I did the following:

(i) first, if my difference was 12 then the number which I will get from step 2 will be 15(1+2+4+8) so I started removing numbers from beginning i.e(15-1-2-4-...) until my number was greater than 12(i.e the difference required). so I will get the minimum number to be added at that position which will be 12.

(ii) now if my difference was 11 then the number which I will get from step 2 will be 15(1+2+4+8) now along with the above the process I will also calculate the minimum by directly removing only one element from the addition of powers of two, (i.e remove only 1 or 2 or 4 only one of them) so I will remove 4 from 15 using the following the process, therefore, the number I will get is 11 which needs to be added at that position.

(iii) now note that using sub-process (ii) on the example given in sub_process(i) will get number 13(as we will remove only 2), and if we use sub_process(i) on the example given in sub_process(ii) will get number 12(as we will do 15-1-2). now in each of the example, we will take the minimum of the numbers obtained from each process.

now I don't why after thinking the algorithm so thoroughly I am getting a failed test case. So, please let me know which scenario is missing in my solution.

P.S: I have tried my best to explain what have I done in my code, that's why the blog is very lengthy and I have written my code in Python so that it will be intuitive for the reader to co-relate the code and the blog; so, please do give it a try and let me know the issue.

link to the question: http://codeforces.net/contest/455/problem/A

The code has been written in python and dynamically programmed. But, i am getting TLE on test case 11. Please ,help in optimising the code if possible and if not; please tell why the code is getting TLE; is it because of python being a slower language or there is some issue in code?? PLEASE, HELP OUT!!

SOURCE CODE:(I DO NOT KNOW HOW TO SHARE SUBMISSION LINK!!):

def boredom(freq_li,i,n): dp=[-1 for i in range(n+1)] dp[n-1]=(n-1)*freq_li[n-1],(n-1)*freq_li[n-1] dp[n]=0,0

for k in range(n-2,-1,-1):
    if freq_li[k]==0:
        dp[k]=dp[k+1]        
    else:
        inclusive_k=k*freq_li[k]
        for j in range(k+2,n):
            curr_ans=dp[j]
            ans=k*freq_li[k]+curr_ans[0]
            inclusive_k=max(inclusive_k,ans)    

        ans=dp[k+1]
        exclusive_k=ans[1]

        overall=max(inclusive_k,exclusive_k)
    dp[k]=inclusive_k,overall    

return dp[0]

n=int(input()) li=[int(x) for x in input().split()] maxm=max(li) freq_li=[0 for i in range(maxm+1)] for ele in li: freq_li[ele]+=1

max_points=boredom(freq_li,0,maxm+1)[1] print(max_points)