New answers tagged

0

This problem is NP-hard. It is easy to reduce the set partition problem to this problem. Let $S$ be an instance of the set partition problem and $s$ be the set of elements in $S$. Set $A = B = S$ and $k = s/2$. The correctness of the reduction is quite straight forward. However, the problem admits a pseudo-polynomial algorithm using dynamic programming. Let ...


0

One example of this in python code be # Loop until the sausage is cooked and we break out while True: # Check if the sausage is cooked if sausage.is_cooked(): # It is! let's leave the loop break else: # It wasn't ready, let's wait a bit longer wait() # Getting here means it must be cooked so let's eat self.eat(...


0

I understand the problem to be the following: Given sets $A_1,\dots,A_n$, find the largest $k$ such that there exist $k$ distinct indices $i_1,\dots,i_k$ that make $A_{i_1} \cap \cdots \cap A_{i_k}$ have a non-empty intersection. This can be solved in $O(nm)$ time, where $m$ denotes the maximum size of any of the $A_i$. It suffices to find $x$ in $A_1 \...


0

For anyone visiting this thread in the future, FIFO can have less page faults in some scenarios. In this one ( <2, 6, 5, 7, ..., ..., ...> ), it can be completed with 2, 8, 6. The access of 2 means that the least recently used page is 6, but the first page in is still 2. The access of 8 replaces 2 in FIFO, but 6 in LRU. The access of 6, therefore, is ...


0

Let $O(G)$ be an oracle that returns the maximum cardinality of an independent set in $G$; you can implement it given your oracle using binary search. Pick an arbitrary vertex $v$, and form a graph $G'$ by removing $v$ and all its neighbors. If $O(G') < O(G) - 1$ is false, then $v$ doesn't participate in a maximum cardinality independent set, and we try ...


2

The minimum number of vertices that have to be removed in order to disconnect the graph is known at the connectivity of the graph. Wikipedia outlines an algorithm for finding the connectivity of a graph. More efficient algorithms might exist. A related problem is the vertex separator problem, in which we want to disconnect two specific vertices by removing ...


1

Suppose that we add $Mx$ to all your functions. This doesn't change the $x$-coordinate of your breakpoints (because $m_1 x + b_1 - m_2 x - b_2$ has the same sign as $(m_1 + M) x + b_1 - (m_2 + M) x - b_2$). Furthermore, for each breakpoint $x$, it just increases the value of the $y$-coordinate by $Mx$. This means that you can recover the original breakpoints,...


0

I think that you don't need to connect the edges both ways even if the original graph was undirected. Because for the flow network, you need a directed graph, you could consider only the edges from $U$ to $V$. Then in this new graph $G'$, you will have a min-cut of 2, which gives you the answer $\{A,C,D,F\}$.


1

In textbooks, the solution given is 6+8+13+20+21= 68/5 = 13.6 This is because the textbooks (including Operating System Concepts 8e by Silberschatz,Gagne,Gelvin) define turnaround time as the time that elapses between the submission and the termination of the process, which is the sum of arrival time, waiting time, execution time and time spent in device ...


0

This problem is called the independent vertex cover problem and it is solvable in polynomial time. Note that the set $S$ must be a vertex cover means that each edge has an endpoint in the set. On the other side, being an independent set means that each edge has at most one endpoint in the set. Hence, each edge has exactly one endpoint in the set. That means ...


2

