### pranav232323's blog

By pranav232323, history, 3 years ago, 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?

P.S. Tagging pllk in case this is an issue with the judging servers. Comments (6)
| Write comment?
 » 3 years ago, # | ← Rev. 2 →   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.
 » 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.
•  » » thanks, it works.
•  » » 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; dp = 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); }} }
•  » » » 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.
 » why TLE For this https://cses.fi/paste/c9b8bdf1ac11f0de582fcd/ ?