page = blog :: brent -> [string]

url = https://byorgey.wordpress.com analysed @ 2021-09-22 16:24 UTC

Yesterday morning I competed in Educational Round 114 on codeforces.com , using only Haskell. It is somewhat annoying since it does not support as many Haskell libraries as Open Kattis ( e.g. no
solve :: Set [ Int ] -> [ [ Int ] ] -> [ Int ] solve forbidden = head . filter ( `S.notMember` forbidden ) . sortOn ( Down . sum ) . sequence
We can think of the tuples as forming a lattice, where the children of a tuple are all the tuples obtained by downgrading exactly one slot of to the next smaller choice. Then the intended solution is to realize that the largest non-forbidden tuple must either be the top element of the lattice (the tuple with the maximum possible value for every slot), OR a child of one of the forbidden tuples (it is easy to see this by contradiction—any tuple which is not the child of a forbidden tuple has at least one parent which has a greater total value). So we can just iterate over all the forbidden tuples (there are at most ), generate all possible children (at most 10) for each one, and take the maximum.
sortOn (Down . sum) . sequence
more efficiently, by interleaving the sorting and the generation. If it can be done lazily enough, then we could just search through the beginning of the generated ordered list of tuples for the first non-forbidden one, without having to actually generate the entire list. Indeed, this reminded me very much of Richard Bird’s implementation of the Sieve of Eratosthenes (see p. 11 of that PDF). The basic idea is to make a function which takes a list of choices for a slot, and a (recursively generated) list of tuples sorted by decreasing sum, and combines each choice with every tuple, merging the results so they are still sorted. However, the key is that when combining the best possible choice for the slot with the largest tuple in the list, we can just immediately return the resulting tuple as the first (best) tuple in the output list, without needing to involve it in any merging operation. This affords just enough laziness to get the whole thing off the ground. I’m not going to explain it in more detail than that; you can study the code below if you like.
I’m quite pleased that this worked, though it’s definitely an instance of me making things more complicated than necessary.