I have just come up with 2 new problems inspired by today's div2D [problem:2194D] and I think they are quite interesting so I hope to share them with you all.<br>↵
↵
#### Original Problem :<br>↵
(refer to the original statement for more clarity)<br>↵
"↵
_Given a table of size $n \cdot m$, where each cell contains either $0$ or $1$. The task is to divide it into two parts with a cut that goes from the top left corner to the bottom right corner. The cut lines can only go right or down._↵
↵
↵
_$a$ = the number of ones in the left part of the table after the cut,_<br>↵
_$b$ = the number of ones in the other part of the table._<br>↵
_Maximize the value of $a \cdot b$._↵
"↵
↵
#### New Problem 1:↵
↵
$a$ = the number of ones s in the left part of the table after the cut,<br>↵
$b$ = the number of **zeros** in the other part of the table.<br>↵
Maximize the value of $a$ **plus** $b$.↵
↵
<spoiler summary="Solution">↵
Let $dp_{i,j}$ be the maximum $a+b$ in row $1...i$ if you cut between cell $(i,j)$ and cell $(i,j+1)$.<br><br>↵
The transition will be this:<br>↵
$dp_{i,j} = (max(dp_{i-1,k})$ for all $k$ from $0$ to $j$$)$ $+$ $($number of $1$ in cells $(i,1...j)$ $)$ $+$ $($number of $0$ in cells $(i,(j+1)...M)$ $)$<br><br>↵
which can be computed in $O(NM)$ time and memory.↵
</spoiler>↵
↵
↵
#### New Problem 2 (Not yet solved):↵
↵
$a$ = the number of ones in the left part of the table after the cut,<br>↵
$b$ = the number of **zeros** in the other part of the table.<br>↵
Maximize the value of $a \cdot b$.↵
↵
<spoiler summary="Not Yet Solved">↵
(blank)↵
</spoiler>↵
↵
Feel free to discuss the solutions of these problems in the comment section!
↵
#### Original Problem :<br>↵
(refer to the original statement for more clarity)<br>↵
"↵
_Given a table of size $n \cdot m$, where each cell contains either $0$ or $1$. The task is to divide it into two parts with a cut that goes from the top left corner to the bottom right corner. The cut lines can only go right or down._↵
↵
↵
_$a$ = the number of ones in the left part of the table after the cut,_<br>↵
_$b$ = the number of ones in the other part of the table._<br>↵
_Maximize the value of $a \cdot b$._↵
"↵
↵
#### New Problem 1:↵
↵
$a$ = the number of ones s in the left part of the table after the cut,<br>↵
$b$ = the number of **zeros** in the other part of the table.<br>↵
Maximize the value of $a$ **plus** $b$.↵
↵
<spoiler summary="Solution">↵
Let $dp_{i,j}$ be the maximum $a+b$ in row $1...i$ if you cut between cell $(i,j)$ and cell $(i,j+1)$.<br><br>↵
The transition will be this:<br>↵
$dp_{i,j} = (max(dp_{i-1,k})$ for all $k$ from $0$ to $j$$)$ $+$ $($number of $1$ in cells $(i,1...j)$ $)$ $+$ $($number of $0$ in cells $(i,(j+1)...M)$ $)$<br><br>↵
which can be computed in $O(NM)$ time and memory.↵
</spoiler>↵
↵
↵
#### New Problem 2 (Not yet solved):↵
↵
$a$ = the number of ones in the left part of the table after the cut,<br>↵
$b$ = the number of **zeros** in the other part of the table.<br>↵
Maximize the value of $a \cdot b$.↵
↵
<spoiler summary="Not Yet Solved">↵
(blank)↵
</spoiler>↵
↵
Feel free to discuss the solutions of these problems in the comment section!
