I have just come up with 2 new problems inspired by today's div2D 2194D - Table Cut and I think they are quite interesting so I hope to share them with you all.
Original Problem :
(refer to the original statement for more clarity)
" 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,
$$$b$$$ = the number of ones in the other part of the table.
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,
$$$b$$$ = the number of zeros in the other part of the table.
Maximize the value of $$$a$$$ plus $$$b$$$.
New Problem 2 (Not yet solved):
$$$a$$$ = the number of ones in the left part of the table after the cut,
$$$b$$$ = the number of zeros in the other part of the table.
Maximize the value of $$$a \cdot b$$$.
Feel free to discuss the solutions of these problems in the comment section!
Auto comment: topic has been updated by meisgood (previous revision, new revision, compare).
I assume for problem 2 you are looking for better than $$$O(N^2M^2)$$$ time? That can be reached easily by adding a $$$b$$$ dimension to the dp.
Yes. I am wondering if there exist a solution with $$$O(NM \sqrt{NM})$$$ time or even better?
If anybody is interested in more problems using the setup: ABC442F — Diagonal Separation 2