in F we can makes the dp states as dp[time%n][col] where time is the current time and time%n denotes the amount of shift in the columns and col is the current column, as row=(time-col)%n which can be written as row=(time%n-col%n+n)%n therefore given the value of time%n and col there will always exist a unique value of row so we dont need row as a state.(here we are using the observation that moving in upward direction is useless so we can say row=(time-col)%n). here's my code for reference, int recsol(vector &grid, int time, int col, int n, int m, vector &memo) { int row = (time - col) % n; int moves = time % n; if (col == m - 1) return time + min(n - row - 1, row + 1); if (grid[(row + time) % n][col] == 1 || memo[moves][col] == -2) return 1e12; if (memo[moves][col] != -1) return memo[moves][col]; memo[moves][col] = -2; int res = recsol(grid, time + 1, col + 1, n, m, memo); if (grid[(row + time + 1) % n][col] != 1) res = min(recsol(grid, time + 1, col, n, m, memo), res); return memo[moves][col] = res; } int32_t main() { faster_io; int t; cin >> t; while (t--) { int n, m; cin >> n >> m; vector grid(n, vector(m)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> grid[i][j]; vector memo(n, vector(m, -1)); int ans = recsol(grid, 0, 0, n, m, memo); if (ans > INT_MAX) cout
hi aryan, so abt F, if we can move only right and down, total steps to reach a cell is fixed, we only need to find reachable cells, it reduces to just dfs, right?
The issue is if you go past the bottommost cell, you will reach the topmost cell in a column. Consider this grid - @ # @ @ @ @ # # # @ @ # # # @ @ @ @ # @ @ denotes the path you should take. # denotes the blocked cells. So a BFS (or other algorithm for shortest path) will be required.
in F we can makes the dp states as dp[time%n][col] where time is the current time and time%n denotes the amount of shift in the columns and col is the current column, as row=(time-col)%n which can be written as row=(time%n-col%n+n)%n therefore given the value of time%n and col there will always exist a unique value of row so we dont need row as a state.(here we are using the observation that moving in upward direction is useless so we can say row=(time-col)%n).
here's my code for reference,
int recsol(vector &grid, int time, int col, int n, int m, vector &memo)
{
int row = (time - col) % n;
int moves = time % n;
if (col == m - 1)
return time + min(n - row - 1, row + 1);
if (grid[(row + time) % n][col] == 1 || memo[moves][col] == -2)
return 1e12;
if (memo[moves][col] != -1)
return memo[moves][col];
memo[moves][col] = -2;
int res = recsol(grid, time + 1, col + 1, n, m, memo);
if (grid[(row + time + 1) % n][col] != 1)
res = min(recsol(grid, time + 1, col, n, m, memo), res);
return memo[moves][col] = res;
}
int32_t main()
{
faster_io;
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector grid(n, vector(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> grid[i][j];
vector memo(n, vector(m, -1));
int ans = recsol(grid, 0, 0, n, m, memo);
if (ans > INT_MAX)
cout
Bruhh , the way you thought of dp states in really awesome. I wasn't able to minimize them during contests. Good solution
Good one.
hey can u explain why dp[moves][col]==-2 can u explain more on dp
@@FastTech1000 we are simply marking the state as visited to preventing infinite loop in the same row
@@vaibhavpratapsingh9956 oh I like do similar things as i am also solving with dp but my coded's isn't giving correct and bw thanks i understand now
hope i will be able to reach specialist after this contest
Good Luck.
Thanku so much ❤
hi aryan, so abt F, if we can move only right and down, total steps to reach a cell is fixed, we only need to find reachable cells, it reduces to just dfs, right?
The issue is if you go past the bottommost cell, you will reach the topmost cell in a column.
Consider this grid -
@ # @ @ @
@ # # # @
@ # # # @
@ @ @ # @
@ denotes the path you should take.
# denotes the blocked cells.
So a BFS (or other algorithm for shortest path) will be required.
how to be as good as you in cf ??
Join discord yt403.com/discord and check 🚗roadmap-to-red-in-2-mins channel for some starting tips.