From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <asmadeus77@gmail.com>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: *
X-Spam-Status: No, score=1.0 required=5.0 tests=AWL,SPF_NEUTRAL 
	autolearn=disabled version=3.1.3
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by yquem.inria.fr (Postfix) with ESMTP id 010BEBC6B
	for <caml-list@yquem.inria.fr>; Tue,  6 Nov 2007 15:46:09 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgAAAMcMMEdA6aq7nmdsb2JhbACOfwEBBwQGERg
X-IronPort-AV: E=Sophos;i="4.21,378,1188770400"; 
   d="scan'208";a="18996409"
Received: from rn-out-0910.google.com (HELO rn-out-0102.google.com) ([64.233.170.187])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 06 Nov 2007 15:46:07 +0100
Received: by rn-out-0102.google.com with SMTP id s46so803010rnb
        for <caml-list@yquem.inria.fr>; Tue, 06 Nov 2007 06:46:03 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=beta;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        bh=InTu+g3txi8H8PQxCA0VAlfNdjetPy3mn8StCzwLhnc=;
        b=AyubBlKFVSvWqCoV8cFIofsmT/GYOb4WouZ19LZKf2D23mTC3vVGirlX95kM/nLErGgEGb2KqFeJDOfaEBoFFoe2fARsdsaGE3I9jvzbTWofYIE2G6DJLriqU1VeS2sEhmg5ty3gixpgbTMFas61wlERoBR2zLf/fsB1YfTKfUI=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=Mr8wCW8ZN3Pfx8PEMISnT0GBWuzck36hGlvHAyblgy0GWjX+FNFw3Nl5mLmdHygwBPArdg0Ombsx4SYdx0vM5NbFcnSFURsLQWdh3chqb/yl59yrFIu3apDq6yNWq4G0xV2RnFtp/HeUklpeypKwxVlOP1nXPkRg2g5TADN8Ju4=
Received: by 10.142.44.11 with SMTP id r11mr1533584wfr.1194360362239;
        Tue, 06 Nov 2007 06:46:02 -0800 (PST)
Received: by 10.65.139.16 with HTTP; Tue, 6 Nov 2007 06:46:02 -0800 (PST)
Message-ID: <b79ece760711060646i639db37cubb57698b8a82d820@mail.gmail.com>
Date: Tue, 6 Nov 2007 15:46:02 +0100
From: "Dominique Martinet" <asmadeus77@gmail.com>
To: "Loup Vaillant" <loup.vaillant@gmail.com>
Subject: Re: [Caml-list] The GC is not collecting... my mistake?
Cc: "Caml mailing list" <caml-list@yquem.inria.fr>
In-Reply-To: <6f9f8f4a0711060451g1219a880gd711d997043b016@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <6f9f8f4a0711060451g1219a880gd711d997043b016@mail.gmail.com>
X-Spam: no; 0.00; martinet:01 iterative:01 ulimit:01 scanf:01 scanf:01 printf:01 printf:01 rec:01 caml-list:01 computation:01 int:01 int:01 usable:02 programming:03 heh:03 

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