The problem says the following:
#CodeForces challenge, memory exceeded
atomic moss
Imagine a grid of classrooms where each room is either hot (+1) or cold (–1). You need to travel from the top‑left to the bottom‑right using only right and down moves. Since you must take a shortest path, you will visit exactly n + m – 1 classrooms. The challenge is to determine whether there exists a shortest path such that the sum of the room values is 0—that is, the path contains an equal number of hot and cold classrooms.
For such a balanced path to exist, n + m – 1 must be even because you need to have the same count of +1’s and –1’s.
Example
Consider a grid with 3 rows and 4 columns:
1 -1 -1 -1
-1 1 1 -1
1 1 1 -1
Shortest Path Length:
With 3 rows and 4 columns, any shortest path will go through 3 + 4 – 1 = 6 classrooms.
The Goal:
Find a path among these 6 classrooms where there are three +1’s and three –1’s, giving a total sum of 0.
In this example, one such path exists, meaning it is possible to balance the number of hot and cold classrooms along a shortest route.
My solution:
string pd(vector<vector<int>> classrooms, int rows, int cols) {
// The idea we are going to implement is as follows.
// We simply want to know if there exists a shortest path such that
// when reaching the final cell, the total temperature sum is 0.
// To do this, we move only to the right or down (ensuring a shortest path),
// and in each cell, we store the possible accumulated temperature sums.
// Since we can only move down or right, for a cell (row, col),
// the possible temperature sums can be calculated using the possible sums
// from the cell above (row - 1, col) and the cell to the left (row, col - 1).
// We do this until all cells are covered, and finally, when we reach the
// final cell (row, col), we check if 0 is present in the set of sums.
// If it is, then there exists a shortest path with a final temperature sum of 0;
// otherwise, it doesn't exist.
// The path length MUST be (rows + cols - 1)
int expected_length = rows + cols - 1;
// Notice that if this number is odd, we cannot obtain a solution,
// since the temperature accumulator will never sum to 0.
if (expected_length % 2 != 0) {
return "NO";
}
// dp[row][col] will contain the set of possible accumulated temperature sums at that cell.
vector<vector<unordered_set<int>>> dp(rows, vector<unordered_set<int>>(cols));
dp[0][0].insert(classrooms[0][0]);
// First, process the first row.
for (int col = 1; col < cols; col++) {
for (int sumTemps : dp[0][col - 1]) {
dp[0][col].insert(sumTemps + classrooms[0][col]);
}
}
// Next, process the first column.
for (int row = 1; row < rows; row++) {
for (int sumTemps : dp[row - 1][0]) {
dp[row][0].insert(sumTemps + classrooms[row][0]);
}
}
// Define the global range for sums: the minimum possible sum is -L and the maximum is L,
// where L = rows + cols - 1.
int upp_range = rows + cols - 1;
int low_range = -upp_range;
// Now that both row and column indices are greater than 0 (because we processed
// the entire first row and first column), complete the dp table.
for (int row = 1; row < rows; row++) {
for (int col = 1; col < cols; col++) {
// Calculate the number of remaining classrooms (steps) from the current cell to the target.
int remainingRooms = (rows - 1 - row) + (cols - 1 - col);
// Add the temperature from the cell above (row-1, col)
for (int sumTemps : dp[row - 1][col]) {
int tempSum = sumTemps + classrooms[row][col];
if (tempSum >= low_range && tempSum <= upp_range && abs(tempSum) <= remainingRooms) {
dp[row][col].insert(tempSum);
}
}
// Add the temperature from the cell to the left (row, col-1)
for (int sumTemps : dp[row][col - 1]) {
int tempSum = sumTemps + classrooms[row][col];
if (tempSum >= low_range && tempSum <= upp_range && abs(tempSum) <= remainingRooms) {
dp[row][col].insert(tempSum);
}
}
}
}
// Finally, in the last cell (rows-1, cols-1), if 0 is present in its set of sums,
// then there exists a valid path; otherwise, no such path exists.
string result = "NO";
for (int temperature : dp[rows - 1][cols - 1]) {
if (temperature == 0) {
result = "YES";
}
}
return result;
}
stray plinth
you could use one contiguous vector instead of a vector of vector
it would probably be better if you didn't take classrooms by value
atomic moss
you could use one contiguous vector instead of a vector of vector
I dont follow
I do follow 
😄 I'll try it