Hi, I was solving problem Book Shop on CSES and found something interesting.
I tried this problem using two different ways:
First: Passed.
dp[i][j] : means maximum pages we can have if we are at shop number i and we have spent j amount of money;
The code is here :
void solve(){
ll n, m;
cin >> n >> m ;
vector<ll> prices(n+1), pages(n+1);
for(int i = 0 ; i < n ; i ++ ){
cin >> prices[i];
}
for(int i = 0 ; i < n; i ++ ){
cin >> pages[i];
}
vector<vector<int>> dp(n+1, vector<int> (m+1, 0));
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 0 ; j <= m ; j ++){
dp[i][j] = dp[i-1][j];
if(j - prices[i-1] >= 0){
dp[i][j] = max(dp[i][j], dp[i-1][j-prices[i-1]] + pages[i-1]);
}
}
}
cout << dp[n][m] << '\n';
}
Here the time compexity is n*m. The outer loop is running n times while the inner one is running m times, and it passed.
Second : TLE
dp[i][j] : maximum pages if we have used i amount of money and currently we are at j'th shop. The code :
void solve(){
ll n, m;
cin >> n >> m ;
vector<int> prices(n+1), pages(n+1);
for(int i = 0 ; i < n ; i ++ ){
cin >> prices[i];
}
for(int i = 0 ; i < n; i ++ ){
cin >> pages[i];
}
vector<vector<int>> dp(m+1, vector<int> (n+1, 0));
for(int i = 1 ; i <= m ; i ++ ){
for(int j = 1 ; j <= n ; j ++){
dp[i][j] = dp[i][j-1];
if(i - prices[j-1] >= 0){
dp[i][j] = max(dp[i][j], dp[i-prices[j-1]][j-1] + pages[j-1]);
}
}
}
cout << dp[m][n] << '\n';
}
Here also the time complexity is m*n. The outer loop is running m times while the inner one is running n times.
Since both have the same time complexity so why one of them is giving TLE ? Is there something that I am missing ?
I didn't look too deep into the code, so this might not be the case in the code you put above.
The computer cannot store a matrix as 2d, because RAM/Cash memory is just like array, you have byte index and value. Therefore, a matrix is stored in an array as follows: First row, Second row, Third row and so on.
For example, matrix [[1, 2], [3, 4]] will be stored as 1 2 3 4. When you move from m[i][j] to m[i][j+1], you only move a single element in memory. However, when going to m[i+1][j], you move the size of dimension 2 in memory. Now, the movements of type 1 are much easier to predict, and therefore the grader can use cash memory as it's going through elements in order. But in the second example, the code jumps through memory, making access slower.