pranav232323's blog

CSES Coin Combinations I Java TLE.
By pranav232323, history, 4 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

Comments Comments (6)
| Write comment?
»
4 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.

→ Reply
»
4 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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have used int but still, it is showing TLE on 3 test cases. Can anybody help me to optimize this. https://cses.fi/paste/5ca0826685e6ac102c689b/

    → Reply
  • »
    »
    13 months 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);
    }

    } }

    → Reply
    • »
      »
      »
      13 months 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.

      → Reply