4개의 숫자합이 0이 되는 조합의 개수 찾기

zerosum.c

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

/*
gcc zerosum.c -o zerosum -ansi -fno-asm -O2 -Wall -lm
*/

void printBuf(int *buf, int num)
{
	for (int i = 0; i < num; i++) {
		printf("[%04d] %d\n", i, buf[i]);
	}
}

static int compareInt(const void *l, const void *r) {
	/*printf("%d - %d = %d\n", *(int *)l, *(int *)r, *(int *)l - *(int *)r); */
	return *(int *)l - *(int *)r;
}

int main(int argc, char *argv[], char *envp[])
{
	int totalNumber = 0;
	
	{
		scanf("%d\n", &totalNumber);
		/* printf("total number = %d\n", totalNumber); */
	}

	int *bufA = malloc(sizeof(int) * totalNumber);
	int *bufB = malloc(sizeof(int) * totalNumber);
	int *bufC = malloc(sizeof(int) * totalNumber);
	int *bufD = malloc(sizeof(int) * totalNumber);
	{
		/* read data */
		for (int i = 0; i < totalNumber; i++) {
			scanf("%d %d %d %d\n", bufA + i, bufB + i, bufC + i, bufD + i); 
			/*printf("%d %d %d %d\n", bufA[i], bufB[i], bufC[i], bufD[i]); */
		}
	}

	int pairTotal = totalNumber * totalNumber;
	int *bufAB = malloc(sizeof(int) * pairTotal);
	int *bufCD = malloc(sizeof(int) * pairTotal);
	{
		/* sort AB, CD */
		for (int i = 0; i < totalNumber; i++) {
			int *pAB = bufAB + i * totalNumber;
			int *pCD = bufCD + i * totalNumber;
			for (int j = 0; j < totalNumber; j++) {
				pAB[j] = bufA[i] + bufB[j];
				pCD[j] = -(bufC[i] + bufD[j]);
			}
		}

		/*printBuf(bufAB, totalNumber * totalNumber); */
		qsort(bufAB, pairTotal, sizeof(int), compareInt);
		qsort(bufCD, pairTotal, sizeof(int), compareInt);
		/*printBuf(bufAB, totalNumber * totalNumber); */
	}

	int totalMatch = 0;
	{
		int iAB = 0;
		int iCD = 0;

		int prevIdx = -99;
		int prevMatch = 0;
		while(iAB < pairTotal && iCD < pairTotal) {
			if (bufAB[iAB] > bufCD[iCD]) {
				iCD++;
				continue;
			}
			else if (bufAB[iAB] < bufCD[iCD]) {
				iAB++;
				continue;
			}
			else if (bufAB[iAB] == bufCD[iCD]) {
				totalMatch++;
				/*printf("A + B = %d\n", bufAB[iAB]); */
				if (prevIdx == iAB) {
					prevMatch++;
				}
				else {
					prevIdx = iAB;
					prevMatch = 1;
				}

				/* iAB와 같은 iCD를 모두 찾았을 경우에
				   next iAB도 iAB와 같은 경우에는 셈을 해 주어야 한다.
				*/
				if ((iCD + 1 == pairTotal || bufCD[iCD] != bufCD[iCD + 1])) {
					while(iAB + 1 < pairTotal) {
						if (bufAB[iAB] == bufAB[iAB + 1]) {
							totalMatch += prevMatch;
							prevIdx++;
							iAB++;
						}
						else {
							break;
						}
					}
				}
				iCD++;
				continue;
			}
		}

	}

	printf("%d\n", totalMatch);

	return 0;
}

zerosum7.c

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#ifdef DEBUG
#include <sys/time.h>
static struct timeval start_tv;
void stopwatch_start() 
{
	gettimeofday(&start_tv, NULL);
}

