5 ms·
It might be easier to define f(m, n, v) where f(m, n, v) is the number of v-vertex shapes that can fit within a m-n square with exactly one vertex in the top le
by tylerhou 5y ago
It might be easier to define f(m, n, v) where f(m, n, v) is the number of v-vertex shapes that can fit within a m-n square with exactly one vertex in the top left hand corner. Then Q(m, n) = \sum_{i \in m, j \in n} f(m, n, 4). f also lends itself to a much easier recurrence.
- marcodiego 5y agoFor me, it seems easy if we don't have to care about the imposed restrictions: no crossing and no straight angles. Hmmmm.... New ideas coming... Maybe we don't have to care about crossings: any crossing can be solved by reordering the vertices, so, all we have to care about is the number unique vertices positions! I still don't know how to avoid straight angles though.
- tylerhou 5y agoIf you didn’t care about the restrictions, then the answer is N*M choose 4.
- marcodiego 5y agoI think I've made some progress... When one line is added to the problem, it allows us to put 1 or 2 vertices there, so... Consider U(m, n) as the number of new unique forms possible for Q(m, n). I'm not sure, but it looks like: U(1, 1) = 1 U(m + 1, n) = U(m, n) * (n + (n+1)*n/2) - X U(m, n + 1) = U(m, n) * (m + (m+1)*m/2) - X Where X is the number of invalid forms generated adding one or two vertices in the new line because of straight angles in diagonals. I'm considering only diagonals, because adding only one or two vertices in the new line will not align 3 vertices horizontally or vertically if all "previous forms" were valid. If we can find X, then, I think Q is given by: Q(m, n) = m*n*U(1, 1) + (m-1)*(n-1)*U(2, 2) + (m-2)*(n-2)*U(3, 3) +...+ 1*1*U(m, n)
- tylerhou 5y ago> If we can find X Almost certainly we need to add terms into the DP state to compute X; unfortunately adding just the number of vertices doesn’t work as some triangles have two edges in which a point can be inserted to create a quadrilateral, while others only have one. The difficulty is finding those terms, though…
- marcodiego 5y agoWhat do you mean by "the DP state"? Also, I think my previous formula is wrong. Maybe it is the sum of: (m - i + 1)*(n - j + 1)*U(i, j) With i, j in [1..m]. But maybe it is still wrong because U(i, j) will re-count combinations from U(i - 1, j) and U(i, j - 1)... Argh! This is complicated! I think I'll have to revisit it if I ever have a good idea.
- tylerhou 5y agoBy DP state, I mean the arguments to the recursive function (for U, the state is the tuple (i, j)). For example, if you wanted to use DP to compute all-pairs-shortest-paths (Floyd-Warshall), you add a third parameter to the DP state ((f(u, v, k)).
- marcodiego 5y agoSure! Dynamic programming, right?