CSES - Sum of Four Values

Explanation

Since we are looking for four numbers $a + b + c + d = x$, we can store all the values that we can achieve using a pair of numbers, and the indices for both numbers in the pair using a map. Then, the problem is reduced to finding two numbers $a$ and $b$ that sum up to a mapped value such that no index is repeated.

We can easily achieve this in $\mathcal{O}(N^2)$ by looping through all unique pairs of numbers, checking whether or not the hashmap contains a value corresponding to $x - a - b$, where $a$ and $b$ are the two numbers being checked. We can then add any previously visited pair in order to make sure none of our indices overlap.

Implementation

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

Copy
 Code Snippet: C++ Short Template (Click to expand)

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct chash {  /// use most bits rather than just the lowest ones
	const uint64_t C =
	    ll(2e18 * acos((long double)-1)) + 71;  // large odd number
	const int RANDOM = rng();

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

public class Main {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int x = io.nextInt();
		int[] arr = new int[n + 1];  // 1-indexed array for this problem
		for (int i = 1; i <= n; i++) { arr[i] = io.nextInt(); }