Problem: CSES - Datatähti 2015 loppu - Ruudukko
I could pass the first two sub tasks but my code gives a RE on the last sub task. I think it has something to do with the size of the strings that I am storing in the 2D vector. Can anyone please help me with this?
CODE:
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
int main() {
FASTIO
// freopen("test_input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int n;
cin >> n;
char board[n][n];
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> board[i][j];
}
}
vector<vector<string>> dp(n, vector<string> (n));
dp[0][0] = board[0][0];
for(int i=1; i<n; i++) {
dp[0][i] = dp[0][i-1] + board[0][i];
dp[i][0] = dp[i-1][0] + board[i][0];
}
for(int i=1; i<n; i++) {
for(int j=1; j<n; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + board[i][j];
}
}
cout << dp[n-1][n-1] << "\n";
return 0;
}
Aren’t you supposed to print a string?
@dedsec_29 I am printing a string. [AC in first two sub tasks]
Oh my bad. By the way do they show test cases for which you’re failing? (Like in CSES problem set)
Did you try running your code on that test case and then debug it to see where you might be getting RE? Can you provide one such small test case? I could then maybe assist/help you with debugging that
I had downloaded one of the test files (the last one) for which I had got a RE. Then I tested my code by writing the output to a file and the thing is that it had given the correct answer when I opened the output file.
Can anyone please help me with this?
Yea, I think it has to be because your program takes more memory than the limit for the last subtask. Suppose for nxn grid the largest path is 2N-1 (Along the left then the bottom wall).
Then size of string in dp[n-1][n-1] will be 1+2+…+n+(n+1)+(n+2)+…+(n+n) = Σ(2N)(2N+1)/2 so O(n^2) space.
This was for string in cell (n-1,n-1). Now consider the same for cells (n-1,n-2), (n-2,n-2), … (i,j). Adding the summation for them in all total will definitely exceed 128MB exceeding the memory limit
1 Like
That is due to memory issues. Notice that you don’t need to create dp[n][n]. At any stage you just need the value in the cell above it that means the above row and left cell. So, you just need 2 arrays- one that will store values in the prev row and second for filling the current row. Once you go to next iteration change to first array to second and now again start filling the second array and continue.
Python Code
'''Author- Akshit Monga'''
n=int(input())
dp=['' for x in range(n)]
grid=[['' for x in range(n)] for y in range(n)]
for i in range(n):
x=input()
for j in range(n):
grid[i][j]=x[j]
dp[0]=grid[0][0]
for i in range(1,n):
dp[i]=dp[i-1]+grid[0][i]
for i in range(1,n):
temp = ['' for x in range(n)]
for j in range(i):
temp[0] += grid[j][0]
temp[0]+=grid[i][0]
for j in range(1,n):
temp[j]=min(temp[j-1],dp[j])+grid[i][j]
dp=temp
print(dp[n-1])
2 Likes
It is true it is due to memory issues only. But space required for dp[n-1][n-1] is O(n) only. For the whole program, the total space would be O(n^3) as there are n^2 cells. Correct me if I am wrong.
vector<vector<string>> dp(n, vector<string> (n));
A 2D vector with a string of max size n at each cell will amount to O(n^3) sapce.
It does seem it’d be O(n). If it were O(n^3), then ( (500)^3 / (2^10) ) / (2^10) which roughly is 119 MB have passed (less than 128 MB), unless each string requires more than maxN bytes of memory. I maybe wrong. It depends on the length of each string in the vector string.
Isn’t my summation correct? I’m just adding length of each string in a bad case where you’d have to traverse first down the grid, then rightwards to the end of grid for an optimal solution.
Say dp[n-1][n-1] stores the string that we traverse from top row and rightmost column that the length of the value of the string that it will store is 2 \cdot n .
It is wrong. dp[n-1][n-1] will not be the summation of the series rather only the last element.
1 Like
Thanks for pointing that out! Sorry to those to whom I might have confused…
1 Like