[Tutorial] Modified Kinetic Tournament (Used in FBHC Round 2)

Правка en2, от ekzhang, 2020-08-30 02:27:05

Background

During Facebook Hacker Cup Round 2 today, Problem D caught my attention. It reminded me of a particular data structure called a modified kinetic tournament, which is not very well known in this community. However, it offers an extremely clean and slick solution to the problem, in my opinion.

I first heard about this data structure from dragonslayerintraining, who described it (and possibly invented it?) in this Codeforces blog comment. Since the data structure is so interesting, I feel like it deserves a longer explanation, some template code, and more examples. That's why I am writing this blog post.

Modified Kinetic Tournaments

Briefly, the functionality of the data structure is a mix between a line container, i.e., "convex hull trick", and a segment tree.

Suppose that you have an array containing pairs of nonnegative integers, $$$A[i]$$$ and $$$B[i]$$$. You also have a global parameter $$$T$$$, corresponding to the "temperature" of the data structure. Your goal is to support the following queries on this data:

  • update(i, a, b): set $$$A[i] = \text a$$$ and $$$B[i] = \text b$$$
  • query(s, e): return $$$\displaystyle \min_{s \leq i \leq e} A[i] * T + B[i]$$$
  • heaten(new_temp): set $$$T = \text{new_temp}$$$
    • [precondition: new_temp >= current value of T]

(For simplicity, we set A[i] = 0 and B[i] = LLONG_MAX for uninitialized entries, which should not change the query results.)

This allows you to essentially do arbitrary lower convex hull queries on a collection of lines, as well as any contiguous subcollection of those lines. This is more powerful than standard convex hull tricks and related data structures (Li-Chao Segment Tree) for three reasons:

  • You can arbitrarily remove/edit lines, not just add them.
  • Dynamic access to any subinterval of lines, which lets you avoid costly merge small-to-large operations in some cases.
  • Easy to reason about and implement from scratch, unlike dynamic CHT.

The tradeoff is that you can only query sequential values (temperature is only allowed to increase) for amortization reasons, but this happens to be a fairly common case in many problems.

Here's the kicker. If you implement the data structure correctly, you get the following time complexities:

  • query: $$$O(\log n)$$$
  • update: $$$O(\log n)$$$
  • heaten: $$$O(\log^3 n)$$$ [amortized]

Implementation

How does it work? With normal kinetic tournaments, you essentially build a min segtree as usual, but you add a global priority queue that stores whenever a "contract" breaks. We can put this in the analogy of increasing temperature. For every node, you store the temperatures at which that node "melts", meaning that the minimum value changes from one child to the other. Then, you can just keep popping events from this priority queue as your data structure heats up.

Kinetic tournament overview

However, this unfortunately only gets you quadratic runtime, which isn't good enough, since you might end up with a single melting event for every intersection between a pair of lines. You need a "modification" to give you amortized logarithmic runtime. In every node of the segment tree, you store the minimum temperature at which any part of its subtree could melt. This fits in naturally with the segment tree definition.

To optimize the data structure, you do not recompute at every certificate failure. Instead, whenever the user calls heaten(), you batch all of the recompute operations and recursively rebuild only the parts of the segment tree that changed, once.

dragonslayerintraining gives a sketch of a potential analysis for this in his comment.

Code

You can find my implementation of a modified kinetic tournament here:

https://ekzlib.herokuapp.com/view/kinetic_tournament.cpp

It defines a single struct with template type (~100 LoC), which has a plug-and-play interface that you can use in your own solutions, and no global variable pollution. Example usage:

int N = 2;
kinetic_tournament<long long> kt(N);

kt.update(0, 2, 10);  // 2t + 10
kt.update(1, 4, 1);   // 4t + 1

kt.heaten(1);         // t = 1
kt.query(0, 0);       // => 2*1 + 10 = 12
kt.query(1, 1);       // => 4*1 + 1 = 5
kt.query(0, 1);       // => min(2*1 + 10, 4*1 + 1) = 5

kt.heaten(5);         // t = 5
kt.query(0, 0);       // => 2*5 + 10 = 20
kt.query(1, 1);       // => 4*5 + 1 = 21
kt.query(0, 1);       // => min(2*5 + 10, 4*5 + 1) = 20

I've verified this implementation on Problem D from Facebook Hacker Cup Round 2, titled "Log Drivin' Hirin'". In this problem, you can simply sort the queries and nodes in order of increasing "carelessness", and the kinetic tournament finishes the task. Full solution is available below. It runs in less than 5 seconds on the entire test input.

Code

Conclusion

I hope to see more of this interesting data structure pop up in competitive programming! Hopefully this explanatory blog post is useful for you, and please let me know if you find any errors.

Теги #kinetic, #data structure, #tutorial, #tournament, #convex hull trick, #line container

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский ekzhang 2022-12-26 04:28:05 16 Update to new, non-broken ekzlib URL
en4 Английский ekzhang 2020-08-30 05:39:08 306 Add note about potential alpha(n) factor
en3 Английский ekzhang 2020-08-30 03:47:30 1019 Fix some misunderstandings (thanks to dragonslayerintraining for comments)
en2 Английский ekzhang 2020-08-30 02:27:05 0 (published)
en1 Английский ekzhang 2020-08-30 02:26:42 11090 Initial revision (saved to drafts)