#Codeforces

[@vaibhavpratapsingh9956]

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

[@manmeetsingh3890]

Bruhh , the way you thought of dp states in really awesome. I wasn't able to minimize them during contests. Good solution

[@aryanc403]

Good one.

[@FastTech1000]

hey can u explain why dp[moves][col]==-2 can u explain more on dp

[@vaibhavpratapsingh9956]

@@FastTech1000 we are simply marking the state as visited to preventing infinite loop in the same row

[@FastTech1000]

@@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

[@kaustubhthakur5178]

hope i will be able to reach specialist after this contest

[@aryanc403]

Good Luck.

[@CoderAadarsh]

Thanku so much ❤

[@neeravmadaan]

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?

[@aryanc403]

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.

[@HetDadhania]

how to be as good as you in cf ??

[@aryanc403]

Join discord yt403.com/discord and check 🚗roadmap-to-red-in-2-mins channel for some starting tips.