CSES - Sum of Four Values
Author: Neo Wang
Explanation
Since we are looking for four numbers , 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 and that sum up to a mapped value such that no index is repeated.
We can easily achieve this in by looping through all unique pairs of numbers, checking whether or not the hashmap contains a value corresponding to , where and 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:
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 onesconst uint64_t C = ll(2e18 * acos((long double)-1)) + 71; // large odd numberconst 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 problemfor (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!