10125 - Sumsets

[Articuno]

I don't think a O(n^4) algo can pass the time limit. Try something better.

[ergysr]

For input 4 -1 0 1 0 the correct output from an old post is 0. logically , -1 + 0 + 1 = 0, but these elements are not distinct(zero appears twice). Can someone give me an explanation.

Thanks!

[mf]

'4 -1 0 1 0' is not a valid input, so you don't need to deal with it.

[Sedefcho]

I am wondering if there is a better method/approach/idea for solving
this problem (different from the one already described above in this thread).

If I am not mistaken the method described above has worst-case
time complexity O( N^2 * log(N^2) ) which basically simplifies down
to O( N^2 * log(N) ) if we ignore the constants
(when estimating the time complexity).

[chchwy]

the O(n^4) algorithm can get AC actually !

but need some tips

Code: Select all

sort array first

for( d = N to 1 )  //from higher to lower
  for( a = 1 to N )
    for( b = a+1 to N )
      for( c = b+1 to N )
        //do comparison here ..

the tip is put the loop d outside, and from higher to lower

it's very efficeint , even faster than (a+b) = (d-c) way

[sazzadcsedu]

Yea,the O(n^4) complexity algorithm can pass the time limit,even in better way than O((N^2)*lg(n^2)) algorithm.But this is not because of the efficiency of O(n^4) algorithm,rather because of the weak data set.In the worst case,when answer is 'no solution' it may have to check almost (1000*1000*1000*1000) combination.

[mostafiz93]

I don't think a O(n^4) algo can pass the time limit. Try something better.

i've got ac with O(n^4), but with some optimization!

[@li_kuet]

Try this case
Input :

Code: Select all

4
-3 -3 -3 -9
0

Output :

Code: Select all

-9

[hpjhc]

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

int set[1010];
void Qsort(int, int);
int search(int, int, int );

int main(void) {

int t, i, j, k, a, ok;
while(scanf("%d", &t), t)
{
for(i = 0; i < t; i++)
scanf("%d", &set);
Qsort(0, t-1);
ok = 0;
for(i = 0; i < t; i++)
{
for(j = i+1; j < t; j++)
{
a = set+set[j];
for(k = t-1; k >= 0; k--)
{
if(set[k] != set && set[k] != set[j] && set[k]-a != set && set[k]-a != set[j] && a != 0)
if(search(set[k]-a, 0, t-1))
{
ok = 1;
break;
}
}
if(ok)
break;
}
if(ok)
break;
}
if(ok)
printf("%d\n", set[k]);
else
printf("no solution\n");
}
return 0;
}

void Qsort(int low, int high)
{
int p = low, q = high, a;
if(low >= high)
return;
a = set[low];
while(p < q)
{
while(p < q && set[q] > a)
q--;
if(p < q)set[p++] = set[q];
while(p < q && set[p] < a)
p++;
if(p < q)set[q--] = set[p];
}
set[p] = a;
Qsort(low, p-1);
Qsort(p+1, high);
}

int search(int result, int low, int high)
{
int mid;
while(low <= high)
{
mid = (low + high)/2;
if(result > set[mid])
low = mid+1;
else if(result < set[mid])
high = mid-1;
else
return 1;
}
return 0;
}

[brianfry713]

From uhunt:
Siegrift> for that problem 4 nested loops are sufficient

[Hikari9]

well, as far as optimizations go, you can make up to O(n^3), heck even O(n^2).

O(n^4): brute force
O(n^3): DP - sort all data, make a for-loop for a, b, c, then get maximum a+b+c that is in the set (use hash_map for constant check)
O(n^2): DP - sort all data, store in memo all distinct pairs a+b, then make a reverse for-loop to check if (d-c) exists in memo such that a!=b!=c!=d

i don't know how the O(n^4) algo passed the runtime, but i implemented the O(n^2) algo, which i think is the official solution to the problem

[Samleo]

Try this case
Input :

Code: Select all

4
-3 -3 -3 -9
0

Output :

Code: Select all

-9

The output is wrong I thot? All numbers in the set must be distinct..

[brianfry713]

Yes all elements in the judge's input are distinct.

[Samleo]

I have got WA for this problem a few times.. I use the d-c = a+b algorithm.. Can I hav some datasets to further test the code (all io is correct)?

Code: Select all

#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<cmath>
#include<map>

using namespace std;

#define LOOP(times) for(int(i) = 0;i<times;i++)

typedef vector<int> vi;

typedef set<int> st;
typedef st::iterator sIter;
typedef st::reverse_iterator sRevIter;


typedef map<int,int> mii;
typedef mii::iterator mIter;

int main(){
    int i,a,b;
    int n,x,sum,diff;
    
    st s,soln;
    sIter sit;
    sRevIter srit;
    
    vi S,ab;
       
    mii dc;
    mIter it;
                 
    /*
    freopen("sumsets.in","r",stdin);
    freopen("sumsets.out","w",stdout);
    //*/
    while(scanf("%d",&n)!=EOF){
        if(!n) break;
                
        bool solution = false;
        
        for(i=0;i<n;i++){
            scanf("%d",&x);
            s.insert(x);
            //set will not only sort but remove similar occurences
        }
        
        if(s.size()<4){
             printf("no solution\n");
             s.clear();
             continue;
        }
        
        for(sit=s.begin();sit!=s.end();sit++){
            S.push_back(*sit);
        }   
        
        ab.push_back(S[n-1]+S[0]);
        dc.insert(make_pair(S[n-1]-S[0],S[n-1]));
        
        for(a=0;a<n-1;a++){
            //if(S[a] != S[a+1]){
            sum = S[a]+S[a+1]; //a+b
            diff = S[a+1]-S[a]; //d-c
            ab.push_back(sum);
            dc.insert(make_pair(diff,S[a+1]));
            //}
        }
        
        sort(ab.begin(),ab.end());
        
        for(b=0;b<ab.size();b++){ //Search
            it = dc.find(ab[b]);
            if(it!=dc.end()){ //rejoice
                 //printf("%d",it->second);
                 soln.insert(it->second);
                 solution = true;
                 //break;
            }
        }
        
        if(!solution){
             printf("no solution");
        }
        else{
            srit = soln.rbegin();
            printf("%d",*srit);
        }
        
        printf("\n");
        
        S.clear();
        s.clear();
        ab.clear();
        dc.clear();
        soln.clear();
    }

    return 0;
}

[brianfry713]

That code won't compile