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

New answers tagged

0

You could just compare the values in a loop, which is trivial and works just fine. And we are now arguing about constant factors. Consider how many array elements you read if the first two items are different (answer: n items from each array). Quite inefficient. As a micro-optimisation adding k elements and comparing the sum would often be faster than ...


3

An alternative to OmG's answer (which is great) would be to sort your points into an ordered array where you can find any points neighbors by looking at the points on either side. This method would be very good if you need to work with the same polygon for many calculations as most work is done upfront but afterwards the cost of determining if two points are ...


0

Your question is interesting because often, when such a problem arises in practice, programmers jump on the naive approach, comparing each element of the first array with each element of the second array and saving the differences. This shows that programmers often do not dwell on algorithm optimization, thinking that on modern architectures such an ...


0

So the core of the problem is to solve the 2 sum closest problem for a particular i: Given a target value, find a pair of numbers who's sum is closer to the target value. The two pointer approach is the procedure you have described with j and k. (from now on called l and r for left and right) Your question is why can we decrease r or increase l. The ...


6

As the polygon is convex, it is simple! Two vertices is consecutive if all other vertices are located just on one side of the line that goes through these two points. This means that the cross product of this vector with the others all have the same sign (all negative or all positive). For example, if those two points are called $P_1$ and $P_2$, you should ...


3

Given that the polygon is convex, its centroid $C$ is in its interior. Test the gradients of the lines $CV$ for each vertex $V$. This gives a linear time test.


0

