jha_saurav's blog

By jha_saurav, history, 2 months ago, In English,

link to the question: http://codeforces.com/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)

 
 
 
 
  • Vote: I like it
  • -30
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jha_saurav (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +2 Vote: I do not like it

The code has two nested loops, which makes it O(n^2). In the editorial, you can find a faster O(n) solution.

In general, if you can find something in the editorial, do not waste people's time asking for it on the blog.

How to add the submission link? Go to your profile. Choose the tab "Submissions". Right click on your submission number and copy link. So this is the link: https://codeforces.com/contest/455/submission/75710100

You may have noticed a few downvotes under the post. Please take care of how you write. OVERUSING BIG LETTERS make you seem SHOUTING. Use commas (,) and dots (.) in a right way so that your post looks tidy and people want to read it.

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

    Well, mate; I will keep that in mind from now onwards; it was my first blog so didn't have much experience.

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

      That is fine. Good luck in problem solving and future contests :)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my python submission for this problem :-
75721750

Lemme know if this helps