4 Values whose Sum is 0

http://acm.pku.edu.cn/JudgeOnline/problem?id=2785

Time Limit: 15000MS
Case Time Limit: 5000MS

Description

The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .

Input

The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 2²⁸ ) that belong respectively to A, B, C and D .

Output

For each input file, your program has to write the number quadruplets whose sum is zero.

Sample Input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

Sample Output

5

Hint

Sample Explanation: Indeed, the sum of the five following quadruplets is zero: (-45, -27, 42, 30), (26, 30, -10, -46), (-32, 22, 56, -46),(-32, 30, -75, 77), (-32, -54, 56, 30).

Source

Southwestern Europe 2005


Solving

집합 a, b, c, d 에서 원소를 하나씩 꺼내 그 합이 0이 되는 경우가 몇 가지인지 찾아야 한다.

모든 경우를 검사해서 확인하는 방법이 있으나 이 경우 n^4의 단위 연산이 필요하다. n이 최대 4000까지 주어지므로 n^4=256000000000000으로 너무 크다. 보다 빠르게 문제를 해결할 수 있는 방법이 필요하다.

이런 문제의 경우 집합을 반으로 나눠서 각각 처리 한뒤 소팅을 하여 문제를 해결할 수 있는 경우가 많다. 이 문제도 이런 방법으로 해결할 수 있다.

n^2=16000000 으로 여전히 크지만 Case Time Limit이 5초 이므로 충분하다.
a,b 집합과 c,d집합을 따로 처리하여 a+b의 모든 경우와 c+d의 모든 경우를 계산한 후 소팅한다. 소팅의 시간복잡도는 O(n log n)이다. 이때 n은 4000이 아니라 16000000이다 실질적으로 총 시간복잡도는 n^2 log n^2 = 2 * n^2 log n = 약 100000000 으로 크지만 5초 이내에는 실행 가능하다.
a+b의 모든 경우와 c+d의 모든 경우가 소팅되 되었으면 한쪽은 오름차순으로 한쪽은 내림차순으로 원소를 비교하면서 그 합이 0이 되는 갯수를 세면 된다. 합이 양수인 경우는 합을 작게 만들어야 하므로 내림차순쪽의 원소를 하나 이동한다. 반대의 경우는 합이 커져야 하므로 오림차순쪽의 원소를 하나 이동한다.

#include <cstdlib> #include <cstdio> #include <vector> #include <algorithm> #include <iostream> using namespace std; int main() { int n; int i, j; int num[4][4000]; int count, count1, count2; vector<int> side1, side2; while (scanf("%d", &n) > 0) { side1.clear(); side2.clear(); for (i = 0; i < n; i++) scanf("%d%d%d%d", &num[0][i], &num[1][i], &num[2][i], &num[3][i]); for (i = 0; i < n; i++) for (j = 0; j < n; j++) { side1.push_back(num[0][i] + num[1][j]); side2.push_back(num[2][i] + num[3][j]); } sort(side1.begin(), side1.end()); sort(side2.begin(), side2.end()); i = 0; j = side2.size()-1; count = count1 = count2 = 0; while (i < side1.size() && j >= 0) { if (side1[i] + side2[j] == 0) { count1 = count2 = 1; while (i+1<side1.size() && side1[i] == side1[i+1]) {i++; count1++;} while (j-1>=0 && side2[j] == side2[j-1]) {j--;count2++;} count += count1*count2; i++; j--; } else { if (side1[i] + side2[j] > 0) j--; else i++; } } printf("%d\n", count); } return 0; }