4
Your problem is a special case of enumerating the vertices of a convex polytope, and there is an efficient (polynomial-delay) recursive algorithm for your special case, which I will describe next.
If $a_1+\dots+a_d > 1$, then there is no solution, and you can terminate. If $a_1+\dots+a_d=1$, there is a single solution $(a_1,\dots,a_d)$, so output it and ...
3
This can be solved in polynomial time.
Say that in the input we are given the number of snakes $n$ and for every snake the squares it occupies. Let $m$ denote the total number of squares in all snakes. Assume every snake occupies at least three squares.
If no square has $x$-coordinate in some interval $[a, b]$, we can compress that interval into a single ...
2
The polymake tool/library can do exactly what you asked for, if you are interested in a practical solution. See here for a brief tutorial.
2
In the following I will call $C:=\{x:\forall i.a_i\le x_i\le b_i\}$ the cuboid and $H:=\{x:\sum_i x_i=1\}$ the hyperplane. I claim that all defining vertices of the polytope $C\cap H$ lie on the intersection of the $1$-dimensional skeleton $S:=\{x:\exists j.\forall i\neq j.x_i\in\{a_i,b_i\}\}$ with $H$, which can be evaluated by $\mathcal{O}(2^{d-1})$ ...
Only top voted, non community-wiki answers of a minimum length are eligible