The online version can be solved in $O(n\log n)$ amortised time, possibly using the technique you already came up with. The key is to maintain just the nonoverlapping intervals that result from merging intervals wherever necessary. Maintain an ordered list of the endpoints of segments in a binary search tree, with each endpoint represented by a pair $(x, ...


0

You can use the Tseytin transformation to convert a circuit to a CNF-formula in linear time (wrt to the number of gates in the circuit). The naive transformation can indeed result in exponentially larger formulas.


0

Set the size of the bag to the value you are trying to reach $t$. For each element $x \in S$ add one item to the set having both its weight and value equal to $x$. The claim is the $(S, t)$ is a yes instance of the subset sums problem if and only if the optimal value of the bag is equal to $t$ (why?).


1

You can prove this by a reduction from the Hitting Set problem (which is NP-Complete): Given a base set $U$, a family $F = \{S_1,\ldots,S_\ell\}$ of subsets of $U$ and an integer $q$, decide if there exists a set $H$ of size at most $q$ which intersects every set in $F$ (this is called a hitting set). So suppose given an instance of the Hitting Set ...


2

Since the processes can only receive message from their adjacent neighbors, we could first have the all the processes propagate the maximum values through the grid in downward direction in parallel. Similar to a one dimensional array in which we have to find the maximum value. But here, we do that in parallel for n columns of processes. After this, the ...


2

This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X. Consider the set of choices you have: For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the ...


4

I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime. Suppose you have an algorithm which works very fast in that case. Then, given any array of integers, you can split it up into an array of even integers and an other of odd integers in linear time. You can then ...


2

Since you already implemented IDA$^*$ you certainly understand why it expands more nodes than A$^*$, i.e., it starts from the start state with a new depth-first traversal in each iteration. Note first that, the overall number of nodes visited by IDA$^*$, while necessarily larger than A$^*$ is not that much larger. The reason is that the number of nodes at ...


1

An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $m$th entry (in order) in a skiplist in $O(\log n)$ time in a skiplist of $n$ entries. In other words, it takes a skiplist that is not an indexable skiplist $O(n)$ time, on average, to find the $m$th element in order in a skiplist, while an ordered skiplist can do ...


0

The problem you posted is a single source shortest-path which given a graph G(V, E) and a designated vertex $s\in V$, requires computing the shortest path from $s$ to all vertices $v\in V$ where the cost of a path $\omega(\pi)$ is defined as the sum of all edge costs in $\pi$. For this specific problem in particular, I would highly recommend a straight ...


0

Imagine you have the following graph (in red are the minimum capacities): The $(s,t)$-path with the lowest flow demand needs $1$ unit of flow, but the minimum flow is $4$. And the $(s,t)$-path with minimum sums of capacities has a sum of $2$, so this also doesn't work.


0

The SWMR ABD algorithm cannot emulate conditional write per se, but if the single writer is a stable leader, with a fault-tolerant leader election algorithm and appropriate modifications to the ABD algorithm (i.e. epoch counters in each message), it is possible to emulate conditional write, as shown in this industry paper: https://arxiv.org/abs/1702.04242. ...


3

Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them. A gangly polyomino in a double-width problem instance Given the initial $a \times b$ problem instance, create a new instance of size $(2a+1) \...


3

This is just speculation, but perhaps what VLC is attempting is to simulate... perfect randomness. That is, each song is picked uniformly at random, independently of previous songs. According to the coupon collector problem, if you have $n$ songs in your list and want to hear all of them, you will have to wait for roughly $n\ln n$ songs to be played. By that ...


1

One reasonable method is to choose a random sample of, say, 1000 items from the array. This can be done in a single pass (say, using reservoir sampling) or using random access (but here we need only 1000 random accesses, so this is probably faster than a single linear pass through the data). Compute a histogram of those 1000 items, and use that to select ...


3

Create a new graph $G' = (W,F)$ as follows: For every every $v\in V$, create three vertices $v_0,v_1,v_2$ in $W$. The index $i$ in $v_i$ represents the fact that any path to this vertex uses exactly $i$ red edges. For every edge $(u,v)\in E\setminus E'$, create the edges $(u_0,v_0)$, $(u_1,v_1)$ and $(u_2,v_2)$ in $F$. For every edge $(u,v)\in E'$, create ...


1

These are called the connected components of the graph. For most purposes, any graph traversal algorithm will suffice for finding the connected components. However, if you have a really big graph, see this question on Stack Overflow for practical considerations.


2

Every such arrangement of 15 balls to 21 boxes corresponds, in a one-to-one fashion, to a string of the form *|**||||...|*, where there are a total of 35 symbols in the string, exactly 15 stars and 20 bars. (Think of each * as a ball, and each | as a divider between two boxes.) These, in turn, correspond to the set of binary strings of length 35 that ...


3

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values). Let say we know that all integers in $A$ are 32-bit values. Use the following steps: Create an empty trie. Every node of trie may contains at most two children for 0 and 1 bits. Insert all values in $A$ into ...


1

This is only an attempt to provide another implementation that solves the nth stack sorting problem (I had to give it a name, ...) with permutations of an arbitrary size $n$ in $O(n)$ ---though the implementation given below works only for digits in the range $[0, n)$. Actually, the analysis provided by user111398 is very nice and (s)he is absolutely right: ...


1

As previously suggested we will discuss the inverse problem, sorting. If we want to sort 5 3 6 2 7 4 1 to 1 2 3 4 5 6 7 by moving elements to the left (top) the only way to get 7 to the bottom is to move 4 and 1 out of the way. Then to get 6 as second last element we also need to move 2. Then to get 5 at the right position we also need to move 3. Now that we ...


3

So I finally managed to do it, here's the answer for future reference. The idea is not to compute the distance map of the image, but of its complement. Here's a example to better understand : You have these binary images, where our objects are in black : Object $X$ Object $Y$ To compute $h(Y, X)$, you need to compute the distance map $dX$ of the ...


1

So if you are not updating the #satisfied/cost ratio after every selection, this algorithm won't perform well. Let $n$ be the number of people and $m$ the number of meals. We denote the cost of meal $i$ by $w_i$. Let's say people $1...n-1$ are all satisfied by meals $1...m-1$ which all have the same cost, but person $n$ will only eat meal $m$. If the cost ...


1

