Tag Archives: balanced

Data structure challenge: application

Posted on April 6, 2020 by Brent

I forgot to mention this in my previous post, but the thing which got me thinking about the predecessor problem in the first place was this competitive programming problem on Open Kattis: Profitable Pizzas I challenge you to go and … Continue reading →

Posted in data structures | Tagged , , , , , , , , , , , , , , | Leave a comment

Data structure challenge: solutions

Posted on April 6, 2020 by Brent

In my previous post I challenged you to find a way to keep track of a sequence of slots in such a way that we can quickly (in or better) either mark any empty slot as full, or find the … Continue reading →

Posted in data structures | Tagged , , , , , , , , , , , , | 3 Comments

Counting inversions via rank queries

Posted on December 18, 2019 by Brent

In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in time. As a reminder, given a sequence , an inversion is a pair of positions such that and … Continue reading →

Posted in haskell | Tagged , , , , , , , , , | 4 Comments

Adventures in enumerating balanced brackets

Posted on October 25, 2016 by Brent

Since I’ve been coaching my school’s ACM ICPC programming team, I’ve been spending a bit of time solving programming contest problems, partly to stay sharp and be able to coach them better, but also just for fun. I recently solved … Continue reading →

Posted in combinatorics, haskell | Tagged , , , | 4 Comments