Subtask 1:
Let's first determine which rows have all contiguous subsegment sums between $-1$ and $2$. We note
Let's analyze the number of $\texttt{+ +}$ in the row. We observe that there can only be at most one occurrence of $\texttt{+ +}$ in a row. Otherwise, we can take a contiguous subsegment between two occurrences of $\texttt{+ +}$,
+ + - + ... + - + +
which has a sum of $3$.
Then, we can try all such grids and determine which ones are consistent with Farmer John's memory, which can be done in $O(\max(R, C))$ time.
Full solution:
Now, we have multiple rows and columns. Let's take a row that has an occurrence of $\texttt{+ +}$:
- + - + + - + -
Now, let's analyze the possible rows that can be under this row. We cannot have two $\texttt{-}$ in a row, so all cells under $\texttt{-}$ must be $\texttt{+}$:
- + - + + - + - + * + * * + * +
Since we can only have one occurrence of $\texttt{+ +}$ in the second row and we cannot have two $\texttt{-}$ in a row, we only have two possibilities for this row:
- + - + + - + - + - + + - + - +
and
- + - + + - + - + - + - + + - +
The one exception is when $R = 2$ and $C = 2$. In that case, we can also have
+ + + +
Let's assume the lower $\texttt{+ +}$ is to the left of the upper $\texttt{+ +}$. Now, the only possibility for the next row is
- + - + + - + - + - + + - + - + - + + - + - + -
We extend downwards until the $\texttt{+ +}$ hits the left or bottom of the grid.
- + - + + - + - + - + + - + - + - + + - + - + - + + - + - + - + + - + - + - + -
A similar analysis holds for upwards. Call this sequence of $\texttt{+ +}$ a chain.
We observe that there cannot be two chains in opposite directions. To prove this, let's try to construct two chains in opposite directions. First, we construct the chain going down and to the left, like in this example:
* * + + * * * * * * * + + * * * * * * * + + * * * * * * * * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
There are two cases for the chain going down and to the right:
* * + + * * * * * * * + + * * * * * * * + + * * * * * * * * + * * * * * * * * * * * * * * * * * * * + * * * * * * * * * + + * * * * * * * * * + + * * * * * * *
* * + + * + + * * * * + + * * * + + * * + + * * * * * + + * + * * * * * * * + + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Now, WLOG, the chains go down and to the left. We can solve the other case by reversing the columns.
Next, we observe that the values in each diagonal going left and down are the same. Consider if one diagonal has
+ -
Then, the surrounding values must be
+ + - +
However, this does not follow the additional condition that the lower $\texttt{+ +}$ is to the left of the upper $\texttt{+ +}$, as the lower left cell is $\texttt{-}$. The other case of
- +
is similar.
We can index the diagonals from $1$ to $R + C - 1$, where cell $(i, j)$ corresponds to diagonal $i + j - 1$. Notice that without any $\texttt{+ +}$ chain, the values of the diagonals alternate between $\texttt{+}$ and $\texttt{-}$, but a $\texttt{+ +}$ chain creates two diagonals with values $\texttt{+}$ and $\texttt{+}$, effectively flipping the values of the following diagonals. Denote the position of a $\texttt{+ +}$ chain as the diagonal the right $\texttt{+}$ is in: the first diagonal whose parity is flipped relative to the alternating pattern.
With this observation, we can now determine the condition for placing multiple chains in a grid. Let's have the chain with the earliest position at position $d$, and assume $C \geq R$:
* * + + * * * * * * * + + * * * * * * * + + * * * * * * * * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
We cannot have more than one $\texttt{+ +}$ in a single row or column, so the minimum position of the following chain is $d + C - 1$, constructed as follows:
* * + + * * * * * * * + + * * * * * * * + + * * * * * * * + + * * * * * * * + + * * * * * * * + + * * * * * * * + + * * * * * * * + + * * *
However, the diagonals in between must alternate between $\texttt{+}$ and $\texttt{-}$. This means that when $C \equiv 1 \pmod{2}$, the minimum position of the right chain is $d + C$. This also means that only every other diagonal after the minimum position is a valid position of the right chain.
In general, the minimum position of the following chain when the previous chain is at position $d$ is
In particular, if $d > \min(R, C)$, then there cannot be any further following chains. This also means that there can be at most two chains in a grid, because $d + \max(R, C) - 1 > \min(R, C)$ (note that $d \geq 2$).
Now, let's analyze which grids are consistent with Farmer John's memory.
For simplicity, fix the values of the first and last diagonals. This will reduce the number of cases. Then, let's analyze the diagonals that have existing values in them and take consecutive pairs of them. For a pair:
This means,
For the cases where we have two chains, we can iterate through the position of the left chain and count the number of possible positions for the right chain. Beware of the edge cases of $\min(R, C) = 1$ and $R = C = 2$. This solution takes $O(R + C + X)$ time.
Nelson's code:
#include <bits/stdc++.h>
using i64 = long long;
struct Cell {
int v, r, c;
};
void tc() {
int r, c, x;
std::cin >> r >> c >> x;
std::vector<Cell> cl(x);
for (auto& [v, ri, ci] : cl) {
char cc;
std::cin >> cc >> ri >> ci;
v = cc == '+';
--ri;
--ci;
}
if (r == 1 && c == 1) {
if (x == 1)
std::cout << 1 << '\n';
else
std::cout << 2 << '\n';
return;
}
auto get_mi_rb = [&](int d) {
int mx = std::max(r, c);
if (mx % 2 == 0)
return d + mx - 1;
return d + mx;
};
auto comp = [&](int mi, int rb) {
if (mi > rb)
return 0;
return (rb - mi) / 2 + 1;
};
i64 ans = 0;
auto solve = [&](bool z) {
std::vector vals(r + c - 1, -1);
for (auto [v, ri, ci] : cl) {
if (vals[ri + ci] == -1)
vals[ri + ci] = v;
else if (vals[ri + ci] != v)
return;
}
bool ff = vals[0] == -1, fl = vals[r + c - 2] == -1;
for (int fval : {0, 1}) {
if (!ff && vals[0] != fval)
continue;
vals[0] = fval;
for (int lval : {0, 1}) {
if (!fl && vals[r + c - 2] != lval)
continue;
vals[r + c - 2] = lval;
std::vector<int> d;
for (int i = 0; i < r + c - 1; ++i) {
if (vals[i] != -1)
d.push_back(i);
}
std::pair i1{-1, -1}, i2{-1, -1};
bool g = true;
for (int i = 0; i < (int)d.size() - 1; ++i) {
int lb = d[i], rb = d[i + 1];
if ((vals[lb] ^ vals[rb]) != (rb - lb) % 2) {
if (i1.first == -1)
i1 = {lb, rb};
else if (i2.first == -1)
i2 = {lb, rb};
else {
g = false;
break;
}
}
}
if (!g)
continue;
if (i1.first == -1) {
if (z)
++ans;
for (int i = 0; i < (int)d.size() - 1; ++i) {
int L = d[i], R = d[i + 1];
for (int lb = vals[L] == 1 ? L + 1 : L + 2; get_mi_rb(lb) <= R; lb += 2)
ans += comp(get_mi_rb(lb), R);
}
} else if (i2.first == -1) {
auto [L, R] = i1;
if (vals[L] == 1)
ans += comp(L + 1, R);
else
ans += comp(L + 2, R);
} else {
auto [l1, r1] = i1;
auto [l2, r2] = i2;
for (int lb = vals[l1] == 1 ? l1 + 1 : l1 + 2; lb <= r1; lb += 2) {
int rb = std::max(get_mi_rb(lb), vals[l2] == 1 ? l2 + 1 : l2 + 2);
ans += comp(rb, r2);
}
}
}
}
};
solve(true);
if (std::min(r, c) > 1) {
for (auto& [v, ri, ci] : cl)
ci = c - 1 - ci;
solve(false);
}
if (r == 2 && c == 2) {
bool g = true;
for (auto [v, ri, ci] : cl) {
if (v == 0) {
g = false;
break;
}
}
if (g)
--ans;
}
std::cout << ans << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--)
tc();
}