Meet In The Middle

Meet In The Middle

Tutorial

Naive Solution

Loop through all subsets in the array and if the sum is equal to $x$, then increase our answer. Worst case this does about $2^{40}$ operations, which is way too slow.

Meet in the Middle Solution

We can divide the given array into two separate arrays. Let's say that the $\texttt{left}$ array runs from indexes $0$ to $\frac{n}{2}-1$, and the $\texttt{right}$ array runs from indexes $\frac{n}{2}$ to $n-1$. Both arrays will have at most $20$ elements, so we can loop through all subsets of these two arrays in at most $2^{21}$ operations, which is perfectly fine.

Now that we've got the subset sums of these two separate arrays, we need to recombine them to search for our answer. For every $\texttt{sum}$ in the $\texttt{left}$, we can simply check how many elements of $x - \texttt{sum}$ there are in $\texttt{right}$. This can be done using simple binary search.

Time Complexity: $O(N\cdot 2^{N/2})$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Kattio io = new Kattio();

		int n = io.nextInt(), x = io.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) { a[i] = io.nextInt(); }

Meet In The Middle On Trees

We apply meet in the middle technique by splitting the continuous chain of $9$ songs into chains of four songs and the center one. We'll compute for each node all the subsets of four different artists such that there is a path going into the this node. Similarly, by reversing the graph, compute the paths going out of the node. In the combining step, loop through all nodes and fix one as the center node. Having precomputed the two groups of subsets (ingoing and outgoing paths), we want to find two sets that are disjoint, i.e no common element. Using Inclusion-Exclusion count for a given set in the first group the number of sets in the second group with one common element. The upperbound for the number of sets is $\binom{100}{4} \cdot 100 = 4 \cdot 10^8$.

Copy
#include <functional>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
	int n;
	cin >> n;

Problems