New answers tagged optimization
1
Let's show that $\{a^n b^n : n \geq 0\}$ is not regular using Myhill's criterion (there are infinitely many equivalence classes):
The pumping lemma shows that $\{a^n b^n : n \geq 0\}$ is not regular. According to Myhill's criterion, if a language is not regular then it has infinitely many equivalence classes. Therefore the language has infinitely many ...
0
It is easy to see the fastest $m=\lceil n/k\rceil$ machines are used. Suppose the speeds of these machines are $p_1\le p_2\le\cdots \le p_m$, then we want to minimize $$p_1s_{\sigma(1)}+\cdots+p_1s_{\sigma(k)}+p_2s_{\sigma(k+1)}+\cdots+p_2s_{\sigma(2k)}+\cdots+p_ms_{\sigma(n)}$$
over all permutations $\sigma$.
By the rearrangement inequality, the sum above ...
0
This is called the offline dynamic storage allocation problem. Check out the papers cited by https://epubs.siam.org/doi/abs/10.1137/S0097539703423941 for a good review of the literature.
2
Suppose the gap between any two words in the same line spans a length of $k$, instead of 1. The only change needed in the Python code would be to change the line in def cost(i, j) from
w = offsets[j] - offsets[i] + j - i - 1
to
w = offsets[j] - offsets[i] + k * (j - i - 1)
def cost(i, j) returns the minimum cost needed for placing the first $j$ words, if ...
1
You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be discarded).
To ensure that you select at least $L$ items:
Add $n(V+1)$ to the value of every item.
Now the problem is equivalent to that of maximizing the number ...
1
You can compute a power of 2 using the operation of left shift, in C and related languages <<. For example, $2^n$ is the same as 1 << n.
An alternative is to precompute the mask for all possible input values, and store them in the array. You'll have to try it out to see whether this is faster than the other suggestion.
1
One simple algorithm is as follows. Start by choosing the dumbbell which is going to have the minimum weight (we are going to try all possibilities). Then take the $M$ dumbbells with maximal rep among those with weight above the minimum weight (if there are enough).
To implement this algorithm efficiently, start by sorting the dumbbells according to weight ...
0
The short answer: You can't. These are heuristics. There are no guarantees. They might fail badly; and there's no reliable way to detect that.
1
I've got bad news. There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely).
Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary. The knapsack problem has a pseudopolynomial ...
0
Your problem is essentially Minimum $k$-Union. In this problem (switching from $k$ to $\ell$), you want to find $\ell$ sets out of $A_1,\ldots,A_t$ which together cover the least number of elements. Denoting by $f(\ell)$ the solution of this problem and by $g(j)$ the solution of your problem, we have
$$
f(\ell) \leq j \Longleftrightarrow \ell \leq g(j).
$$
...
11
Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass?
Donald Knuth and Michael Plass. "Breaking Paragraphs into Lines".
https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md
https://github.com/baskerville/paragraph-breaker
https://cs.uwaterloo.ca/~dberry/ATEP/...
2
Form a directed graph of dependencies, with an edge $x\to y$ if course $x$ is a prerequisite for course $y$. Use Kahn's algorithm to topologically sort the graph. In particular, in each semester, you take all courses with indegree 0 (i.e., all courses where you've satisfied all prerequisites), then delete those courses from the graph.
This assumes there ...
3
This can be solved with dynamic programming; see https://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness or https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-20-dynamic-programming-ii-text-justification-blackjack/ for resources.
2
Yes. Every computation problem can be viewed as computing a function $f:\{0,1\}^ \to \{0,1\}^*$: on input $x$, the algorithm outputs $f(x)$.
Here is a corresponding decision problem: given $x$ and $i$, determine whether the $i$th bit of $f(x)$ is 1. If you can solve that decision problem, you can solve the original computation problem.
(Strictly speaking,...
0
The problem is NP-hard by a reduction from https://en.wikipedia.org/wiki/Independent_set_(graph_theory) or set packing.
One approach to solve the problem is to use integer linear programming: define 0-or-1 variables $v_1,\dots,v_n$, and then minimize $t$ subject to the constraints $\|\sum_i v_i x_i \|_\infty \le t$ and $\sum_i v_i = k$. Note that $\|\sum_i ...
2
I think this is actually "just" maximum cardinality bipartite matching, which can be solved optimally in $O(|E|\sqrt{|V|})$ time using the Hopcroft-Karp algorithm.
On one side, you have a vertex for each demanded impression (say, customer A demands 50000 of either "javascript" or "typescript", and customer B demands 10000 "javascript", so 60000 vertices in ...
2
If you had only one tag, this would become a knapsack problem: in particular, determining whether you could sell all the impressions would be exactly the subset problem. Therefore, the problem is NP-hard.
A plausible approach to solve it in practice would be to use integer linear programming.
1
Actually, derivative methods such as random search shorten the time allocated for function evaluation if the problem is big. On the other hand, derivative-free methods take much time to complete function evaluation that leads to a dramatic increase in optimization time.
-2
Using Trie Data Structure.
public class Solution {
public int[] solve(int[] A, int[] B) {
int ans[] = new int[B.length];
Trie root = new Trie();
for (int s : A) {
insert(root, s);
}
for (int i = 0; i < B.length; i++) {
ans[i] = search(root, B[i]);
}
return ans;
}
...
2
You can use meet-in-the-middle to reduce the running time to $O(n^{\lceil k/2 \rceil})$.
For simplicity, let me assume that $k$ is even.
The idea is as follows:
Partition $A$ into two parts.
For each part, compute a sorted list of sums of $k/2$ elements from the part.
For each $k/2$-sum in the first part, use binary search to find the best $k/2$-sum in ...
2
From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.
Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$ into at most $j$ segments. If no feasible ...
Top 50 recent answers are included
