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

Odd Behaviour in CSES task
Автор krm24, 4 года назад, По-английски

I was solving CSES problem (Coin Combinations II) and oddly it gave TLE when I made the dp array as dp[x+1][n] and gave correct ans when it was changed to dp[n][x+1].

Problem TLE Code Correct Code

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

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

Cache missing in 2nd case is much less than in 1st case.

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

Similar discussion: https://mirror.codeforces.com/blog/entry/70018?#comment-663101

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

    thanks well explained

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

    As a rule of thumb, the entity which will have greater change(for eg: dp[i][j]=d[i-1][j-some value] , here the entity corresponding to j is having a greater change) should be kept in inner dimensions. Is this right or should the constraints of the entities be also considered?

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

Here: https://mirror.codeforces.com/blog/entry/70018?#comment-548451

→ Ответить