pranav232323's blog

By pranav232323, history, 5 months ago, In English

I'm getting TLE despite having an optimal time complexity: $$$O(nk)$$$ where $$$k$$$ is the target and $$$n$$$ is the number of coins. I even tried optimizing the modulo operation according to https://codeforces.com/blog/entry/77506, but I still have one test case that keeps TLE-ing. Further, downloading and running that test case locally indicates that my code is executing in well under the time limit of $$$1$$$ second.

Is there anything I can do at this point?

Submission: https://cses.fi/paste/6a1dc1e39bbd5552186afe/

Problem: https://cses.fi/problemset/task/1635

P.S. Tagging pllk in case this is an issue with the judging servers.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

CSES submissions are not globally visible. You need to share it as a paste (you can create one by scrolling to the bottom of your code in your submission, or alternatively use an online paste website. Here's my solution as a paste for example: https://cses.fi/paste/3ff7373cf56f6af416e923/. please share yours the same way). If you're using an O(nk) memory solution, you are not being cache friendly most likely, which is why it might TLE.

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

Instead of taking MOD(dp[x]%MOD) directly try using if(dp[x]>MOD) dp[x]-= MOD, this should definitely help, moreover if you are storing your dp values as long then you should store it as int.

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

    I've already implemented the MOD optimization you mentioned.

    Changing long to int sounds like a good idea.

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

    Update: changing long to int did the trick

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please can you explain how changing long into int decrease time?