Tag Info

Hot answers tagged algorithms

5

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). ...

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".

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{... 2 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 ... 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 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$... 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 ... 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 ... 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 ... 1 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 ... 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)\$.

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