10125 - Sumsets

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

Moderator: Board moderators

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10125 - Sumsets

Post by Articuno » Sun Jan 04, 2009 10:50 pm

I don't think a O(n^4) algo can pass the time limit. Try something better.
May be tomorrow is a better day............ :)

ergysr
New poster
Posts: 9
Joined: Sun Oct 07, 2007 1:25 pm

Re: 10125 - Sumsets

Post by ergysr » Wed Jan 14, 2009 5:29 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10125 - Sumsets

Post by mf » Thu Jan 15, 2009 4:31 am

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 10125 - Sumsets

Post by Sedefcho » Sun Jan 25, 2009 6:10 pm

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
New poster
Posts: 2
Joined: Sat Nov 22, 2008 10:45 am

Re: 10125 - Sumsets

Post by chchwy » Thu Mar 18, 2010 3:18 am

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
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 10125 - Sumsets

Post by sazzadcsedu » Wed Apr 21, 2010 7:38 am

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.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

mostafiz93
New poster
Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

Re: 10125 - Sumsets

Post by mostafiz93 » Sun Apr 29, 2012 9:08 pm

Articuno wrote: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
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: 10125 - Sumsets

Post by @li_kuet » Fri Jul 06, 2012 10:07 am

Try this case :D
Input :

Code: Select all

4
-3 -3 -3 -9
0
Output :

Code: Select all

-9

hpjhc
New poster
Posts: 17
Joined: Wed Jun 26, 2013 10:35 am

10125 - Sumsets WA

Post by hpjhc » Fri Sep 13, 2013 6:12 pm

#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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10125 - Sumsets WA

Post by brianfry713 » Fri Sep 13, 2013 9:20 pm

From uhunt:
Siegrift> for that problem 4 nested loops are sufficient
Check input and AC output for thousands of problems on uDebug!

Hikari9
New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

Re: 10125 - Sumsets

Post by Hikari9 » Fri Sep 20, 2013 9:17 pm

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 :D

Samleo
New poster
Posts: 11
Joined: Mon Dec 03, 2012 2:39 pm

Re: 10125 - Sumsets

Post by Samleo » Mon Oct 28, 2013 4:07 pm

@li_kuet wrote:Try this case :D
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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10125 - Sumsets

Post by brianfry713 » Mon Oct 28, 2013 8:11 pm

Yes all elements in the judge's input are distinct.
Check input and AC output for thousands of problems on uDebug!

Samleo
New poster
Posts: 11
Joined: Mon Dec 03, 2012 2:39 pm

Why WA? Any test cases?

Post by Samleo » Wed Oct 30, 2013 9:01 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10125 - Sumsets

Post by brianfry713 » Thu Oct 31, 2013 10:49 pm

That code won't compile
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”