Problem 465592 · hard · Phase 04 Non-Linear Data Structures

The Frequency Pool's k-th Clash

binary trie · subtree counts · order statistics · design · classes

A ground station keeps a pool of radio frequencies (non-negative integers; the same frequency may be in the pool several times). When a new transmitter with frequency x asks for a slot, the station ranks the pool by the clash value x XOR y of every stored copy y. Design FrequencyPool:

  • FrequencyPool() starts with an empty pool.
  • add(x) puts one more copy of x into the pool (returns None).
  • remove(x) takes one copy of x out and returns True, or returns False if x is not in the pool.
  • kth_clash(x, k) lists the clash values x ^ y of all copies in the pool, sorted ascending (duplicates kept), and returns the k-th one (k starts at 1). Return -1 if the pool holds fewer than k copies. The pool does not change.

Examples

ops:  ["FrequencyPool", "add", "add", "add", "add", "kth_clash", "kth_clash", "kth_clash", "remove", "remove", "kth_clash", "kth_clash"]
args: [[], [5], [1], [5], [12], [4, 1], [4, 3], [4, 4], [5], [7], [4, 3], [4, 1]]
Output: [None, None, None, None, None, 1, 5, 8, True, False, 8, 1]
Explanation: against 4 the clash values are 5^4 = 1, 1^4 = 5, 5^4 = 1, 12^4 = 8,
sorted [1, 1, 5, 8]. After removing one 5 they are [1, 5, 8].

Constraints

  • 0 <= x < 2**20, k >= 1
  • Up to 2 * 10**4 calls in total
  • Target: every call in about O(20) steps; sorting the clash values for each kth_clash is too slow

Goals

  • Keep a multiset of integers in a binary trie with a count on every node
  • Find the k-th smallest XOR against a query by choosing a child from counts at each bit
  • Support removal and report whether the value was present
Starting Python…