Sum of Four Values

Explicación

Como buscamos cuatro números $a + b + c + d = x$ , podemos guardar todos los valores que podemos alcanzar usando un par de números, y los índices de ambos números del par, usando un mapa. Luego, el problema se reduce a hallar dos números $a$ y $b$ que sumen un valor mapeado tal que ningún índice se repita.

Podemos lograr esto fácilmente en $\mathcal{O}(N^2)$ recorriendo todos los pares únicos de números, comprobando si el hashmap contiene un valor correspondiente a $x - a - b$ , donde $a$ y $b$ son los dos números que se están comprobando. Luego podemos agregar cualquier par visitado previamente para asegurarnos de que ninguno de nuestros índices se superponga.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++Java


// CodeSnip{CPP Short Template}
 
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 {  /// usar la mayoría de los bits en vez de solo los más bajos
	const uint64_t C = ll(2e18 * acos((long double)-1)) + 71;  // número impar grande
	const int RANDOM = rng();
	ll
	operator()(ll x) const {  /// https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
		return __builtin_bswap64((x ^ RANDOM) * C);
	}
};
 
template <class K, class V> using ht = gp_hash_table<K, V, chash>;
 
int main() {
	setIO();
 
	int n, x;
	cin >> n >> x;
 
	vi v(n);
 
	for (int i = 0; i < n; i++) cin >> v[i];
 
	ht<int, pi> hm;
 
	for (int i = n - 1; i >= 0; i--) {
		for (int j = i - 1; j >= 0; j--) {
			int idx = x - v[i] - v[j];
			if (hm.find(idx) != hm.end()) {
				cout << i + 1 << " " << j + 1 << " " << hm[idx].f + 1 << " "
				     << hm[idx].s + 1 << endl;
				return 0;
			}
		}
 
		for (int j = i + 1; j < n; j++) hm[v[i] + v[j]] = {i, j};
	}
 
	cout << "IMPOSSIBLE" << endl;
}


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];  // arreglo indexado desde 1 para este problema
		for (int i = 1; i <= n; i++) { arr[i] = io.nextInt(); }
 
		Map<Integer, int[]> twoSum = new HashMap<>();
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				int differenceToX = x - arr[i] - arr[j];
				if (twoSum.containsKey(differenceToX)) {
					int k = twoSum.get(differenceToX)[0];
					int l = twoSum.get(differenceToX)[1];
					io.printf("%d %d %d %d", i, j, k, l);
					io.close();
					return;
				}
			}
			for (int j = 1; j <= i - 1; j++) {
				twoSum.put(arr[j] + arr[i], new int[] {j, i});
			}
		}
 
		io.println("IMPOSSIBLE");
		io.close();
	}
 
	// CodeSnip{Kattio}
}