Skip to content

Instantly share code, notes, and snippets.

@thatseeyou
Last active March 18, 2016 09:42
Show Gist options
  • Save thatseeyou/2a41fbe558dc07768ff3 to your computer and use it in GitHub Desktop.
Save thatseeyou/2a41fbe558dc07768ff3 to your computer and use it in GitHub Desktop.
4개의 숫자합이 0이 되는 조합의 개수 찾기
#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;
}
#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;
}
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment