krm24's blog

Odd Behaviour in CSES task
By krm24, 6 years ago, In English

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

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
6 years ago, hide # |
← Rev. 2  
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

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

    thanks well explained

    → Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
6 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply