CSES - Sum of Four Values

Author: Neo Wang

Table of Contents

ExplanationImplementation

Explanation

Since we are looking for four numbers a+b+c+d=xa + 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 aa and bb that sum up to a mapped value such that no index is repeated.

We can easily achieve this in O(N2)\mathcal{O}(N^2) by looping through all unique pairs of numbers, checking whether or not the hashmap contains a value corresponding to xabx - a - b, where aa and bb 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: O(N2)\mathcal{O}(N^2)

C++

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

Java

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

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!