commit 8f79a0a319f855ae75a9009e4a81d6cbb6d8cde1
parent e317d9ccf349cb499917e69bd5244c02f5ecfdc6
Author: Andrew Laack <andrew@laack.co>
Date: Thu, 12 Nov 2026 10:52:23 -0600
Fold left for prefix sum + window calculation in ocaml
Diffstat:
3 files changed, 71 insertions(+), 0 deletions(-)
diff --git a/comp/fence/ex1.in b/comp/fence/ex1.in
@@ -0,0 +1,2 @@
+7 3
+1 2 6 1 1 7 1
diff --git a/comp/fence/main.ml b/comp/fence/main.ml
@@ -0,0 +1,38 @@
+let readInput () =
+ Scanf.scanf " %d %d" (fun a b -> (a,b))
+in
+
+let rec readList take =
+ if take <= 0 then []
+ else
+ let x = Scanf.scanf " %d" (fun a -> a)
+ in x :: readList (take-1)
+in
+
+let append ls input =
+ match ls with
+ | [] -> [input]
+ | h :: _ -> (h + input) :: ls
+in
+
+let prefixSum ls =
+ List.rev (List.fold_left append [0] ls)
+in
+
+let rec minSum i leftLs rightLs =
+ match rightLs with
+ | [] -> (max_int, 0)
+ | h :: t -> min (h - (List.hd leftLs), i) (minSum (i + 1) (List.tl leftLs) (List.tl rightLs))
+in
+
+(* their compiler is old as shit *)
+let rec drop n ls =
+ match ls with
+ | _ :: t when n > 0 -> drop (n - 1) t
+ | _ -> ls
+in
+
+let ll, take = readInput () in
+ let ls = readList ll in
+ let pre = prefixSum ls in
+ print_int (snd (minSum 1 pre (drop take pre))); print_newline ()
diff --git a/comp/fence/problem.txt b/comp/fence/problem.txt
@@ -0,0 +1,31 @@
+B. Fence
+time limit per test
+1 second
+memory limit per test
+256 megabytes
+
+There is a fence in front of Polycarpus's home. The fence consists of n planks of the same width which go one after another from left to right. The height of the i-th plank is hi meters, distinct planks can have distinct heights.
+Fence for n = 7 and h = [1, 2, 6, 1, 1, 7, 1]
+
+Polycarpus has bought a posh piano and is thinking about how to get it into the house. In order to carry out his plan, he needs to take exactly k consecutive planks from the fence. Higher planks are harder to tear off the fence, so Polycarpus wants to find such k consecutive planks that the sum of their heights is minimal possible.
+
+Write the program that finds the indexes of k consecutive planks with minimal total height. Pay attention, the fence is not around Polycarpus's home, it is in front of home (in other words, the fence isn't cyclic).
+Input
+
+The first line of the input contains integers n and k (1 ≤ n ≤ 1.5·105, 1 ≤ k ≤ n) — the number of planks in the fence and the width of the hole for the piano. The second line contains the sequence of integers h1, h2, ..., hn (1 ≤ hi ≤ 100), where hi is the height of the i-th plank of the fence.
+Output
+
+Print such integer j that the sum of the heights of planks j, j + 1, ..., j + k - 1 is the minimum possible. If there are multiple such j's, print any of them.
+
+---
+
+- n planks of the same width
+- planks can have distinct heights
+ - non-negative too :)
+- take k consecutive planks such that their height is minimal
+- two options:
+ - better:
+ - sliding window
+ - worse:
+ - prefix sum
+ - better for arbitrary sizes