We have an array of integers $a[]$, with each $|a[i]| \leq 10^{6}$, $size(a)\leq10^{5}$, and $a[i]-a[i-1]\leq100$.
Then we define the term range as a subarray $[x,y]$ of the array $a[]$, $x \lt y$.
We need to find total number of ranges that satisfy the property that for two given ranges $([x_{1},y_{1}]$ and $[x_{2},y_{2}])$ either one or more of the below conditions are true:
1) $(y_{1} – x_{1} \neq y_{2} – x_{2})$
2) $a[x_{1}+k] – a[x_{1}+k-1] \neq a[x_{2}+k] – a[x_{2}+k–1]$ for some $k \in \{1, 2, ... y_{1}-x_{1}\}$.
How can we visualize this problem? Is this related to some classical problem?
Asked By : Salena
Answered By : D.W.
I don't want to give away the solution -- I want you to have the chance to experience the pleasure of finding a nice solution on your own -- but I'll suggest a bunch of hints that might help:
To count the number of range-pairs that satisfy either 1) or 2), you could instead count the number of range-pairs that satisfy neither 1) nor 2) (and then adjust your answer appropriately). What would it mean for a range-pair to violate 1) and violate 2)? Try writing out the conditions. I think you might find that those conditions are easier to think about. When I suggest you write out the conditions, I really do mean it: write it down, in full, and then stare at the result for a while. I think you'll be able to find how this is related to another problem that is easier to state.
You might look at the first derivative of the array $a[]$. In other words, let the array $b[]$ be defined by $b[i] = a[i]-a[i-1]$ (so $size(b) = size(a)-1$). Now translate the conditions so that they refer to $b$ instead of $a$. Write down the result, simplify as much as possible, and stare at it. I think you'll find that helps you write down a cleaner version of the problem statement, which makes this problem look even cleaner and helps you see how this might be related to some other problem that is easier to restate. Hint: repeated substrings....
You might find it interesting and helpful to learn about algorithms for the longest common substring problem, the Rabin-Karp hash function, and rolling hash functions. Suffix trees may be helpful, too.
If you're still stuck, try counting the number of such range-pairs where the ranges are of length 1 (i.e., $y_1-x_1=y_2-x_2=1$). Can you do it? Now try counting the number of such range-pairs of length 2. How would you do that? Can you do it? Is there a simple way to think about what that's counting? Now how about the number of range-pairs of length 3. Once you've solved all three of those, does that give you any ideas for how to generalize? I'm not trying to suggest that this is literally the algorithm you should use (it's one possible algorithm, but you can build better ones), but that this will help you conceptualize what this is asking you to solve and it might help you think about the problem more clearly so that you can identify even better solutions.
Finally: You'll need to spend some significant time struggling with this problem on your own. Be prepared to have to try out many different ideas and have most of them go nowhere. Be persistent. Don't expect it's just going to magically come to you in 5 seconds. Solving these kinds of algorithm problems takes hard work and a lot of effort, so don't just assume it's not going to work before you put in that kind of effort.
Bottom line. I'm pretty sure this can be solved in $O(n\ell)$ time, where $n=size(a)$ and $\ell$ is the length of the longest repeated substring (and thus in $O(n \lg n)$ time on average, if the input string is random). Also I believe it should be possible to solve this in $O(n)$ worst-case running time, using sufficiently advanced algorithmics machinery (augmented suffix trees). Caveat: I haven't checked all the details carefully, so you should do that yourself.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/13190
0 comments:
Post a Comment
Let us know your responses and feedback