thoughts.txt (1368B)
1 - n keys 2 - each giving a_1, ..., a_n units of happiness 3 - triad 4 - starting from x is: 5 - x, x+2, x+4 6 - happiness is a_{x} + a_{x+2} - a_{x+4} 7 - how many pairs of triads such that 8 - a pair doesn't share any keys 9 - same amount of audience love 10 11 - 10_000 test cases 12 - n <= 200_000 13 - -10_000 <= a_i <= 10_000 14 - sum of n over all test cases <= 200_000 15 16 --- 17 18 - 200_000 values at most 19 - with large range 20 - thoughts here: 21 - we can just compute each of the possible triads because they are constrained as a series 22 - we then have a set with lookups and sum the number of times we hit a value in the set 23 - constraint of relevance: 24 - they mustn't share any keys 25 26 --- 27 28 - idea: 29 - compute all pairs 30 - compute the sums and then creates sets of matches where we encode this as a list of indexes that start these triads 31 - we can then perform some basic match to compute intersections and such within groups 32 - is this too costly? assume there's a case where ~200_000 sums match, we then do a o(n^2) op to compare them all 33 - on insertions we could add the number of additional matches we get to some sum 34 - that seems better. 35 - so when inserting the first element we add none 36 - when inserting the second element we add 1 iff they are disjoint 37 - we then proceed as such.