In the rules of chess, one player can demand a draw when the same position is entered three times. If your opponent can demand a draw, the value of the position is 0 in the best case. So if you look forward far enough, you see that a move leading to repetition may not be that good. (In this case, you would choose the second best move if it has a value > 0, ...


1

Note: there is no way to know how Google does it. All we can do is speculate based on whatever information is publicly available. If you want to know, you have to ask them, not us. Google Docs' collaborative features are reportedly an offshoot of Google Wave. Google Wave, in turn, reportedly used Operational Transformation. As a very high-level basic ...


1

So, we have that $f(n) = O(n^c \log^k(n)) = O(n^0 \log^2(n))$; and since $log_b(a) = log_2(1) = 0 = c$, we are in the 2nd case of the Master's theorem (work to divide the problems is comparable to the work on subproblems (wiki)); thus, applying the theorem, we get $T(n) = \Theta(log^3(n))$. On the floor operation, I don't know what is the cleanest way of ...


1

So rewriting my answer from the comments. Let $n$ be the size of the input (say the total size of both arrays), then $\Omega(n \log n)$ is a reasonable lower-bound on the running time of the problem. (See this paper for a similar bound). One way to solve it is hence to sort both arrays and then using sliding window technique (two pointers) to find two ...


0

There are three ways how you could proceed: If both arrays are already sorted for example in ascending order, then you start at the beginning of the first array and the end of the last array; if the sum is too small you skip to the next element of the first array, if the sum is too large you skip to the previous element of the second array, and so on. If ...


1

In C++ we call this algorithm rotate. It was made famous by Sean Parent's C++ Seasoning talk in 2013 (discussion of rotate begins at 8:53). Here is cppreference.com's possible implementation adapted into C. /** * @brief Moves two ranges of elements in an array. * * The elements in the range [first, n_first) to directly before * ...


0

Let the string be $S_1,\ldots,S_n$. For every $m$, find the minimum number of words that $S_1,\ldots,S_m$ can be split into. I'll let you work out the remaining details.


3

In a game-theoretical sense, both of the moves you describe are equally good in the scenarios you describe, so the algorithm is "correct" in that it doesn't matter which move it picks -- you do not explicitly encode a preference for faster wins (or faster gains of $+100$) over slower scores. Introducing a discount factor to explicitly encode such a ...


3

This is because you are not using a discount factor in your search. A discount factor $\gamma$ is a number between 0 and 1. The discount factor describes the preference of an agent for current rewards over future rewards. When $\gamma$ is close to 0, rewards in the distant future are viewed as insignificant. When $\gamma$ is 1, discounted rewards are ...


1

The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) > c(u)$ causes the inner while to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.


2

You can reduce your problem to maximum bipartite matching on the graph $G = ( U \cup C, E)$, where $E = \{ (u,c) \in U \times C \; : \; u \in c\}$.


1

Your groups of tiles can be considered as graphs, where vertices represent tiles and two vertices are connected by edge if and only if their corresponding tiles touch each other side by side. So, in terms of graph theory, the problem you are trying to solve is known as CISE (Connected Induced Subgraphs Enumerating). You can find a number of papers, ...


0

$\mathbf 1.$ Say there are two paths from node A to node B. Path1 has 4 edges. Path2 has 2 edges. An overall increase in edge weight by x increases, the cost of Path1 by 4x. the cost of Path2 by 2x. If Path 1 was the optimum path found by Dijkstra then in order for it to remain the optimum path even after the increase. $Cost_{Path1} + 4x < Cost_{...


0

$$ \mathrm{OPT}[i,j] = \begin{cases} \max_{h\in\{i+1,\dots,j-1\}} \left\{\mathrm{seq}[i] + \mathrm{seq}[h] + \mathrm{seq}[j] + \mathrm{OPT}[i,h] + \mathrm{OPT}[h,j]\right\} &\mbox{if } j-i > 1 \\ 0 & \mbox{if } j-i = 1 \end{cases} $$ where $1\le i<j\le n$. Thank you all for your advices, especialy @Steven for providing link to another ...


1

So, basically in heap representation, $LEFT(i)$ refers to the index of $i's$ left child. What we want to show is that index $⌊𝑛/2⌋+1$ is a leaf and is not a middleware node which can be proved if we could show the index of the left child is larger than the number of elements in the heap. On the other hand, $LEFT(⌊𝑛/2⌋+1) = 2(⌊𝑛/2⌋+1) = 2⌊𝑛/2⌋+2 $ and ...


0

I can see several problems with your solution. First of all, I don't think you are updating the balls after every second, as I would expect there to be a loop from $1$ to $t_i$. I think you are adding $t_1$ seconds, then adding $t_2$ seconds etc. Which brings up the second problem. I think you are treating the intervals $t_i$ as incremental, whereas in the ...


1

Your explanations are a bit incorrect. What line 10 does is to add the high 64-bit word of $x_l y_l$ (%rdx after line 9) to $2^{64} (x_h y_l + x_l y_h)$. The low 64-bit word has been computed in line 9 and is in %rax. Now, all the overflows that have been ignored will affect bit 128 only, i.e. the obtained result can differ from the correct result only by a ...


0

If there is no upper bound on the number of classes per semester and the dependencies are acyclic, this can be solved by a modified topological sort as follows: Schedule every class for which all (zero or more) prerequisites are met in the earliest semester in which they are available. Repeat this for all remaining classes (i.e. those not yet scheduled), ...


0

In a binary tree, you can represent the tree from root to leaves as follows: 0 root 1 2 root's children 3 4 5 6 root's grandchildren etc. To get the children of a node, you take its index x and compute 2x+1 and 2x+2. This makes some certain assumptions: Each node has exactly two children, except the leaves, which are all on the same (or two neighboring) ...


1

You could compute a full Single Source Shortest Paths (SSSP) at the beginning for both of your vertices (s and t). Then, whenever you add an edge, you update only the shortest paths affected, i. e. you check whether the edge uv provides an improvent for sv, su, tv or tu. If not, your SSSP is still correct. If it gives an improvement, you then also have to ...


0

A possible solution may be to compute the all pair shortest path matrix and then select the largest value in the matrix. As long as |E|<<|V|^2 or the graph is not dense, your complexity constraint should be satisifed. Johnson's algorithm does it in O(|V|^2 log |V|+|V||E|). Refer to this for a better understanding of time complexity in case of ...


0

This answer on stackoverflow has an example of why 1 is false. https://stackoverflow.com/questions/10790909/adding-weights-to-all-edges-of-graph-change-in-spanning-tree-and-shortest-path Quoting from the above: Consider a graph with 3 vertices (A,B,C), with the following edges: A-B = 1 A-C = 0 C-B = 0 The shortest weighted path between A and B is ...


0

The subproblems can be broken down as follows. f0 :- Number of available 0s. f1 :- Number of available 1s. ld :- The last digit of the string generated till now. dp[f1][f0+f1][0] = dp[f1][f0+f1-1][0] + dp[f1-1][f0+f1-1][1] dp[f1][f0+f1][1] = dp[f1-2][f0+f1-2][0] + dp[f1-1][f0+f1-1][1] which basically boils down to, Say at any step the string is S0 ...


1

We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want. Sorting ...


1

First, we randomly select an element that is not the smallest one as a pivot, and partition the elements into two subsets: the ones less than the pivot ($P$) and the ones no less than the pivot ($Q$). Let $S$ be the sum of elements in $Q$. If $S=C$, then $Q$ is exactly the optimal subset we want. If $S<C$, then the optimal subset is the union of $Q$ ...


0

One solution that comes to mind is to first build a directed graph where every vertex represents a vertex. An edge goes from Box A to Box B if B fits into A. One can easily verify that this graph contains no cycles. A maximum sequence of nested boxes is equivalent to the longest path in this directed acyclic graph. A longest path in a DAG can be found by ...


6

Say we have strings $a = a_0a_1...a_{n-1}$ and $b=b_0b_1...b_{n-1}$. First concatenate $a$ with itself and remove the last character. You should get a new string $a=a_0a_1...a_{n-1}a_0a_1...a_{n-2}$. Now we are interested in substrings of size $n$ in new string $a$ that are orthogonal to $b$ (this is a very classic trick to deal with cyclic strings/arrays). ...


2

$\texttt{index1}$ is index of the first element of subarray 1, $\texttt{index2}$ is index of the first element of subarray 2 and $\texttt{array_end}$ is index of the last element in the array. From $\texttt{index2}$ to $\texttt{index2_i}$ is a buffer that contains the elements to be inserted after $\texttt{index2_i}$ reaches array_end. From $\texttt{...


3

We can assume without loss of generality that $y$ is the first position, and that the first position is zero. Suppose that there are $n$ elements in the array. Then we want to apply the permutation $\pi(i) = (i+x) \pmod n$. Two elements $i,j$ are in the same cycle of $\pi$ if $i \equiv j \pmod {(n,x)}$, which means the the cycle leaders (minimum elements of ...


2

Let's solve your example question first. Say, we want to know the number of combinations of size 2 possible from $A, B, C$. This would be equal to for each element in $A$, pair it with each element in $B$. This gives us $|N_A||N_B|$ combinations of size 2. for each element in $A$, pair it with each element in $C$. This gives us $|N_A||N_C|$ combinations of ...


1

I think of divisibility mostly in terms of decomposition into prime factors: to be divisible by a query integer $q$, an integer $a_i$ has to be divisible by at least the same power of each prime in $q$s decomposition. Divisibility by different primes is independent: I think of this (divisibility of integers from a set that can be preprocessed) as a ...


0

If the only condition is that $a_i >= 3a_{i-1}$ for even i then this should be quite trivial? What subset sums can you achieve by just picking the last two array elements?


0

The point of my exercise is to encode the path existence in CNF Well, a trivial way to do this is by reducing the problem to 2-SAT, following this set of rules: Assing a literal to every edge of your graph, for example first element in first row become $a$, second element in first row become $b$ etc. Put in OR relation the literal in the "start" position ...


1

Your attempt runs into a huge problem with the input [1, 2, $2^{63}$]. Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you. For this specific problem, I think ...


0

Maintain an array Composite_in_Array[n] and Multiples[n] initialize with zero. for i=n-1 to i>=0 if( Composite_in_Array[i] !=0 ) for j=i-1 to j>=0 if( A[j] % A[j] == 0 ) Composite_in_Array[j]=1; Multiples[i]++; Find the index with largest value in Multiples[]. Corresponding value in A[] will be your answer. This ...


0

When measuring comparisons, we usually only charge comparisons of elements of the array (more accurately, we charge comparisons for the datatype of array elements, but not of array indices). In the example of linear search, at each iteration you are comparing one element of the array to the input element being searched. So in total, you are making exactly $n$...


2

I'll explain the Dynamic Programming approach to your problem using your sample sequence $[2,1,5,3,4]$. This approach is based on analysis of sub-problems - in your case each sub-problem is simply a task to find the maximal value (in the sense you described in your question) for some sub-sequence. These sub-problems are related to each other - this ...


3

It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the corresponding subset sum instance has answer "yes".


1

When the value of $t_1$ is not present you are just given weighted intervals from left to right with weight value, and you should ask questions of the form, what is the sum of the weights of intervals that contains x. If we know all intervals/weights before hand this whole task is easy without any fancy data structure, just adding the beginning of the ...


0

To more generally answer @DavidChian, Thank you very much, especially for cheering me up a bit. Now, if I understood your post right, you say, that there isn't a general way, but you still gave the following starting point: instead of my proposed number sequence, you choose a Data Flow Graph (DFG). Using your model, where the most effective space-time ...


0

The algorithm in the (edited) answer has worst-case quadratic time complexity. (An worst-case example is a tree where there are just two strands and the given nodes are the two leaves.) A (non-recursive) $O(n)$ time and $O(1)$ space algorithm, assuming that nodes have parent pointers: Compute the height of both target nodes. Until the heights are equal, ...


2

This problem can be solved greedily. First remove all digits that are present in both arrays since they can be used as prefix of the number and we keep difference of high order digits as low as possible. Add them to the numbers from lower digits to higher digits in order to obtain smallest $n_1$ at the end. Observation: after this process is done all ...


1

Derp, nevermind. I observed that on the last iteration, the inner loop takes $N$ steps. On the previous iteration, the inner loop would take $\frac{N}{2}$ steps. Overall, this would take $N, \frac{N}{2}, \frac{N}{4}, \frac{N}{8},...$ steps, which has a geometric sum to $2N$ steps. Therefore, the loop is $O(N)$.


1

Since there are no updates there is a rather simple solution. Store a map of key -> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position. For example in the input array: $$[(3, 1), (2, 3), ...


Top 50 recent answers are included