Note that a 2-regular graph is a disjoint union of cycles. Since you have a designated starting vertex $v$, you can disregard all cycles not containing $v$. Put differently, we can assume that the input graph is a single cycle (whose edges are labeled with zeros and ones). Your current $\Theta(\ell)$ solution is optimal since even reading the input requires ...


1

Thanks to user111398. Here is some (Excel) VBA code to prove it works: Option Explicit Public Sub Test() Dim sPermutation As String Dim lIndex As Long For lIndex = 0 To 2 * 3 * 4 * 5 - 1 sPermutation = GetPermutation(lIndex, "ABCDE") Debug.Print sPermutation & ": " & GetRotates(sPermutation) Next End Sub Public ...


2

Let $F$ be a function that maps integers from $0 \dots N-1$ to $\{0, 1\}$. We want to find $x$ (which is promised to be unique) such that: $$F(x) = 1$$ Now let's take two random integers $a$ and $b$ from $0 \dots N-1$ and output: $b$, if $F(a) = 0$ $a$, if $F(a) = 1$ For any fixed $x$ and $y$ we have: $$P_{a=x} = P_{b=x} = P_{a=y} = P_{b=y} = \frac{1}{N}...


0

To compute the probability for $\geq n$, you first compute the probability for an unbounded until and subtract from it the probability for $\leq n-1$. If you compare the sets of paths these formulas represent then you will that they are indeed the same. You start off with a set of all paths satisfying "reach B via C", let's call it $T$. From this set, you ...


0

Store them in a heap or priority queue, keyed on the size of the message. This way, if you want the $k$ largest messages, you can keep track of that as each message arrives. This will require $O(k)$ space to keep track of the $k$ largest messages at each step, and $O(\log k)$ time per message that arrives, so it should be pretty efficient.


0

a 2-CNF formula is satisfiable if and only if there is no variable that belongs to the same strongly connected component as its negation. But I don't find any reason for the right to left direction. how can the inexistence of such variable guarantee satisfaction of CNF? Think of a variable assignment for some unsatisfiable 2-SAT instance. This means ...


3

Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given ...


6

Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are ...


0

The given information tells you absolutely nothing about the runtime of B. As an example, let’s say the solution is a vector of N numbers which can be found in O(n^2 log n) but not in O(n^2), and let B be the problem “What was your input”. Solve the problem in O(n^2 log n), pass the solution to B, get it back in O(n), all consistent with the information ...


0

Any finitely terminating non-deterministic algorithm can be made deterministic by using depth-first search on the tree of possible executions. Or, to explain it another way: each time you have a non-deterministic choice, fork the program into multiple copies, one per possible choice. Forking might be done by calling the operating system's fork() call (very ...


1

An algorithm can be seen as the steps needed to go from a well defined type of input to some well defined output. The input can therefore be everything that one can represent within a computer. In the algorithm you are asking for it seems like the input has already been classified as specific good as in apples are already classified as apples, had it not ...


0

So I guess you are showing that an array can be made a heap in linear time. $(\log n - i)$ counts the maximum number of swaps that a node may require, starting at level $i$, and descending to its final level; at most it could become a leaf. For instance if it starts at level $0$, then it could possibly require $\log n$ swaps; this would happen if the node ...


1

The time complexity doesn't just depend on N. It's possible that due to the coefficients, you have to evaluate the polynomial with very high precision to determine whether some minimum of the polynomial near a point x has a value >0, =0 or <0, and you need to know this to know the number of roots near to x (0, 1, or 2).


0

In the first part where the summation $\sum_{i=1}^{\log n}i2^i$, you see that whole summation can be written as that chain of summations (if you sum them all up you'll end up getting the first form on the top). Then you use the summation of power two's formula, i.e. $\sum_{i=0}^{n}2^i= 2^{n+1}-1$. In the first line $=2+2^2+...+2^{log n}$ the formula is ...


1

It turned out we can achieve it in $O(nM)$ time where $n$ is the number of distinct items in the store, and $M$ is the final bill. We can build a 2-dimensional array with size $C[T, M]$ as follows: $C[i, j] = 1$, if there exists a way to add items from $\{t_1,t_2,...,t_i\}$ that adds up to $M$. $C[i, j] = 0$, if we cannot find items that adds up to $M$. ...


2

This is known as the closure problem. I quote the Wikipedia paragraph describing the reduction to the max flow problem here. As Picard (1976) [1] showed, a maximum-weight closure may be obtained from $G$ by solving a maximum flow problem on a graph $H$ constructed from $G$ by adding to it two additional vertices $s$ and $t$. For each vertex $v$ with ...


2

Here is an iterative algorithm to enumerate such matrices, which proceeds by induction on $m$. I suspect it will be be better than brute force. Let condition (2') be that every pair of rows is $i$-interlacing for some $i\in \{0,1,2\}$. Note that every matrix that satisfies conditions (1), (2), (3), (4) can be broken up into the concatenation of a matrix $...


Top 50 recent answers are included