A Fenwick bound week

Codeforces was quite active this week with two Division 1 rounds. The 462nd one took place on Wednesday (problems, results, top 5 on the left, analysis). Um_nik was the only one able to solve all problems, submitting one in the last minute — but he would've won without that one anyway. Congratulations on the great performance!

Round 463 took place on Thursday (problems, results, top 5 on the left, analysis). It was Radewoosh's turn to be the only competitor to solve all problems, with 7 minutes to spare this time. Well done!

He will be representing his university in the upcoming ICPC World Finals in Beijing, along with a few others that you can see in the screenshots on the left, so the competition there promises to be very interesting :)

Finally, the Open Cup Grand Prix of Gomel on Sunday provided another glimpse into full team performances (results, top 5 on the left). Moscow SU team Red Panda has found the winning ways again, this time thanks to being the only team to solve problem I — and doing it in the beginning of the third hour of the contest, which is quite unusual for a problem with only one solver. Congratulations!

Last week, I have mentioned a data structure problem from the Open Cup. n people are coming to lunch and forming a queue. The people are split into disjoint groups. When i-th person comes to the lunch, if there's nobody from their group c_i already in the queue, they stand at the back of the queue. When there is somebody from their group already in the queue, they can also stand next to any such person (directly before or after), but only if they would be cutting in front of at most a_i people by doing so. If they have multiple positions where they can join the queue according to the above restrictions, they always pick the front-most one. Initially the queue is empty. Given the values of c_i and a_i in the order the people come to lunch, how will the final queue look like?

One could immediately start thinking about standard approaches applicable in this problem. The fact that we need to be able to run a query against the last a_i people in the queue suggests that we should probably use a balanced tree that supports quick splitting, like a treap, and maintain the size of the subtree plus some additional structures necessary to answer queries in each node. This approach can probably be made to work, but the nice thing about the problem is that we can obtain a much easier to code solution.

Since every person only ever joins the queue either in last position, or next to a person from their group, if we maintain the queue as a list of segments of people from the same group, in other words as a list of (group, counter) pairs, then the only operations we need to support is to increment a counter and to add a new group to the end of the list. Now in order to find a place for the next person we need to find the set of groups corresponding to the last a_i+1 people, and then find the first group of the required type in that set.

In order to find the boundary on the group level, we need to be able to find the largest prefix for which the sum of counters does not exceed a given value. This can be done in O(logn) by maintaining the counters in a Fenwick tree, I will give more details below.

And in order to find the first group of the required kind after the given one, we can simply maintain a vector of indices of groups for each kind. Since we only ever create new groups at the end, these indices never change, and a simple binary search can find the first group of the given kind after a given index.

Finally, after we know what happens with groups we know at which position does each person enter the queue, but we still need to output the final order. This can be done using the same Fenwick tree with "largest prefix with sum not exceeding x" operation we already used: we go from the end and maintain the free spots in the Fenwick tree.

So instead of a balanced tree with extra information in nodes, we've managed to get by using two very easy to code data structures: a Fenwick tree, and a vector. The solution is O(nlogn), and the constant hidden in O() is also really small.

This solution used the following non-standard operation on a Fenwick tree: find the largest prefix with sum not exceeding x. A naive implementation using binary search and Fenwick prefix sums would give O(log²n) complexity, which would most likely still be fast enough to get the problem accepted. However, tgehr has pointed out to me that the standard Fenwick tree allows an extremely simple O(logn) way to answer this question.

Suppose our Fenwick tree has n elements, and k is the largest power of 2 not exceeding n. The (2^k-1)-th element of the Fenwick tree array contains the sum s of elements on the segment [0;2^k-1], so by comparing x with just this number we know if our answer is below or above 2^k. Let's suppose it's above 2^k. Then we notice that (2^k+2^k-1-1)-th element of the Fenwick tree array contains the sum of elements on the segment [2^k;2^k+2^k-1-1], so by comparing x-s with just this number we know if our answer is below or above 2^k+2^k-1. We continue traversing the powers of two in the same manner, and it turns out that the standard Fenwick tree stores exactly the sums needed to execute this binary search! Here's the actual code:

private int upperBound(int[] f, int x) {
    int res = 0;
    int max = Integer.numberOfTrailingZeros(
        Integer.highestOneBit(f.length));
    for (int k = max; k >= 0; --k) {
        int p = res + (1 << k) - 1;
        if (p < f.length && f[p] <= x) {
            x -= f[p];
            res += 1 << k;
        }
    }
    return res;
}

Thanks for reading, and check back next week.