The Stack Overflow podcast is back! Listen to an interview with our new CEO.
11

The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid $$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&&|&&|\\7&-&8&-&9\end{matrix}$$ ...


6

Lemma. $|a|+|b|=\max(|a+b|, |a-b|)$ for any real number $a$ and $b$. Proof 1. $|x|=\max(x, -x)$ for all real number $x$. So $$\begin{aligned} |a|+|b| &=\max(a, -a) + \max(b, -b)\\ &=\max(a+b, a-b, -a+b, -a-b)\\ &=\max(\max(a+b, -a-b), \max(a-b, -(a-b))\\ &=\max(|a+b|, |a-b|) \end{aligned}$$ Proof 2. There are $2 \times 2 = 4$ cases. $a\ge ...


6

The $a \times b$ grid graph has the vertex set $[a] \times [b]$, and edges of two types: horizontal edges $(i,j),(i+1,j)$ (of which there are $(a-1)b$) and vertical edges $(i,j),(i,j+1)$ (of which there are $a(b-1)$), for a total of $ab$ vertices and $(a-1)b+a(b-1)=2ab-a-b$ edges.


5

In the terminology of Nikoli Puzzles this is known as "Nanbarinku" or "Numberlink". The description does not always explicitly mention all squares must be covered, but this is indeed the case in all solutions I checked. According to Wikipedia Numberlink the problem is NP complete, with reference: Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), NP-...


5

No, your reasoning seems right. Sometimes problem setters just throw in such things in order to make the problem sound harder than it is.


2

You have an unweighted, undirected graph with $N$ vertices, and where each vertex has degree $K$. Then the problem of computing shortest paths can be solved in $O(KN)$ time using simple breadth-first search. Why is this faster than Floyd-Warshall etc.? Because Floyd-Warshall has to handle weighted graphs. In your case you have an unweighted graph: every ...


2

Firstly you did not write the complete question, to complete it, if $S$ is the maximum sum of weights in any sub-grid of lenght $ \le L$, then we have to report $S$ and length of the sub-grid with smallest integral side where sum of weights inside it is $S$ ( hint: it won't change the complexity of the solution ). But that is slight detail which I leave to ...


2

Let $b(p, \ell)$ be a boolean value denoting whether the horizontal segment whose left endpoint is $p$ and whose length is $\ell$ exists. Then the values of $b(p,\ell)$ for all possible $p$ and $\ell$ can be computed in $O(n^3)$ recursively using the fact that $b(p,\ell)$ is true iff $b(p,\ell-1)$ is true and $b(p+\ell-1,1)$ is true where $p+\ell-1$ ...


1

Travelling Sales Man is NP-complete. This problem isn't, it has an easy polynomial time solution. Don't go there.


1

Yes, there are efficient algorithms for this problem, using standard data structures for storing two-dimensional data. Here is a simple approach. Store all of the colored pixels in a quadtree. Next, for each sub-circle, compute it bounding box, so now you have a square instead of a circle. Query the quadtree data structure to find all points contained ...


1

There is a dynamic programming algorithm whose running time is $O(2^{4n})$. Suppose we have already chosen a configuration for the first $i$ columns. Mark a cell in the $i$th column as "red" if the cell to its right cannot be selected (i.e., the number of selected neighbors, not counting its right neighbor, is equal to the number in that cell), or "green" ...


1

Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time. You can find the number of faces in each component by Euler's identity. This can be done in linear time per component. Pick the component with the largest number of faces and find the cycle bordering that component. ...


1

Start by counting the left edges and top edges, then add in the missing right and bottom edges. For a $m \times n$ grid graph, there are $m \times n-1$ left edges (a left edge for each column at each row). Similarly, there are $m-1 \times n$ top edges. At this point, we are still missing the bottom edges for the last row, and the right edges for the ...


1

Let \begin{align} C&=\left\lfloor\frac WL\right\rfloor& R&=\left\lfloor\frac HL\right\rfloor \end{align} be the maximum number of rows and columns respectively. It sounds as though you're looking for the maximum $L^*$ such that, when $L=L^*$, we have $CR\ge N$. Let \begin{align} L_0&=\sqrt{\frac{WH}N}\\ C_0&=\left\lceil\frac W{L_0}\...


Only top voted, non community-wiki answers of a minimum length are eligible