void stopwatch_check(char msg[])
{
	return;

	struct timeval now_tv;
	gettimeofday(&now_tv, NULL);

	struct timeval elapsed_tv;

	timersub(&now_tv, &start_tv, &elapsed_tv);

	printf("%s: %ld.%d\n", msg, elapsed_tv.tv_sec, elapsed_tv.tv_usec);
}
#endif

/*
gcc zerosum.c -o zerosum -ansi -fno-asm -O2 -Wall -lm
*/

const int NumCols = 4;

void printBuf(int *buf, int num)
{
	for (int i = 0; i < num; i++) {
		printf("[%04d] %d\n", i, buf[i]);
	}
}

static int compareInt(const void *l, const void *r) {
	/*printf("%d - %d = %d\n", *(int *)l, *(int *)r, *(int *)l - *(int *)r); */
	return *(int *)l - *(int *)r;
}

static int compareReverseInt(const void *l, const void *r) {
	/*printf("%d - %d = %d\n", *(int *)l, *(int *)r, *(int *)l - *(int *)r); */
	return *(int *)r - *(int *)l;
}

typedef struct heap_node_tag {
	int x;
	int y;
	int value;
} heap_node_t;

#define HEAP_START_INDEX 1

void printHeap(int sizeHeap, heap_node_t *minHeap)
{
	printf("[%p]", minHeap);
	for(int i = HEAP_START_INDEX; i <= sizeHeap; i++) {
		if (i == 2 || i == 4 || i == 8 || i == 16 || i == 32) {
			printf("| ");
		}
		printf("%d(%d,%d) ", minHeap[i].value, minHeap[i].x, minHeap[i].y);
	}
	printf("\n");
}

static int extractMinValueCallCount = 0;
int extractMinValue(const int sizeSumList, int *sumList, heap_node_t *minHeap, int *minCount) 
{
	extractMinValueCallCount++;

	heap_node_t * const topNode = minHeap + HEAP_START_INDEX;
	const int sizeSumColumn = sizeSumList + 1;
	const int sizeHeap = sizeSumList >> 1;

	*minCount = 1;
	/* int minValue = *(sumList + (sizeSumList + 1) * minHeap[1].x + minHeap[1].y); */
	int minValue = topNode->value;

	if (minValue == INT_MAX) {
		*minCount = 0;
		return minValue;
	}

	int curIndex = HEAP_START_INDEX;
	int curValue = minHeap[curIndex].value;
	int leftIndex, leftValue, rightIndex, rightValue, nextIndex;
	heap_node_t temp;


	for(;;) {
		/* change root */
		topNode->y += 1;
		/* update root value */
		topNode->value = *(sumList + sizeSumColumn * topNode->x + topNode->y);

		curIndex = HEAP_START_INDEX;
		curValue = minHeap[curIndex].value;

		/* min heapify */
		do {
			leftIndex = curIndex << 1;
			leftValue = minHeap[leftIndex].value;

			rightIndex = leftIndex + 1;
			rightValue = minHeap[rightIndex].value;

			if (leftValue < curValue || rightValue < curValue) {
				nextIndex = leftValue < rightValue ? leftIndex : rightIndex;

				temp = minHeap[curIndex];
				minHeap[curIndex] = minHeap[nextIndex];
				minHeap[nextIndex] = temp;

				if (nextIndex > sizeHeap) {
					break;
					/* next Index is leaf */
					/* no more */
				}
				else {
					curIndex = nextIndex;
				}
			}
			else {
				break;
			}
		} while(1);

#ifdef DEBUG
		printf("          new root = %d\n", topNode->value);
#endif
		/* check duplicate */
		if (topNode->value > minValue) {
#ifdef DEBUG
			printHeap(sizeSumList, minHeap);
#endif
			break;
		}

		(*minCount)++;
	} 

	return minValue;
}

