bogdan.cebere
BAN USERO(N) with a deque
- bogdan.cebere January 02, 2011yes, you're right. actually the solution is very wrong.thanks for your counterexample.I think we actually might need the minimum number of complete subgraphs(because for a correct subset I want all nodes to be connected to each other).
- bogdan.cebere December 26, 2010First, for finding the components you must run a DFS. Second, your solution has worse complexity(kind of O(2^N * N*N)).
- bogdan.cebere December 25, 2010I don't think it's possible to have (a1,a2,a3) a valid subset and (a1,a2) an exclusion rule..
- bogdan.cebere December 25, 2010We can imagine the set {a1,a2,a3,..} like a graph where initially all nodes are connected with each other.This means that initially this is a complete graph. Now we check the exclusion set, and for all 2 nodes in the same exclusion set, we remove the edge that connects them.Now, the remaining graph is full with nodes that are connected only and only if they can be in the same graph. Now, in order to find a valid subset, we can run a Depth First search to find all connected components.Every connected component will be a valid subset according to the way we created the graph. Now, for any of this subsets, we must generate the subsets to find all the solutions. Final complexity O(2^N). I think this solution is more interesting than raw backtracking.
- bogdan.cebere December 24, 2010O(N)
- bogdan.cebere November 12, 2010External sort
- bogdan.cebere November 09, 2010Actually, a trie could work here if we put the pattern in it. But it isn't a true trie, it's more like a finite automata, to be useful.And this idea is very good for multiple patterns.For details, search for Aho-Corasick algorithm. For a single pattern, it's the same with KMP, but it's power comes with multiple patterns.So, with single patterns KMP it is the best, for multiple patterns, a trie constructed with Aho-Corasick algorithm will do the job.
- bogdan.cebere November 09, 2010You must find all the occurrences of the pattern in the text.This means that you must create a trie of suffixes of the text to use it right.And the complexity in this case is O(N^2), with N the length of the text.KMP is much more simpler to implement and with a better complexity.
- bogdan.cebere November 08, 2010can you hint how it can be done in O(N)? I thought that segment trees could work, but I don't how..
- bogdan.cebere November 01, 2010Suppose A is the original vector, N it's length and deque the vector that acts like a deque. Initially back = -1 and front = 0.In the deque vector we keep the positions possible for the answer in the current subarray of length K. First we pop values front the back of the deque as long as the value at the position deque[back] is greater than the one at the position i. After we check is i - deque[front] is less or equal than K.If it isn't, it means that the valuw at deque[front] isn't useful anymore because it is too far from to current position. Finally, if we alredy seen k numbers, it means we can start to get minimums, whick will always be stored in deque[front]. I hope it's clear
for(int i = 1 ; i <= N ; i++)
{
while(front<=back && a[i]<=a[deque[back]]) back--;
deque[++back]=i;
if(deque[front] == i-K) front++;
if(i >= K) printf("%d\n",a[deque[front]]);
}
This can be done easily using a deque.We loop through the array, and at the same time we keep a deque with the minimums.Always, the front of the deque will be the minimum of the current subarray of length k.At a new value, while the last value in the deque is greater than the new one, we pop it.So it the deque will remain only the smallest values. If the current value and the beginning of the deque have indexes at a distance greater than k in the array, we pop from the beginning of the deque.At last, if the current index is greater than k, we can return the front of the deque as the samllest value in the current subarray of length k.Time complexity O(N) and space O(N).
- bogdan.cebere October 30, 2010Consider the array 1,2,3,100.
In this case the answer is 100 and not 1 * 4(the length).
It can be done in O(N^2), looping through all the possible lengths, and for a certain length using a deque to find out the minimum for every subarray of current length.But for sure it can be done better.
- bogdan.cebere October 30, 2010We can do a binary search, and at each step we verify if the current number has duplicate.If no, we're done,else we check if t he duplicate is in the left of the current number or in the right .If it is in the left, and at left of current number there are an even number of elements, then we continue searching at left, of if at the right of current number there are an odd number of elements, we continue in the right with the binary search.The same way we can think if the duplicate is in the right of the current number. The time complexity is O(logN) and space O(N).
- bogdan.cebere October 30, 2010you could do it with a hashtable.
- bogdan.cebere October 27, 20102* 0 + 1 = 2 ?
- bogdan.cebere October 27, 2010It doesn't matter.It isn't a binary search tree.
- bogdan.cebere October 24, 2010Supose S is the array of integers, N the length and sum the current sum.
Let best be the solution at current step.We keep in x and y the limit of the best array
Initally,best = -INF and sum = 0.
Then
for(i = 0 ;i < N ; ++i)
{
if(sum <= 0) {sum = S[i] ; idx = i; }
else sum += S[i];
if(best < sum) {best = sum;x = idx ; y = i;}
The solution will be the subarray [x,y]. Complexity O(N) time O(1) memory and one loop.
- bogdan.cebere October 24, 2010Knuth-Morris-Pratt algorithm.
- bogdan.cebere October 24, 2010We can do this by marking each node with 0 or 1.The first one we mark with 1, then a node in his list of neighbours with 0, then a neighbour of the neighbour with 1 and so until we mark all the nodes(and return true) or we arrive in a node that is 0 and we want to mark it with 1 or viceversa (and we return false).
- bogdan.cebere October 20, 2010We can do this using the number of bits equal to 1 of a number. If S has N elements and t = 0, we can loop to t = (1 << N) - 1 and at every step we check on which positions in t the bits are 1.Using the position, we show the element which is on that position in the set.For example:
S = {a,b}
t = 0 the bits are 00. We output {}
t = 1 the bits are 01. we output {b}
t = 2 the bits are 10. we output {a}
t = 3 the bits are 11. we output {a,b}
t = 4 > (1 << 2) - 1 . we stop
Let A be the array and T = 0.
While A[T] <= A[T + 1] we increase T be one unit.Doing so , we find the longest increasing sequence from the start of the array.
Now, let P = T + 1. The idea is to find if after A[T] are elements smaller than it.
So , while(P < A.length && T >= 0) if(A[P] < A[T]) --T; else ++P;
After these operations, T will be actually n1, because we know that A[1..T] is increasing(from first step) and there is no element in the array smaller than A[T] after position T.
We use the same idea to find the longest increasing array that has A[A.length - 1].
To do so, let T2 = A.length - 1.While A[T2] >= A[T2 - 1] --T2.
Now we must find if in the rest of the array is a bigger element than the one in the A[T2]. We could go until position T found previously, and if there is a P so A[P] >= A[T2] we increase T2.Finally T2 will actually be n2. Time complexity O(N) and space complexity O(1). There are other solutions in O(N logN) time and O(1) space using sorting or O(N log N) time and O(N) space using heaps.
We could do with a bucket sort. We use a vector of 255 elements , where every element is a list.Now, we put every IP address is this list after it's last 8 bits.Now we have the array sorted after the last 8 bits. We repeat the step with the next 8 bits from the back, applying the sorting now for the new array(sorted after the la 8 bits). We do like this 4 times(for every group of 8 bits). The sorting will take O(N) time.
- bogdan.cebere January 23, 2011