algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.ml (4789B)


      1 (*
      2 - problem 
      3     - producing snowmen
      4     - three snowballs per
      5         - leg ball must be strictly larger than the torso
      6         - torso must be strictly larger than the head
      7         - a,b,c s.t. a < b < c for the balls
      8     - three conveyors with n snowballs each
      9     - first  is a_1, a_2, ..., a_n
     10     - second is b_1, b_2, ..., b_n
     11     - third  is c_1, c_2, ..., c_n
     12     - cyclic conveyors
     13     - i,j,k where 1 <= i,j,k <= n
     14         - this specifies which balls on each conveyor the production starts from
     15     - assembling goes as follows
     16         - first snowman has head size a_i, torso of b_j, legs of size c_k
     17         - second will have a_{i+1}, b_{j+1}, c_{k+1}
     18         - so on
     19         - last will be:
     20             - a_{i+n-1}, b_{j+n-1}, c_{k+n-1} 
     21     - i,j,k must be chosen to make the snowmen stable
     22     - return number of suitable selections for i,j,k
     23 
     24 - thoughts
     25     - brute force approach is to just check each selection of i,j,k
     26         - there are O(n^3) options for this
     27         - at most 5000 elements
     28             - 5000 ** 3 = 125_000_000_000
     29                 - too slow
     30             - 5000 ** 2 = 4_000_000
     31                 - this is probably ~ our target
     32     - what else can we search over?
     33         - selections of base, torso, heads
     34             - there are compression opportunities here (I think)
     35                 - basically, we can find the O(n^2) selections of base and torsos
     36                 - we then find the O(n^2) selections of torsos and heads
     37                 - we then we then match on valid base/torso pairs, joined on torso/head combinations
     38                 - concretely, we'd create 2 seperate 5000x5000 grids representing combinations
     39                 - this feels off, not sure why
     40                     - probably because I haven't entirely solved the problem of constraining the starting points to sane options
     41     - who can we dp on this?
     42         - we're trying to count selections that work
     43             - can we just dp on selections?
     44                 - not really because selections aren't preserved across selections
     45                     - that's not true, if we just offset each selection they are so kinda?
     46                         - this would functionaly change the dimensions of this problem
     47                             - instead we care about relative offsets
     48                                 - that's not obviously better asymptotically
     49                                 - actually, this drops this down by one factor of n because each selection has n offsets that match the current one
     50                                     - generally, if we hit a state again, we can return the overall finding of that selection from the prior step because the current is the same
     51                                     - actually we could constrain our selections with this knowledge and multiply by n at the end
     52                             - how would this look?
     53                                 - we can put the first selection at 0 and vary the other two. this gives us offsets onto them, and we notice that moving the top element is just the same as moving everything by a shift
     54 
     55 - fleshed out
     56     - set i = 0
     57     - set res = 0
     58     - for j in range(n):
     59         - for k in range(n):
     60             - if valid i,j,k : res += 1 else continue
     61     - multiply final result by n because i can be 0,1,...,n-1 and still have the same cyclic property
     62 
     63 - can the idea above be memoized?
     64     - sort of. i can be safe relative to j and k but this isn't fool-proof
     65         - we only compare j and k values in unique ways
     66 
     67 *)
     68 
     69 let read_int () = Scanf.scanf " %d" (fun x -> x) in
     70 
     71 let readArr length =
     72   let arr = Array.make length 0 in
     73 
     74   let rec load i =
     75     if i = length then ()
     76     else
     77       let () = arr.(i) <- read_int () in
     78       load (i + 1)
     79   in
     80 
     81   let () = load 0 in
     82   arr
     83 in
     84 
     85 let isValid x y j =
     86   let rec loopStep offset =
     87     if offset = Array.length x then true
     88     else if x.(offset) >= y.((offset + j) mod Array.length x) then false
     89     else loopStep (offset + 1)
     90   in
     91   loopStep 0
     92 in
     93 
     94 let solve a b c =
     95   let n = Array.length a in
     96   let rec loopK k count =
     97     if k = n then count
     98     else
     99       let count = if isValid b c k then count + 1 else count in
    100       loopK (k + 1) count
    101   in
    102   let rec loopJ j count =
    103     if j = n then count
    104     else
    105       let count = if isValid a b j then count + 1 else count in
    106       loopJ (j + 1) count
    107   in
    108   Int64.mul (Int64.mul (Int64.of_int (loopJ 0 0)) (Int64.of_int (loopK 0 0))) (Int64.of_int n)
    109 in
    110 
    111 let rec handleTestCases rem =
    112   if rem > 0 then (
    113     let ln = read_int () in
    114     let a = readArr ln in
    115     let b = readArr ln in
    116     let c = readArr ln in
    117     print_string (Int64.to_string (solve a b c));
    118     print_newline ();
    119     handleTestCases (rem - 1))
    120   else ()
    121 in
    122 
    123 let testCases = read_int () in
    124 handleTestCases testCases