krm24's blog

By krm24, 11 days 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

»
11 days ago, # |
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.

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it
  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    thanks well explained

  • »
    »
    10 days ago, # ^ |
      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?