int main(int argc, char *argv[], char *envp[])
{
	int numInitialRows = 0;
	{
		scanf("%d\n", &numInitialRows);
	}

	int *inputList[NumCols];
	{
		for (int col = 0; col < NumCols; col++) {
			inputList[col] = (int *)malloc(sizeof(int) * numInitialRows);
		}

		for (int row = 0; row < numInitialRows; row++) {
			scanf("%d %d %d %d\n", inputList[0] + row, inputList[1] + row, inputList[2] + row, inputList[3] + row); 
		}
	}
#ifdef DEBUG
	stopwatch_check("Read Done");
#endif

	if (numInitialRows == 1) {
		printf("1\n");
		return 0;
	}

	{
		qsort(inputList[0], numInitialRows, sizeof(int), compareInt);
		qsort(inputList[1], numInitialRows, sizeof(int), compareInt);
		qsort(inputList[2], numInitialRows, sizeof(int), compareReverseInt);
		qsort(inputList[3], numInitialRows, sizeof(int), compareReverseInt);
	}
#ifdef DEBUG
	stopwatch_check("Sort each Done");
#endif

	int *leftSumList = (int *)malloc(sizeof(int) * (numInitialRows + 1) * numInitialRows);
	int *rightSumList = (int *)malloc(sizeof(int) * (numInitialRows + 1) * numInitialRows);
	{
		/* sum Left, Right */
		int x;
		int y;
		for (x = 0; x < numInitialRows; x++) {
			for (y = 0; y < numInitialRows; y++) {
				leftSumList[(numInitialRows + 1) * x + y] = inputList[0][x] + inputList[1][y];
				rightSumList[(numInitialRows + 1) * x + y] = -(inputList[2][x] + inputList[3][y]);
			}
			leftSumList[(numInitialRows + 1) * x + y] = INT_MAX; /* ending mark */
			rightSumList[(numInitialRows + 1) * x + y] = INT_MAX;
		}
	}
#ifdef DEBUG
	stopwatch_check("Sum Done");
#endif

#ifdef DEBUG 
	{
		int x, y;

		printf("--- input ---\n");

		printf("          x     0   1   2   3\n");
		for (y = 0; y < numInitialRows; y++) {
			printf("Left  y[%02d] : ", y);
			for (x = 0; x < numInitialRows; x++) {
				printf("%3d ", leftSumList[(numInitialRows + 1) * x + y]);
			}
			printf("\n");
		}
		printf("\n");

		for (y = 0; y < numInitialRows; y++) {
			printf("Right y[%02d] : ", y);
			for (x = 0; x < numInitialRows; x++) {
				printf("%3d ", rightSumList[(numInitialRows + 1) * x + y]);
			}
			printf("\n");
		}
		printf("\n");
	}
#endif

	heap_node_t *leftMinHeap = (heap_node_t *)malloc(sizeof(heap_node_t) * (numInitialRows + 2));
	heap_node_t *rightMinHeap = (heap_node_t *)malloc(sizeof(heap_node_t) * (numInitialRows + 2));

	/* init headp */
	{
		int i;

		for (i = HEAP_START_INDEX; i <= numInitialRows; i++) {
			const int x = i - HEAP_START_INDEX;
			leftMinHeap[i].x = x;
			leftMinHeap[i].y = 0;
			leftMinHeap[i].value = leftSumList[(numInitialRows + 1) * x];
			rightMinHeap[i].x = x;
			rightMinHeap[i].y = 0;
			rightMinHeap[i].value = rightSumList[(numInitialRows + 1) * x];
		}
		leftMinHeap[i].value = INT_MAX;
		rightMinHeap[i].value = INT_MAX;
	}
		
#ifdef DEBUG
	printf("init heap\n");
	printHeap(numInitialRows, leftMinHeap);
	printf("\n");
	printHeap(numInitialRows, rightMinHeap);
#endif

	long long matchCount = 0;

	int leftMinCount = 0;
	int rightMinCount = 0;

	int leftMinValue = extractMinValue(numInitialRows, leftSumList, leftMinHeap, &leftMinCount);
	int rightMinValue = extractMinValue(numInitialRows, rightSumList, rightMinHeap, &rightMinCount);

	do {
#ifdef DEBUG
		printf("%d(%d) vs. %d(%d)\n", leftMinValue, leftMinCount, rightMinValue, rightMinCount);
#endif

		if (leftMinValue == rightMinValue) {
			matchCount += (long long)leftMinCount * rightMinCount;

			leftMinValue = extractMinValue(numInitialRows, leftSumList, leftMinHeap, &leftMinCount);
			rightMinValue = extractMinValue(numInitialRows, rightSumList, rightMinHeap, &rightMinCount);
		}
		else if (leftMinValue < rightMinValue) {
			leftMinValue = extractMinValue(numInitialRows, leftSumList, leftMinHeap, &leftMinCount);
		}
		else {
			rightMinValue = extractMinValue(numInitialRows, rightSumList, rightMinHeap, &rightMinCount);
		}

		if (leftMinValue == INT_MAX || rightMinValue == INT_MAX)
			break;

	} while(1);

	printf("%lld\n", matchCount);
	/*printf("call minHeapify: %d\n", minHeapifyCallCount);
	printf("call extractMinValue: %d\n", extractMinValueCallCount); */

#ifdef DEBUG
	stopwatch_check("All Done");
#endif

	return 0;
}

