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