PrevNext
Rare
 0/4

Fracturing Search

Author: Benjamin Qi

Prerequisites

A simple solution to "Robotic Cow Herd" that generalizes.

General Outline

Problem

Suppose that you have a rooted tree where each vertex ii has a value viv_i. Also, if ii is not the root then ii has a parent pip_i satisfying vpiviv_{p_i} \le v_i. Given that each vertex has at most DD children, find the KK smallest values in the tree.

Approaches

Approach 1: Use a priority queue initially containing only the root. At each step, extract the vertex with smallest value from the priority queue and insert all of its children into the queue. Since we insert O(KD)O(KD) vertices in the priority queue, this runs in O(KDlog(KD))O(KD\log (KD)) time. You can think of this as Dijkstra on a tree.

Approach 2: Suppose that we know that the KK-th smallest value is an integer in the range [0,A][0,A]. Then for any x[0,A]x\in [0,A] we can check whether there are less than KK values in the tree less than or equal to xx in O(KD)O(KD) time with a simple DFS that breaks once you find KK values. This approach runs in O(KDlogA)O(KD\log A) time.

We'll focus on the first approach.

Optional: A Faster Solution

There are ways to do this in O(K)O(K) time for a binary tree if you don't need to return the values in sorted order (see here).

Generalizing

Suppose that you want to find the KK objects with the smallest values in some (potentially very large) search space.

  • First, we need to impose a tree structure satisfying the properties mentioned above. Say that bb lies in the subtree of aa if aa lies above (or is equal to) bb in the tree.
  • Let the "root" be the object of smallest value. Every object must lie in the subtree of the root.
  • The children of the root should partition the entire search space (aside from the root) into a bounded number of disjoint subspaces.
  • Of course, each child should also have the smallest value in its subtree.

Essentially, we start with the entire search space and then we fracture it into subspaces based on the children of the root. Then we can finish with either of the two approaches.

KK-th Smallest Spanning Tree (USACO Camp 2018)

Let's look at an example.

Problem

Given a graph with N50N\le 50 vertices and at most (N2)\binom{N}{2} edges, find the KK-th (K104K\le 10^4) smallest spanning tree.

(Note: not solved in contest.)

Solution

Video (by tehqin)

For this problem, the objects are spanning trees. The root is the minimum spanning tree (which can be calculated with Kruskal's algorithm), and contains all objects in its subtree.

The idea is to designate a small number of children of the root, each of which should be formed by modifying the root slightly. If we can somehow ensure that each object has at most NN "children" then we only need to consider O(NK)O(NK) spanning trees in order to find the KK-th smallest.

The first step is to consider the easier problem of finding the second MST. To do this, we can choose to exclude one edge of the MST and then find the smallest possible replacement for it. Let the edges in the MST be labeled 1N11\ldots N-1. Then one idea is to let the ii-th child subspace of the root to consist of all spanning trees not including edge ii of the minimum spanning tree for each i[1,N1]i\in [1,N-1].

Unfortunately, this doesn't work because the child subspaces overlap. We can instead let the ii-th child subspace contain all spanning trees that

  • include the first i1i-1 edges of the MST
  • do not include the ii-th edge of the MST

for each i[1,N1]i\in [1,N-1]. Every spanning tree other than the root is contained within exactly one of these child subspaces, which is what we want. After sorting the edges in increasing order of weight once, we can compute the MST within each child subspace in O(Mα(N))O(M\alpha (N)) time with DSU.

Overall, the runtime is O(NMKα(N))O(NMK\alpha(N)) for storing the information about each spanning tree and O(NKlog(NK))O(NK\log (NK)) for maintaing the priority queue of objects so that we can extract the minimum. Note that with the second approach mentioned in the first section the running time would instead be O(NMKα(N)logans)O(NMK\alpha(N)\log ans), which may be too slow.

My Solution

Robotic Cow Herd

Focus Problem – read through this problem before continuing!

As with the analysis, for each location you should

  • sort the controllers of that location by cost
  • add the controller of minimum cost for each location to the cost of the cheapest robot
  • subtract that minimum cost from every controller at that location (so now the minimum cost controller for each location is just zero)

Importantly, we should then sort the locations by their respective second-minimum controller costs.

Approach 1

Binary search on the cost cc of the KK-th robot. If we can compute the costs of all robots with cost at most cc or say that there are more than KK in O(K)O(K) time, then we can solve this problem in O(NlogN+Klogmax(c))O(N\log N+K\log \max(c)) time (similar to "Approach 2" above). This is the approach that the first analysis solution takes, although it includes an extra logN\log N factor due to upper_bound. I have removed this in my solution below.

1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5typedef vector<int> vi;
6typedef pair<ll,ll> pl;
7
8#define f first
9#define s second
10

Approach 2

There's also an O(NlogN+KlogK)O(N\log N+K\log K) time solution with a priority queue that constructs the robots in increasing order of cost. As before, we want each robot to have a bounded number of "child" robots. However, if you look at my DFS function above, it seems that every robot can have up to NN children! Nevertheless, the DFS takes O(K)O(K) rather than O(KN)O(KN) time due to the break statement, which works since we sorted by second-cheapest robot.

In fact, we can modify the DFS function so that every robot has at most three rather than NN children.

1void dfs(int pos, ll cur, int id) {
2 if (cur > mx || num == K) return;
3 res += cur; num ++;
4 if (id+1 < v[pos].size())
5 dfs(pos,cur+v[pos][id+1]-v[pos][id],id+1);
6 if (pos+1 < v.size()) {
7 if (id == 1) dfs(pos+1,cur-v[pos][1]+v[pos+1][1],1);
8 if (id) dfs(pos+1,cur+v[pos+1][1],1);
9 }
10}

Now I'll describe what how the priority queue solution works:

First start with the robot of minimum cost. The robot with second-minimum cost can be formed by just choosing the second-minimum controller for the first location. After this, we have a few options:

  • We can choose the third-minimum controller for the first location.
  • We can discard the second-minimum controller for the first location and select the second-minimum controller for the second location (and never again change the controller selected for the first location).
  • We can keep the second-minimum controller for the first location and select the second-minimum controller for the second location (and never again change the controller selected for the first location).

None of these options can result in a robot of lower cost. In general, suppose that we have a robot and are currently selecting the jj-th cheapest controller for the ii-th location. Then the transitions are as follows:

  • Select the j+1j+1-th cheapest controller for the ii-th location instead.
  • If j=2j=2, select the 11-st cheapest controller for the ii-th location instead and also select the 22-nd cheapest controller for the i+1i+1-st.
  • Keep the jj-th cheapest controller for the ii-th location and also select the 22-nd cheapest controller for the i+1i+1-st.

Since there exists exactly one way to get from the cheapest robot to every possible robot, we can use a priority queue.

1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5typedef pair<int,int> pi;
6typedef vector<int> vi;
7typedef pair<ll,pi> T;
8
9#define f first
10#define s second

Other Problems

StatusSourceProblem NameDifficultyTagsSolution
Baltic OINormalExternal Sol
CCOVery HardCheck DMOJ
YSInsaneShow Sketch

Module Progress:

Give Us Feedback on Fracturing Search!

PrevNext