Re: [Caml-list] The GC is not collecting... my mistake?

["Dominique Martinet" <asmadeus77@gmail.com>]

Hello,
(It did pass, I typed all of what you see next, then though it wasn't
worth it since I didn't answer your question anyway. Well, since you
though that didn't work, I might as well send it :P)

I'm not used to your way of programming (with arrows and such), and
guessing you were the one subscribe as "loup", I assume you're
considering the first Banderole problem. (my answer not fitting the
second one, heh)

Here's what I did, and what seemed the most logical to me at that time
(a plain iterative "check everything" function ; the check being
tail-recursive and dropping as soon as there's a problem). The time
computation requirement was 1s, and I had at worst 0.23, so that's
still quite usable I guess. (Time complexity should be O(l*n) worst
case and space one would be O(n) as I write everything in an array.
(That's n and not l, which is much worse :P))

I had some time at the end and planned to try the second one, but with
l=100_000 and n=2_000_000 (worst possibe thing they could ask us to
do), my program took 30 seconds to compute, and I don't think it
respects the space one either :P (using ulimit -v 2000)

let scan_int () = Scanf.scanf " %d" (fun x->x)
let show_int x  = Printf.printf "%d\n" x

let _ =
  let longueur,nb_pics=Scanf.scanf " %d %d" (fun x y -> x,y)
  and compteur = ref 0 in
  let tab_hauteurs = Array.make nb_pics 0 in
  for i=0 to nb_pics - 1 do
    tab_hauteurs.(i) <- scan_int ()
  done;
  let rec check i decallage =
   if decallage < longueur
     then if tab_hauteurs.(i+decallage) <= tab_hauteurs.(i)
         then check i (decallage + 1)
         else false
     else tab_hauteurs.(i+decallage) = tab_hauteurs.(i)
  in
  for i=0 to nb_pics - longueur - 1 do
    if check i 0 then incr compteur
  done;
  show_int !compteur