algorithms

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

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.