Tag Info

4

The answer depends heavily on what operations you allow to appear in the trees. If the tree uses only addition, subtraction, and multiplication, this is an instance of the polynomial identity testing problem, which can be solved in polynomial time by a randomized algorithm. Basically, you pick random values for $a,b$ and check whether both trees return the ...

3

In general, if you know nothing about the array, then searching linearly is the best you can do (a simple adversarial argument is enough to justify this). However, if you know more about the structure of the array, there are plenty of things you can do. For example, imagine the array has the following property: its elements are sorted increasingly up to a ...

3

If the algorithm terminates at all then $A[i] = i$ for $i \leq n-1$, and so $A$ is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching $i = i_0$, we know that $A[j] = j$ for $j < i_0$, and so $A[i_0],\ldots,A[n]$ is a permutation of $i_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices ...

3

Use a product construction, to construct a new graph whose vertices are given $(x,y,z,k)$, where $k$ counts the index into the sequence of colors (i.e., we are currently at $k$th vertex in that sequence). Then, find the shortest path in this new graph using any standard shortest-path algorithm. If all weights are non-negative, you can use Dijkstra's ...

2

By noticing that $H$ remains a tree except when $H \gets H \cup (a,b)$ happens, you can use a ST-Tree[1], which you can easily modify to support queries of the form "what is the maximum weight edge on the path from $a$ to $b$" Instead of adding $(a,b)$ directly to $H$ first you check if $a$ and $b$ are connected (using the ST-Tree or a Union-Find)...

2

The text has a luminance value $t_0$ and the background occupies a luminance interval $[L_0,H_0]$, $L_0 \le H_0$. I think what you want is to ensure a separation of at least some $s$ between them. There are many degrees of freedom here; one way to capture most of them is to decide beforehand on a way to penalise changes in these variables, as well as the ...

2

Build a grid graph, with one node per entry in the matrix, and edges between each pair of adjacent nodes. Also add a source node $s$ with an edge from $s$ to each blue node, and a sink node $t$ with an edge from each white node to $t$. Set the capacity of each edge to 1, except the $s$-to-blue edges have capacity $\infty$, and the white-to-$t$ edges have ...

2

I don't see a need for any interesting algorithm. In its essence it is equivalent to the following: given an array $A$ of integers and an integer $x$, move all instances of $x$ to the front of $A$, keeping the rest in the same order. Once you can solve that, you can apply it to each node of your tree. To move all instances to the front, one approach is to ...

2

The answer by nir shahar goes to the point. Another way to see this is to consider Radó's non-computable function $S(n)$ (the maximum number of steps a Turing machine with $n$ states does when started with an empty tape before halting). If you could compute your function $M$, you could compute $S$ (for each TM of $n$ states compute your function $M$, run the ...

2

I think this is correct and incorrect at the same time. It depends on how we define the problem we want to solve. Formulation I If we are interested in an algorithm that given $\langle M, w\rangle$ will tell you how much time $M$ runs on $w$ (assuming it halts), then there is such an algorithm: emulate $M$ on $w$ and count the number of steps it does until ...

1

In the rest of the answer I will slightly abuse the notation by treating $A$ as a set. For simplicity I will also assume that the integers to sort are distinct, so that we are dealing with sets instead of multisets. This assumption is easy to remove. Construct a min-heap $H^-$ and a max-heap $H^+$, each containing all elements in $A$. Extract the minimum $\... 1 One approach is to guess$a$(i.e., iterate over all possibilities for it, and the following for each possibility). Then, you can infer the value of$b$, namely,$b = a r_b/r_a$, so test whether$b \in B$. Do the same for each of$c,\dots,z$. If they all work, then you have found a solution; otherwise, proceed on to your next guess at$a$. This should ... 1 The problem statement is correct. I think you getting confused about: repeat$j \gets j-1$until$A[j] \leq x$. It means that if$A[j]>x$then do$j \gets j-1$. Similarly, loop$8-10$means that if$A[i]<x$then do$i \gets i+1$. Therefore, the algorithm executes in the following way on$A = [1,2]$: After the loop$5-7$,$j$becomes$1$since$A[2] &...

1

Since $f(n) \in \Theta(n^2)$ there exist two constants $n_0$ and $c>0$ such that $f(n) \ge c n^2$ for all $n \ge n_0$. Suppose then that $f(n) \in O(n)$. For some $n'_0$ and $c'>0$, we have $f(n) \le c'n$ for all $n \ge n'_0$. Selecting $n = \max\left\{ n_0, n'_0, 1+\left\lfloor \frac{c'}{c} \right\rfloor \right\}$ leads to the following contradiction: ...

1

Let the input array be $A[1 \dots n]$ and consider any contiguous subarray $A[i \dots j]$ of $A$ such that $i \le M-1$ and $j \ge M$ (that is, $A[i \dots, j]$ includes both $A[M-1]$ and $A[M]$). The subarray $A[i \dots j]$ maximizes $\sum_{k=i}^j A[k]$ if and only if: $A[i,\dots M-2]$ is a (possibly empty) suffix of $A[1 \dots, M-2]$ that maximizes $\sum_{k=... 1 If you're familiar with cycle sort, you can start to see that this algorithm also operates in a similar way (although it's super inefficient). Essentially, the inner loop doesn't terminate until the element in the current position$i$is$i$. So when the outer loop moves on to the next element, you are guaranteed that the subarray to the left is sorted and ... 1 In the book Kernelization by Fomin, Lokshtanov, Saurabh, Zehavi (which is downloadable as a PDF on the first author's homepage) you find Chapter 4. Crown decomposition. This should point you to the answer. 1 I suspect they probably mean $$ub_d = \max_i x_i^d$$ where$x_i^d$is the$d$h coordinate of$x_i$; and similarly for$lb_d$, but using$\min$instead of$\max$. But I don't know -- I am just speculating based on context. 1 Let$A = \{ i : x_i \geq 1/k \}$. By construction,$|A| \leq k \sum_i x_i \leq k \mathrm{OPT}$. The set$A$is a set cover, since if$S_j = \{i_1,\ldots,i_\ell\}$(where$\ell \leq k$) then$x_{i_1} + \cdots + x_{i_\ell} \geq 1$, and so$\max(x_{i_1},\ldots,x_{i_\ell}) \geq 1/\ell \geq 1/k\$.

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