1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I don't understand the question at all. What are the inputs to the algorithm that's supposed to count the number of ranges? (Are $x_1,y_1,x_2,y_2$ inputs, i.e., fixed constants given to us?) Also, I get that you want to count the total number of ranges $[x,y]$ such that (foo-condition) holds; but I can't understand what (foo-condition) is. For one thing, your specification of the condition does not seem to depend upon $x$ or $y$ at all. That can't be right. Can you please edit the question to be more precise about which ranges $[x,y]$ satisfy the property and which ones do not? $\endgroup$ – D.W. Jul 10 '13 at 2:34
  • $\begingroup$ @D.W. the conditions are for a pair of ranges. We have to find total number of ranges such that every pair of such range, satisfies one of the two conditions. $\endgroup$ – Salena Jul 10 '13 at 2:37
  • $\begingroup$ If you counting the number of pairs $([x_1,y_1],[x_2,y_2])$ of ranges, then please edit the question to state that. Important: please incorporate all clarifications into the question itself, so that others don't need to read the set of comments. (You might want to read the FAQ for more information on how this site works. It is not a discussion forum; rather, it is intended for archival-quality questions and their answers.) $\endgroup$ – D.W. Jul 10 '13 at 2:42
  • $\begingroup$ Also: please edit the question to describe what you've tried and where you've gotten stuck. (It's expected that you try to solve your problem yourself before asking here. Site guidelines include explaining what you've tried and where you are stuck. You're more likely to get useful answers if you follow these site guidelines.) $\endgroup$ – D.W. Jul 10 '13 at 2:44
  • $\begingroup$ We are not counting the number of pairs. There will be a total of $n^2$ ranges. Now we need only those ranges which satisfy the above conditions, when compared to every other range. $\endgroup$ – Salena Jul 10 '13 at 2:46
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes I have come this far. But still counting all ranges would take O(n^2) atleast. or can it be done in lesser time? $\endgroup$ – Salena Jul 10 '13 at 2:40
  • $\begingroup$ How is the LCS relevant here? $\endgroup$ – Salena Jul 10 '13 at 2:42
  • $\begingroup$ Salena, you need to spend some more time thinking this through. You have concluded that counting all such ranges would take $\Theta(n^2)$ time at least, but that is not necessarily the case. Spend some time thinking this through and following my advice to write down the resulting conditions and thinking about the problem. Then, edit your question to explain how far you got and where you got stuck (e.g., why you think it'll take $\Theta(n^2)$ time). We're not going to solve your homework for you. $\endgroup$ – D.W. Jul 10 '13 at 2:45
  • $\begingroup$ the fourth point you added, still keeps it $n^2$ computations $\endgroup$ – Salena Jul 10 '13 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.