Блог пользователя bobbilyking

CSES Coin comb I TLE: why?
Автор bobbilyking, история, 4 года назад, По-английски

https://pastebin.com/zV3jsqy7

i did look at the CF editorial, and yeah my implementation (i don't think) is wrong. and someone else had the same TLE problem as me but he never said how he resolved it (if he ever did). Is this just a java thing? Editorial says that time complexity is n * target, which is 10^8 operations, so maybe I can make very very slight optimizations somewhere to get it under 1ms?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I also got TLE with recursive dp in c++ and had to do iterative. Timelimit is strict but 10^8 is indeed the intended complexity. Try swapping out the modding line with this as mod is a heavy operation.

if (whatever >= MOD) whatever -= MOD

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    omg that worked ty

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Had been scratching my head around what further to optimize....well there's always an optimization ty :)

    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    woahhh, it really worked!! But I found another code online and it makes the use of MOD but it didn't get any TLE, how is that possible. LINK: https://usaco.guide/problems/cses-1635-coin-combinations-i-unordered/solution

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I don't remember if that optimization was required in C++ codes for this problem or not. If it was, I have no idea tbh.

      → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      Btw one thing to note about this problem. You don't even need $$$n \cdot x$$$ mod calls.

      Here is the solution with n * x mod calls
      Here is the solution with x mod calls
      → Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It works, thanks.

    → Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Not sure in java but in C++ a%b works slightly faster if b is a constant. So in the following code int mod = 1e9 + 7 will give TLE but int const mod = 1e9 + 7 will not.

dp[0] = 1;
    for (int i = 1; i <= m; i++)
    {   for (int j = 1; j<= n; j++)
        {   int x = i - a[j];
            if (x >= 0)
                dp[i] = (dp[i] + dp[x])%mod;
        }
    }
    cout << dp[m];
→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This saved me in other problem, I was getting TLE with almost the same code I done 2 years before. just adding a const and it got accepted.

    In Problem "Graph paths I" runs 4 times faster, about 57 million of '%' operations in the worst test case.

    → Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This really works !!!

    My soln got accepted after 6 attempts :)

    → Ответить
  • »
    »
    7 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For java user, declare mod globally as:

    static final int mod = 1000000007;

    and it will work fine

    → Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thankyou. I did a lot of submissions and finally decided to google search it. This method worked.

    → Ответить
»
6 месяцев назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

[deleted comment]

→ Ответить