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

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

Re: 1152 - 4 Values whose Sum is 0

Post by Shihab » Sun Nov 23, 2014 7:24 pm

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

Post by brianfry713 » Wed Nov 26, 2014 12:01 am

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!

Post Reply

Return to “Volume 11 (1100-1199)”