zerosum8.c

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef DEBUG
#include <sys/time.h>
static struct timeval start_tv;
void stopwatch_start() 
{
	gettimeofday(&start_tv, NULL);
}

void stopwatch_check(char msg[])
{
	struct timeval now_tv;
	gettimeofday(&now_tv, NULL);

	struct timeval elapsed_tv;

	timersub(&now_tv, &start_tv, &elapsed_tv);

	printf("%s: %ld.%06d\n", msg, elapsed_tv.tv_sec, elapsed_tv.tv_usec);
}
#endif

/*
gcc zerosum.c -o zerosum -ansi -fno-asm -O2 -Wall -lm
*/

const int NumCols = 4;

void printBuf(int *buf, int num)
{
	for (int i = 0; i < num; i++) {
		printf("[%04d] %d\n", i, buf[i]);
	}
}

static int compareInt(const void *l, const void *r) {
	/*printf("%d - %d = %d\n", *(int *)l, *(int *)r, *(int *)l - *(int *)r); */
	return *(int *)l - *(int *)r;
}

static int compareReverseInt(const void *l, const void *r) {
	/*printf("%d - %d = %d\n", *(int *)l, *(int *)r, *(int *)l - *(int *)r); */
	return *(int *)r - *(int *)l;
}

typedef struct valueCountNode_tag {
	int value;
	int count;
} Node;

