pranav232323's blog

By pranav232323, history, 3 years 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://mirror.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

| Write comment?
»
3 years 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.

»
3 years 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.

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

    thanks, it works.

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

    Thanks it works.

    public class CoinCombinationsI { public static long mod = 1000000007L;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int t = 1;
        outer:
        while (t-- > 0) {
            int n = sc.nextInt();
            int x = sc.nextInt();
            int[] arr = readarr(sc, n);
            long[] dp = new long[1000007];
            dp[0] = 1;
            for (int i = 1; i <= x; i++) {
                for (int coin : arr) {
                  if(i - coin < 0) continue;
                  dp[i] += dp[ (i - coin)];
                  if(dp[i]>mod) dp[i]-= mod;
                }
            }
            out.println(dp[x] % mod);
        }

    } }

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

      Another possiblity is to to keep dp as a long[], and then have a single %-operation after the coin for loop

      for (int coin : arr) {
         if(i - coin < 0) continue;
         dp[i] += dp[ (i - coin)];
      }
      dp[i] %= mod;
      

      This should cut down the number of %-operations by a factor of 100 compared to your original code.

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