page =
url = https://byorgey.wordpress.com
blog :: brent -> [string]
Yesterday morning I competed in Educational Round 114 on codeforces.com , using only Haskell. It is a somewhat annoying since it does not support as many Haskell libraries as Open Kattis ( e.g. no
unordered-containers
split
, or
vector
); but on the other hand, a lot of really top competitive programmers are active there, and I enjoy occasionally participating in a timed contest like this when I am able.
WARNING : here be spoilers! Stop reading now if you’d like to try solving the contest problems yourself. (However, Codeforces has an editorial with explanations and solutions already posted, so I’m not giving anything away that isn’t already public.) I’m going to post my (unedited) code for each problem, but without all the imports and
extensions and whatnot; hopefully that stuff should be easy to infer.
Problem A – Regular Bracket Sequences
In this problem , we are given a number and asked to produce any distinct balanced bracket sequences of length . I immediately just coded up a simple recursive function to generate all possible bracket sequences of length , and then called
take n
on it. Thanks to laziness this works great. I missed that there is an even simpler solution: just generate the list
()()()()...
(())()()...
((()))()...
, i.e. where the th bracket sequence starts with nested pairs of brackets followed by singleton pairs. However, I solved it in only four minutes anyway so it didn’t really matter!
readB = C.unpack >>> read main = C.interact $ C.lines >>> drop 1 >>> concatMap ( readB >>> solve ) >>> C.unlines bracketSeqs 0 = [ "" ] bracketSeqs n = [ "(" ++ s1 ++ ")" ++ s2 | k <- [ 0 .. n - 1 ] , s1 <- bracketSeqs k , s2 <- bracketSeqs ( n - k - 1 ) ] solve n = map C.pack . take n $ bracketSeqs n
Problem B – Combinatorics Homework
In this problem , we are given numbers , , , and , and asked whether it is possible to create a string of
A
’s,
B
’s, and
C
’s, such that there are exactly adjacent pairs of equal letters. This problem requires doing a little bit of combinatorial analysis to come up with a simple Boolean expression in terms of , , , and ; there’s not much to say about it from a Haskell point of view. You can refer to the editorial posted on Codeforces if you want to understand the solution.
readB = C.unpack >>> read main = C.interact $ C.lines >>> drop 1 >>> map ( C.words >>> map readB >>> solve >>> bool "NO" "YES" ) >>> C.unlines solve :: [ Int ] -> Bool solve [ a , b , c , m ] = a + b + c - m >= 3 && m >= z - ( x + y ) - 1 where [ x , y , z ] = sort [ a , b , c ]
Problem C – Slay the Dragon
This problem was super annoying and I still haven’t solved it. The idea is that you have a bunch of “heroes”, each with a numeric strength, and there is a dragon described by two numbers: its attack level and its defense level. You have to pick one hero to fight the dragon, whose strength must be greater than or equal to the dragon’s defense; all the rest of the heroes will stay behind to defend your castle, and their combined strength must be greater than the dragon’s attack. This might not be possible, of course, so you can first spend money to level up any of your heroes, at a rate of one coin per strength point; the task is to find the minimum amount of money you must spend.
The problem hinges on doing some case analysis. It took me a good while to come up with something that I think is correct. I spent too long trying to solve it just by thinking hard; I really should have tried formal program derivation much earlier. It’s easy to write down a formal specification of the correct answer which involves looping over every hero and taking a minimum, and this can be manipulated into a form that doesn’t need to do any looping.
In the end it comes down to (for example) finding the hero with the smallest strength greater than or equal to the dragon’s defense, and the hero with the largest strength less than or equal to it (though one of these may not exist). The intended way to solve the problem is to sort the heroes by strength and use binary search; instead, I put all the heroes in an
IntSet
and used the lookupGE and lookupLE functions .
However, besides my floundering around getting the case analysis wrong at first, I got tripped up by two other things: first, it turns out that on the Codeforces judging hardware,
is only 32 bits, which is not big enough for this problem! I know this because my code was failing on the third test case, and when I changed it to use
Int64
(which means I also had to switch to
Data.Set
Data.IntSet
), it failed on the sixth test case instead. The other problem is that my code was too slow: in fact, it timed out on the sixth test case rather than getting it wrong per se. I guess
just have too much overhead.
Anyway, here is my code, which I think is correct, but is too slow.
data TC = TC { heroes :: ! [ Int64 ] , dragons :: ! [ Dragon ] } data Dragon = Dragon { defense :: ! Int64 , attack :: ! Int64 } main = C.interact $ runScanner tc >>> solve >>> map ( show >>> C.pack ) >>> C.unlines tc :: Scanner TC tc = do hs <- numberOf int64 ds <- numberOf ( Dragon <$> int64 <*> int64 ) return $ TC hs ds solve :: TC -> [ Int64 ] solve ( TC hs ds ) = map fight ds where heroSet = S.fromList hs total = foldl' ( + ) 0 hs fight ( Dragon df atk ) = minimum $ [ max 0 ( atk - ( total - hero ) ) | Just hero <- [ mheroGE ] ] ++ [ df - hero + max 0 ( atk - ( total - hero ) ) | Just hero <- [ mheroLE ] ] where mheroGE = S.lookupGE df heroSet mheroLE = S.lookupLE df heroSet
I’d like to come back to this later. Using something like
to sort and then do binary search on the heroes would probably be faster, but
is not supported on Codeforces. I’ll probably end up manually implementing binary search on top of something like
Data.Array.Unboxed
. Doing a binary search on an array also means we can get away with doing only a single search, since the two heroes we are looking for must be right next to each other in the array.
Edited to add : I tried creating an unboxed array and implementing my own binary search over it; however, my solution is still too slow. At this point I think the problem is the sorting. Instead of calling
sort
on the list of heroes, we probably need to implement our own quicksort or something like that over a mutable array. That doesn’t really sound like much fun so I’m probably going to forget about it for now.
Problem D – The Strongest Build
In this problem , we consider a set of -tuples, where the value for each slot in a tuple is chosen from among a list of possible values unique to that slot (the values for a slot are given to us in sorted order). For example, perhaps the first slot has the possible values , the second slot has possible values , and the third slot has possible values . In this case there would be possible tuples, ranging from up to . We are also given a list of forbidden tuples, and then asked to find a non-forbidden tuple with the largest possible sum.
If the list of slot options is represented as a list of lists, with the first list representing the choices for the first slot, and so on, then we could use
sequence
to turn this into the list of all possible tuples. Hence, a naive solution could look like this:
solve :: Set [ Int ] -> [ [ Int ] ] -> [ Int ] solve forbidden = head . filter ( `S.notMember` forbidden ) . sortOn sum . sequence
Of course, this is much too slow. The problem is that although (the size of the tuples) is limited to at most , there can be up to choices for each slot (the choices themselves can be up to ). The list of all possible tuples could thus be truly enormous; in theory, there could be up to ), and generating then sorting them all is out of the question.
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 solution must either be the top element of the lattice (the tuple with the maximum possible value for every slot), OR the child of one of the forbidden tuples (it is easy to see this by contradiction—any tuple which is not the child of a banned 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 for each one, and take the maximum.
However, that’s not how I solved it! I started thinking from the naive solution above, and wondered whether there is a way to do
sortOn 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). 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 really want.
I’m quite pleased that this worked, though it’s probably an instance of me making things too complicated.
data TC = TC { slots :: [ [ Choice ] ] , banned :: [ [ Int ] ] } tc = do n <- int TC <$> ( n >< ( zipWith Choice [ 1 .. ] <$> numberOf int ) ) <*> numberOf ( n >< int ) main = C.interact $ runScanner tc >>> solve >>> map ( show >>> C.pack ) >>> C.unwords solve :: TC -> [ Int ] solve TC { .. } = choices . fromJust $ find ( ( `S.notMember` bannedSet ) . choices ) bs where bannedSet = S.fromList banned revSlots = map reverse slots bs = builds revSlots data Choice = Choice { index :: ! Int , value :: ! Int } data Build = Build { strength :: ! Int , choices :: [ Int ] } deriving ( Eq , Show , Ord ) singletonBuild :: Choice -> Build singletonBuild ( Choice i v ) = Build v [ i ] mkBuild xs = Build ( sum xs ) xs -- Pre: all input lists are sorted descending. -- All possible builds, sorted in descending order of strength. builds :: [ [ Choice ] ] -> [ Build ] builds [] = [] builds ( i : is ) = chooseFrom i ( builds is ) chooseFrom :: [ Choice ] -> [ Build ] -> [ Build ] chooseFrom [] _ = [] chooseFrom xs [] = map singletonBuild xs chooseFrom ( x : xs ) ( b : bs ) = addToBuild x b : mergeBuilds ( map ( addToBuild x ) bs ) ( chooseFrom xs ( b : bs ) ) addToBuild :: Choice -> Build -> Build addToBuild ( Choice i v ) ( Build s xs ) = Build ( v + s ) ( i : xs ) mergeBuilds xs [] = xs mergeBuilds [] ys = ys mergeBuilds ( x : xs ) ( y : ys ) = case compare ( strength x ) ( strength y ) of GT -> x : mergeBuilds xs ( y : ys ) _ -> y : mergeBuilds ( x : xs ) ys
Problems E and F
I didn’t even get to these problems during the contest; I spent too long fighting with problem C and implementing my overly complicated solution to problem D. I might attempt to solve them in Haskell too; if I do, I’ll write about them in another blog post!
Posted in competitive programming , haskell | Tagged Codeforces , solutions | Leave a comment
Competitive programming in Haskell: Codeforces Educational Round 114