PrevNext
Rare
 0/8

Meet In The Middle

Author: Chongtian Ma

Problems involving dividing the search space into two.

Edit This Page

Meet In The Middle

Focus Problem – try your best to solve this problem before continuing!

Tutorial

Pro Tip

Meet in the Middle technique can take advantage of the smaller constraint and calculate a naive solution in two halves. Therefore the constraints tend to be doubled.

Naive Solution

Loop through all subsets in the array and if the sum is equal to xx, then increase our answer. Worst case this does about 2402^{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 left\texttt{left} array runs from indexes 00 to n21\frac{n}{2}-1, and the right\texttt{right} array runs from indexes n2\frac{n}{2} to n1n-1. Both arrays will have at most 2020 elements, so we can loop through all subsets of these two arrays in at most 2212^{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 sum\texttt{sum} in the left\texttt{left}, we can simply check how many elements of xsumx - \texttt{sum} there are in right\texttt{right}. This can be done using simple binary search.

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

C++

#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]; }

Java

Warning: Tight Time Limit

CSES has very tight time constraints for java, so the following code will barely pass in around 1 second. It is not guaranteed to pass on first submits, so you might need to submit multiple times.

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(); }

Problems

StatusSourceProblem NameDifficultyTags
CFEasy
Show TagsBinary Search, Meet in the Middle
SilverEasy
Show Tags2P, Meet in the Middle
CFEasy
Show TagsBinary Search, DFS, Meet in the Middle
YSNormal
Show TagsBitmasks, DP, Meet in the Middle
CFHard
Show TagsDFS, Meet in the Middle, NT
CFHard
Show TagsBinary Search, DFS, Meet in the Middle
KattisHard
Show TagsDFS, Meet in the Middle, PIE

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext