Home » 国际竞赛 » Details

USACO 2020 January Contest, Gold Problem 2. Farmer John Solves 3SUM

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午6:19

USACO 2020 January Contest, Gold Problem 2. Farmer John Solves 3SUM

Farmer John believes he has made a major breakthrough in algorithm design: he claims to have found a nearly linear time algorithm for the 3SUM problem, an algorithmic problem famous for the fact that no known solution exists running in substantially better than quadratic time. One formulation of the 3SUM problem is the following: given an array $s_{1}, \dots, s_{m}$ of integers, count the number of unordered triples of distinct indices $i, j, k$ such that $s_{i} + s_{j} + s_{k} = 0$ .

To test Farmer John's claim, Bessie has provided an array $A$ of $N$ integers ( $1 \leq N \leq 5000$ ). Bessie also asks $Q$ queries ( $1 \leq Q \leq 10^{5}$ ), each of which consists of two indices $1 \leq a_{i} \leq b_{i} \leq N$ . For each query, Farmer John must solve the 3SUM problem on the subarray $A [a_{i} \dots b_{i}]$ .

Unfortunately, Farmer John has just discovered a flaw in his algorithm. He is confident that he can fix the algorithm, but in the meantime, he asks that you help him pass Bessie's test!

SCORING:

Test cases 2-4 satisfy $N \leq 500.$
Test cases 5-7 satisfy $N \leq 2000.$
Test cases 8-15 satisfy no additional constraints.

INPUT FORMAT (file threesum.in):

The first line contains two space-separated integers $N$ and $Q$ . The second line contains the space-separated elements $A_{1}, \dots, A_{N}$ of array $A$ . Each of the subsequent $Q$ lines contains two space-separated integers $a_{i}$ and $b_{i}$ , representing a query.It is guaranteed that $- 10^{6} \leq A_{i} \leq 10^{6}$ for every array element $A_{i}$ .

OUTPUT FORMAT (file threesum.out):

The output should consist of $Q$ lines, with each line $i$ containing a single integer---the answer to the $i$ -th query. Note that you should use 64-bit integers to avoid overflow.

SAMPLE INPUT:

7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7

SAMPLE OUTPUT:

2
1
4

For the first query, the possible triples are $(A_{1}, A_{2}, A_{5})$ and $(A_{2}, A_{3}, A_{4}) .$

Problem credits: Dhruv Rohatgi

<h3> USACO 2020 January Contest, Gold Problem 2. Farmer John Solves 3SUM 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

For each pair $(i, k)$ satisfying $i < k$ let $n u m [i] [k]$ equal the number of $j$ such that $i < j < k$ and $A_{i} + A_{j} + A_{k} = 0$ . Then if $a n s [i] [k]$ denotes the answer for $(A_{i}, A_{i + 1}, \dots, A_{k})$ , we can write

a n s [i] [k] = n u m [i] [k] + a n s [i] [k - 1] + a n s [i + 1] [k] - a n s [i + 1] [k - 1] .

After generating $a n s$ , each query can be answered in constant time.

Now I'll describe a way to compute $n u m [i] [i + 1], \dots, n u m [i] [N]$ in $O (N)$ time. For each $k$ from $i + 1, \dots N$ in increasing order, consider a hashmap (unordered_map in C++) that allows you to query the number of occurrences of any integer among $A_{i + 1}, \dots, A_{k - 1}$ . Then $n u m [i] [k]$ is equal to the number of occurrences of $- A_{i} - A_{k}$ in this map. When $k$ is incremented by one the only change to the map is a single insertion. As hashmap operations run in $O (1)$ time, this solution runs in $O (N^{2})$ time overall.

However, due to the high constant factor of hashmap, this solution does not earn full points. Because all entries of $A$ are in the range $[- 10^{6}, 10^{6}],$ we can replace the hashmap with an array of size $2 \cdot 10^{6} + 1,$ greatly improving the runtime.

import java.io.*;
import java.util.*;
 
public class threesum {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new FileReader("threesum.in"));
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("threesum.out")));
		String[] line = in.readLine().split(" ");
		int N = Integer.parseInt(line[0]);
		int Q = Integer.parseInt(line[1]);
		line = in.readLine().split(" ");
		int[] A = new int[N]; 
		long[][] ans = new long[N][N];
		for (int i = 0; i < N; ++i) A[i] = Integer.parseInt(line[i]);
		int[] z = new int[2000001];
		for (int i = N-1; i >= 0; --i) {
			for (int j = i+1; j < N; ++j) {
				int ind = 1000000-A[i]-A[j];
				if (ind >= 0 && ind <= 2000000) ans[i][j] = z[ind];
				z[1000000+A[j]] ++;
			}
			for (int j = i+1; j < N; ++j) {
				z[1000000+A[j]] --;
			}
		}
		for (int i = N-1; i >= 0; --i) 
			for (int j = i+1; j < N; ++j)
				ans[i][j] += ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
		for (int i = 0; i < Q; ++i) {
			line = in.readLine().split(" ");
			int a = Integer.parseInt(line[0]);
			int b = Integer.parseInt(line[1]);
			out.println(ans[a-1][b-1]);
		}
		out.close();
	}
}

Of course, it was still possible to pass without replacing the hashmap by an array. Although this wasn't intended, I'll include two additional solutions for the sake of completeness.

In C++, gp_hash_table is somewhat faster than unordered_map, especially if you specify an initial capacity. See here for more information.

#include <bits/stdc++.h>
using namespace std;

void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}

#include <ext/pb_ds/assoc_container.hpp> // for gp_hash_table
using namespace __gnu_pbds;

int N,Q;
long long ans[5000][5000];
vector<int> A;
 
int main() {
	setIO("threesum");
	cin >> N >> Q;
	A.resize(N); for (int i = 0; i < N; ++i) cin >> A[i];
	for (int i = 0; i < N; ++i) {
		gp_hash_table<int,int> g({},{},{},{},{1<<13}); 
		// initialize with capacity that is a power of 2
		for (int j = i+1; j < N; ++j) {
			int res = -A[i]-A[j];
			auto it = g.find(res); 
			if (it != end(g)) ans[i][j] = it->second;
			g[A[j]] ++;
		}
	}
	for (int i = N-1; i >= 0; --i) for (int j = i+1; j < N; ++j)
		ans[i][j] += ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
	for (int i = 0; i < Q; ++i) {
		int a,b; cin >> a >> b;
		cout << ans[a-1][b-1] << "\n";
	}
}

In Java, a hashmap solution passes if StreamTokenizer is used to take care of input, although it uses much more memory than I would expect. (If anyone knows how to reduce the memory usage, could you let me know?)

import java.io.*;
import java.util.*;
 
public class threesum {
	static StreamTokenizer in;
	static int nextInt() throws IOException {
		in.nextToken();
		return (int)in.nval;
	}
	public static void main(String[] args) throws IOException {
		in = new StreamTokenizer(new BufferedReader(new FileReader("threesum.in")));
		PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("threesum.out")));
		int N = nextInt(); int Q = nextInt();
		int[] A = new int[N]; 
		long[][] ans = new long[N][N];
		for (int i = 0; i < N; ++i) A[i] = nextInt();
		Map<Integer,Integer> z = new HashMap<>();
		for (int i = N-1; i >= 0; --i) {
			z.clear();
			for (int j = i+1; j < N; ++j) {
				int ind = -A[i]-A[j];
				ans[i][j] = z.getOrDefault(ind,0);
				z.put(A[j],z.getOrDefault(A[j],0)+1);
			}
		}
		for (int i = N-1; i >= 0; --i) 
			for (int j = i+1; j < N; ++j)
				ans[i][j] += ans[i+1][j]+ans[i][j-1]-ans[i+1][j-1];
		for (int i = 0; i < Q; ++i) 
			out.println(ans[nextInt()-1][nextInt()-1]);
		out.close();
	}
}

[/hide]