int main(int argc, char *argv[], char *envp[])
{
#ifdef DEBUG
	{
		stopwatch_start();
	}
#endif
	/**************************************************************************
	 * 1. Read Input
	 */
	int numInitialRows = 0;
	{
		scanf("%d\n", &numInitialRows);
	}

	int *inputList[NumCols];
	{
		for (int col = 0; col < NumCols; col++) {
			inputList[col] = (int *)malloc(sizeof(int) * numInitialRows);
		}

		for (int row = 0; row < numInitialRows; row++) {
			scanf("%d %d %d %d\n", inputList[0] + row, inputList[1] + row, inputList[2] + row, inputList[3] + row); 
		}
	}
#ifdef DEBUG
	stopwatch_check("Read Done");
#endif

	/**************************************************************************
	 * 2. Sort each input columns
	 */
	{
		qsort(inputList[0], numInitialRows, sizeof(int), compareInt);
		qsort(inputList[1], numInitialRows, sizeof(int), compareInt);
		qsort(inputList[2], numInitialRows, sizeof(int), compareReverseInt);
		qsort(inputList[3], numInitialRows, sizeof(int), compareReverseInt);
	}
#ifdef DEBUG
	stopwatch_check("Sort each Done");
#endif

	/**************************************************************************
	 * 3. Make array of list summing each pair
	 */
#define LEFT_SIDE 0
#define RIGHT_SIDE 1
	Node *sumList[2][2];
	int listHeight = numInitialRows + 1;
	{
		int side, i;

		for (side = 0; side < 2; side++) {
			for (i = 0; i < 2; i++) {
				sumList[side][i] = (Node *)malloc(sizeof(Node) * listHeight * numInitialRows);
			}
		}
	}
	{
		/* sum Left, Right */
		int x, y;
		for (x = 0; x < numInitialRows; x++) {
			for (y = 0; y < numInitialRows; y++) {
				sumList[LEFT_SIDE][0][listHeight * x + y].value = inputList[0][x] + inputList[1][y];
				sumList[LEFT_SIDE][0][listHeight * x + y].count = 1;
				sumList[RIGHT_SIDE][0][listHeight * x + y].value = -(inputList[2][x] + inputList[3][y]);
				sumList[RIGHT_SIDE][0][listHeight * x + y].count = 1;
			}
			sumList[LEFT_SIDE][0][listHeight * x + y].value = INT_MAX; /* ending mark */
			sumList[LEFT_SIDE][0][listHeight * x + y].count = 0; /* ending mark */
			sumList[RIGHT_SIDE][0][listHeight * x + y].value = INT_MAX;
			sumList[RIGHT_SIDE][0][listHeight * x + y].count = 0;
		}
	}
#ifdef DEBUG
	stopwatch_check("Sum Done");
#endif

#ifdef DEBUG 
	{
		int x, y;

		printf("--- input ---\n");

		printf("          x     0   1   2   3\n");
		for (y = 0; y < numInitialRows; y++) {
			printf("Left  y[%02d] : ", y);
			for (x = 0; x < numInitialRows; x++) {
				printf("%3d ", sumList[LEFT_SIDE][0][listHeight * x + y].value);
			}
			printf("\n");
		}
		printf("\n");

		for (y = 0; y < numInitialRows; y++) {
			printf("Right y[%02d] : ", y);
			for (x = 0; x < numInitialRows; x++) {
				printf("%3d ",sumList[RIGHT_SIDE][0][listHeight * x + y].value);
			}
			printf("\n");
		}
		printf("\n");
	}
#endif
	/* free inputList */
	/*
	{
		for (int col = 0; col < NumCols; col++) {
			free(inputList[col]);
		}
	}
	*/

	/**************************************************************************
	 * 4. Merge sort array of list
	 */
	int side;
	int numSourceList; /* ex. 9 -> 5 -> 3 -> 2 -> 1 */
	int list;

	int sourceIdx = 0; /* 0 -> 1 -> 0 -> ... */
	int targetIdx = 1; /* 1 -> 0 -> 1 -> ... */

	for (side = 0; side < 2; side++) {
		sourceIdx = 0; /* 0 -> 1 -> 0 -> ... */
		targetIdx = 1; /* 1 -> 0 -> 1 -> ... */
		int sourceListHeight = listHeight;

		for (numSourceList = numInitialRows; numSourceList > 1; numSourceList = ((numSourceList + 1) >> 1)) {
			Node *sourceList = sumList[side][sourceIdx];
			Node *targetList = sumList[side][targetIdx];
#ifdef DEBUG
			memset(targetList, 0, sizeof(Node) * listHeight * numInitialRows);
#endif
			for (list = 0; list < (numSourceList >> 1); list++) {
#ifdef DEBUG
				printf("side = %d, source = %d, target = %d, sourceListHeight = %d, numSourceList = %d, list = %d\n", side, sourceIdx, targetIdx, sourceListHeight, numSourceList, list);
#endif
				Node *source0 = sourceList + ((sourceListHeight << 1) * list);
				Node *source1 = source0 + sourceListHeight;

				Node *target = targetList + ((sourceListHeight << 1) * list);
				target->value = source0->value;
				target->count = 0;

				for (;;) {
					/* printf("    %d vs. %d\n", source0->value, source1->value); */
					if (source0->value < source1->value) {
						if (target->value == source0->value) {
							target->count += source0->count;
						}
						else {
							target++;
							target->value = source0->value;
							target->count = source0->count;
						}
						source0++;
					}
					else if (source0->value > source1->value) {
						if (target->value == source1->value) {
							target->count += source1->count;
						}
						else {
							target++;
							target->value = source1->value;
							target->count = source1->count;
						}
						source1++;
					}
					else /* (source0->value == source1->value) */ {
						if (target->value == source0->value) {
							target->count += source0->count + source1->count;
						}
						else {
							target++;
							target->value = source0->value;
							target->count = source0->count + source1->count;
						}
						source0++;
						source1++;
					}

					if (target->value == INT_MAX)
						break;
				} /* for(;;) */
			} /* for (list = 0; list < (numSourceList / 2); list++)  */

			/* if the other exists */
			if ((list << 1) < numSourceList) {
				Node *source0 = sourceList + ((sourceListHeight << 1) * list);
				Node *target = targetList + ((sourceListHeight << 1) * list);
				long numRemain = (listHeight * numInitialRows - ((sourceListHeight << 1) * list));
#ifdef DEBUG
				printf("OTHER: remain = %ld, side = %d, source = %d, target = %d, sourceListHeight = %d, numSourceList = %d, list = %d\n", numRemain, side, sourceIdx, targetIdx, sourceListHeight, numSourceList, list);
#endif
				memcpy(target, source0, sizeof(Node) * numRemain);
			}
#ifdef DEBUG 
			{
				printf("---- merged target ----\n");
				int value, count;
				for (int i = 0;i < listHeight * numInitialRows;i++) {
					value = targetList[i].value; 
					count = targetList[i].count;
					if (value == INT_MAX) 
						printf("[%d][%d][%02d] ------\n", side, targetIdx, i);
					else 
						printf("[%d][%d][%02d] %3d * %3d\n", side, targetIdx, i, value, count);
				}
			}
#endif

			sourceListHeight *= 2;
			sourceIdx = targetIdx;
			targetIdx = (sourceIdx + 1) % 2;
		} /* for (numSourceList = numInitialRows; numSourceList > 1; numSourceList = (numSouceList + 1) / 2) { */
	} /* for (side = 0; side < 2; side++)  */

#ifdef DEBUG 
	{
		int side, i;

		printf("---- merged ----\n");
	
		for (side = 0; side < 2; side++) {
			int value, count;
			Node *sourceList = sumList[side][sourceIdx];
			printf(">>-- source ----\n");
			for (i = 0;i < listHeight * numInitialRows;i++) {
				value = sourceList[i].value; 
				count = sourceList[i].count;
				if (value == INT_MAX) 
					break;
				else 
					printf("[%d][%d][%02d] %3d * %3d\n", side, sourceIdx, i, value, count);
			}
		}
	}
#endif

	/**************************************************************************
	 * 5. Count same pairs with sorted list
	 */
	long long matchCount = 0;
	{
		Node *leftList = sumList[LEFT_SIDE][sourceIdx];
		Node *rightList = sumList[RIGHT_SIDE][sourceIdx];

		for(int leftValue = leftList->value, rightValue = rightList->value;leftValue < INT_MAX && rightValue < INT_MAX; leftValue = leftList->value, rightValue = rightList->value) {

			if (leftValue < rightValue) {
				leftList++;
			}
			else if (leftValue > rightValue) {
				rightList++;
			}
			else {
				matchCount += (long long)leftList->count * rightList->count;
				leftList++;
				rightList++;
			}
		}
	}

	printf("%lld\n", matchCount);

#ifdef DEBUG
	stopwatch_check("All Done");
#endif

	return 0;
}