You are given an array of integers. You have to find the shortest substring that contains only the elements from the interval [ A, B ]. Also, every integer from the interval [ A, B ] has to appear at least once in the substring. If there is no such substring output -1.
INPUT:
The first line contains three integers n, A and B (1 <= n <= 1.000.000, 1 <= A <= B <= 1.000.000.000). The following line contains n integers from the interval [1, 1.000.000.000] representing the array.
OUTPUT:
Output the length of such shortest substring, or -1 if there is none.
To be honest, it's a homework assignment and I just can't figure out how to solve it while keeping it's runtime <0.5 seconds
I'm supposed to do it in Pascal, but I'd be glad to receive the solution in any language.
Name:
Anonymous2010-02-28 15:08
inb4 Pascal sucks && underage b&
Name:
Anonymous2010-02-28 15:11
program fff;
var s:string[12];
begin
s:='Pascal sucks.'
writeln(s);
readln;
end.
Off the top of my head. Iterate over the array, storing substrings that are in the range. This could be done as a p-list alternating the beginnings and endings of the substrings, or you could make a record to store the two together. Then filter out the substrings that have a length (end-start) of less than B-A. If there are any substrings left, then you can do the annoying work of checking that each element in A->B is in the substring.
Name:
Anonymous2010-02-28 18:14
EXPERT LINEAR SOLUTION
(define (shortest-substring-length a b z)
(let* ((n (vector-length z))
(d (- b a -1))
(v (make-vector d 0)))
(let loop ((s 0) (i 0) (t 0) (m (+ n 1)))
(cond
((= t d)
(let* ((c (- (vector-ref z s) a))
(o (- (vector-ref v c) 1)))
(vector-set! v c o)
(loop (+ s 1) i (if (zero? o) (- t 1) t) (min (- i s) m))))
((= i n)
(if (= m (+ n 1)) -1 m))
(else
(let ((q (vector-ref z i)))
(if (<= a q b)
(let* ((c (- q a))
(o (vector-ref v c)))
(vector-set! v c (+ o 1))
(loop s (+ i 1) (if (zero? o) (+ t 1) t) m))
(begin
(vector-fill! v 0)
(loop (+ i 1) (+ i 1) 0 m)))))))))
(let* ((n (read))
(a (read))
(b (read))
(z (make-vector n)))
(do ((i 0 (+ i 1)))
((= i n) (display (shortest-substring-length a b z)) (newline))
(vector-set! z i (read))))
>>8
It's really hard to read that, but where is your check that each element between a and b is in your vector? All I see is that you are incrementing the appropriate vector entry. This alone would mean that you couldn't have a linear time solution.
Name:
Anonymous2010-02-28 19:26
Linear time for n? Or for what variable? I think you don't know what you want.
>>11
Of course. O(n) time, O(n+b-a) space. For the first, consider that one or both of s and i increase every iteration, they never decrease and s ≤ i ≤ n. For the second, see the calls to make-vector.
>>8
That would be my idea, too. Props for the implementation and for being completely worthless to >>1 unless he's got some serious reverse psychology going on.
To nitpick; the given code is O(n + b - a) in time too, since initializing v is Θ(b - a), but that's easily fixed in production code by an initial check for a + n > b.
Umm, guys, I really appreciate your effort, but I can't make any sense of >>8
I can understand Pascal/C++/Java/Javascript, and I'm pretty confident I could figure out C/PHP/Mathlab.
[HM50] Find a lower bound for the running time of a solution that assumes an infinite number of processing steps may be run in parallel.
Name:
Anonymous2010-03-01 8:10
>>14
Right. Worse, the same problem is in vector-fill!, which may be called n times. Fixed version:
(define (shortest-substring-length a b z)
(let* ((n (vector-length z))
(d (- b a -1))
(v (make-vector d)))
(define (f x p)
(do ((q x (+ q 1))) ((or (>= q n) (eq? p (<= a (vector-ref z q) b))) q)))
(let loop ((s 0) (i 0) (k 0) (t 0) (m (+ n 1)))
(cond
((= t d)
(let* ((c (- (vector-ref z s) a)) (o (- (vector-ref v c) 1)))
(vector-set! v c o)
(loop (+ s 1) i k (if (zero? o) (- t 1) t) (min (- i s) m))))
((= i n)
(if (> m n) -1 m))
((< i k)
(let* ((c (- (vector-ref z i) a)) (o (vector-ref v c)))
(vector-set! v c (+ o 1))
(loop s (+ i 1) k (if (zero? o) (+ t 1) t) m)))
(else
(let* ((s (f k #t)) (k (f s #f)))
(if (< (- k s) d)
(loop k k k 0 m)
(begin
(vector-fill! v 0)
(loop s s k 0 m)))))))))
(let* ((n (read)) (a (read)) (b (read)) (z (make-vector n)))
(do ((i 0 (+ i 1)))
((= i n) (display (shortest-substring-length a b z)) (newline))
(vector-set! z i (read))))