1152 - 4 Values whose Sum is 0

All about problems in Volume 11. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Shihab
New poster
Posts: 33
Joined: Thu Jun 13, 2013 1:19 pm

Re: 1152 - 4 Values whose Sum is 0

help tle

Code: Select all

``````#include <cmath>
#include <climits>

#include <queue>

#include <vector>

#include <map>

#include <cstdlib>

#include <fstream>

#include <iomanip>

#include <iostream>

#include <sstream>  // istringstream buffer(myString);

#include <stack>

#include <algorithm>

#include <cstring>

#include <cassert>

using namespace std;

map<int,int>map1;
//int half1[16000001],half2[16000001];
int i = 1;
int k,j;
int n;
int a[4][4000];
int tc;

int main()
{

//freopen("in.txt","r",stdin );
//freopen("out.txt","w+",stdout );

scanf("%d",&tc);

for( i=1; i<=tc; i++ )
{

scanf("%d",&n);

map1.clear();

int c1 = 0;

for( j=1; j<=n; j++)
{
scanf("%d %d %d %d",&a[0][j],&a[1][j],&a[2][j],&a[3][j]);
}

int g=0;
for( k=1; k<=n; k++ )
{
for( j=1; j<=n; j++ )
{
map1[ a[0][k] + a[1][j] ]++;
}
}

g = 0;

for( k=1; k<=n; k++ )
{
for( j=1; j<=n; j++ )
{
if( map1[(a[2][k] + a[3][j]) *-1 ] )
{
map1[(a[2][k] + a[3][j]) *-1 ]--;
c1++;
}
}
}

if( i!=1 )
printf("\n");
printf("%d\n",c1);

}

return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1152 - 4 Values whose Sum is 0

Try solving it with an array instead of STL map.
Compute half1 as the sum of each a and each b. Sort half1, and then create a new sorted map-like array with two elements: each number in half1 and the number of times it occurs in half1.
For each c plus each d, do a binary search of the map-like array to search for that sum.

Part of your algorithm is also wrong.
Input:

Code: Select all

``````1

2
0 1 0 -1
1 0 -1 0
``````
AC output 6
Check input and AC output for thousands of problems on uDebug!