set

[biwkina]

how can i get sum of any two members in a set?

[bird1234]

give some details about your problem

[biwkina]

input a sequence and you find the smallest number which cant be the sum of sequences members, for example. given sequence: 1 2 5 6 758 - answer is 4

[48T7M4Gy]

http://www.cplusplus.com/reference/set/set/

As a start I would look at the properties of a <set>, the elements are accessible as you can expect so summing any two would be easy.

And then I might (likely) have a look at <algorithm> ... permutations
http://www.cplusplus.com/reference/algorithm/

[biwkina]

For a given set consisting of positive integers, determine the smallest positive number,unimaginable as the sum of the elements of any subset of the set.

Input

The input file contains all the numbers that make up a given set.Each of them does not exceed 1015, the total amount does not exceed 10000,and their sum is guaranteed to not exceed 264-1.

Output

In the output file to bring a single number- the answer of the problem.


you can do this?

[lastchance]

There really has to be a better way of doing this.

This recursive version sort of works, but it can take a staggeringly long time for some input data.

EDIT: superseded by the code in a later post.

Input data goes in file data.txt

#include <iostream>
#include <fstream>
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

//----------------------------------------------------------------------

void readData( vector<int> &vec )
{
   int value;
   ifstream in( "data.txt" );
   while( in >> value ) vec.push_back( value );
   in.close();
}

//----------------------------------------------------------------------

void show( vector<int> &vec )
{
   for ( int i = 0; i < vec.size(); i++ ) cout << vec[i] << "  ";
   cout << endl;
}

//----------------------------------------------------------------------

bool isSum( int N, vector<int> &v )
{ 
   int Nminus;
   vector<int>::iterator iter, elem, last;

   // Quick tests
   if ( N == 0        ) return true ;
   if ( v.size() == 0 ) return false;
   if ( N == v[0]     ) return true ;

   // Find the set of elements of v that are less than or equal to N
   iter = v.begin();
   while( iter != v.end() && *iter <= N ) iter++;                       
    
   // For each element test reduced (N minus element) against the rest of the lower vector
   last = iter - 1;
   for ( elem = v.begin(); elem != iter; elem++ )
   {
      Nminus = N - *elem;
      if ( Nminus == 0        ) return true ;
      if ( Nminus < v.front() ) return false;

      while( last != v.begin() && *last > Nminus ) last--;
      vector<int> s( v.begin(), last + 1 );
      if ( last >= elem ) s.erase( s.begin() + ( elem - v.begin() ) );

      if ( isSum( Nminus, s ) ) return true;                         // recursive function call
   }
   return false;
}

//----------------------------------------------------------------------

int main()
{
   vector<int> myData;

   readData( myData );
   sort( myData.begin(), myData.end() );
   int sum = accumulate( myData.begin(), myData.end(), 0 );
   cout << "Sorted data: ";  show( myData );
   cout << "Total sum:   ";  cout << sum << endl;

   int N = 1;
   while( N >= myData[0] && N <= sum )
   {
      cout << "Testing N = " << N << endl;
      if ( !isSum( N, myData ) ) break;
      N++;
   }

   cout << "Minimum number not composable from the set is " << N;
}

//---------------------------------------------------------------------- 

EDIT: superseded by the code in a later post.

[biwkina]

time limit 1 second

[gunnerfunner]

hello OP, a thank you to lastchance would have been nice instead of your next 'set' of requirements

[lastchance]

No, I admit, my algorithm is not good. It works OK for

1 2 5 6 7 5 8

and very badly for

1 2 5 6 7 5 8 56 23 4 2 19

The challenge is apparently at
https://www.e-olymp.com/en/problems/2426
although there are some very dubious translations into English there.

There must be much better solutions; this thread is very much still open.

[lastchance]

Try this one instead.

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

//----------------------------------------------------------------------

int readData( vector<int> &data )
{
   int value;
   int sum = 0;
   ifstream in( "data.txt" );
   while( in >> value ) 
   {
      data.push_back( value );
      sum += value;
   }
   in.close();
   return sum;
}

//----------------------------------------------------------------------

void show( vector<int> &data )
{
   vector<int>::iterator iter;
   for ( iter = data.begin(); iter != data.end(); iter++ ) cout << *iter << "  ";
   cout << endl;
}

//----------------------------------------------------------------------

int main()
{
   vector<int> myData;
   int i, j, item;

   int total = readData( myData );
   sort( myData.begin(), myData.end() );               // sort data (helps efficiency later)
// cout << "Sorted data: ";  show( myData );           // un-comment these two lines while debugging
// cout << "Total:       ";  cout << total << endl;    //    

   bool *sumData = new bool[total+1];                  // sumData[i] being true will indicate i is a possible sum
   fill( sumData, sumData + total + 1, false );

   int sumMax = 0;                                     // sumMax contains the maximum sum so far, and limits range
   for ( i = 0; i < myData.size(); i++ )
   {
      item = myData[i];                                // the next data point
      for ( j = 1; j <= sumMax; j++ )                  // loop round, adding previous sums to this one
      {
         if ( j < item && !sumData[j] )                    // if data is sorted, this will never be a sum, so can stop
         {
            cout << "Answer: " << j;
            exit( 0 );
         }
         if ( sumData[j] ) sumData[item+j] = true;     // j was a previous sum, so item+j will be a new one 
      }
      sumData[item] = true;                            // also add this isolated value to set of possible sums
      sumMax += item;                                  // extend the maximum sum so far to include the new item 
   }

   j = 1;
   while ( j <= total && sumData[j] ) j++;

   cout << "Answer: " << j;
}

//---------------------------------------------------------------------- 

[48T7M4Gy]

#include <iostream>
#include <algorithm>

int main () {
    
    int max_sum = 0;
    int min_sum = 9000000;
    
    int array[] = {1,2,5,6,758};
    //int array[] = {1, 2, 5, 6, 7, 5, 8, 15, 56, 14, 24, 4, 2, 19};
    int length = sizeof(array)/sizeof(int);
    
    std::sort(array, array + length);
    
    int** sum_array = new int *[length];
    for(int i = 0; i < length; ++i)
        sum_array[i] = new int[length];
    
    for (int row = 0; row < length; row++)
    {
        for( int col = 0; col < length; col++)
        {
            sum_array[row][col] = 0;
        }
    }
    
    for (int row = 0; row < length; row++)
    {
        for( int col = 0; col < length; col++)
        {
            if( row != col)
            {
                sum_array[row][col] = array[row] + array[col];
                
                if ( sum_array[row][col]  > max_sum )
                    max_sum = sum_array[row][col];
                
                if ( sum_array[row][col]  < min_sum )
                    min_sum = sum_array[row][col];
            }
        }
    }
    
    int* sequence_array = new int[max_sum];
    
    for (int row = 0; row < length; row++)
    {
        for( int col = 0; col < length; col++)
        {
            sequence_array[sum_array[row][col]] = 1;
        }
    }
    
    for (int i = min_sum; i <= max_sum; i++)
    {
        if (sequence_array[i] == 0 )
        {
            std::cout << i << " <-- FIRST ... QED\n";
            break;
        }
    }
    
    for(int i = 0; i < length; ++i)
        delete [] sum_array[i];
    delete [] sum_array;
    
    delete [] sequence_array;
    
    return 0;
}

4 <-- FIRST ... QED
Program ended with exit code: 0

[biwkina]

thanks guys for working hard, but try to do this https://www.e-olymp.com/en/contests/2573/problems/20559

[biwkina]

#lastchance your program is working 50 % it has runtime error end some mistakes too, unfortunately i cant resolve this, i don't know enough

[lastchance]

Hello Biwkina

Can you give me an example of the data.txt file which is not working with my SECOND code, please. Make sure that there are only integer numbers in there.

Data file

1 2 5 6 7 5 8

gives answer 4.

Data file

1 2 5 6 7 5 8 56 23 4 2 19

gives answer 139 (one more than the sum of all numbers).

Data file

10 20 50 6 7 5 8 56 230 4 27 19

gives answer 1 (because all numbers are bigger than 1).

These are all correct (I think) and correspond to the different types of scenario in input data. I don't cover the very large integers envisaged in your competition, I'm afraid, but that would be easily fixed.

[biwkina]

i changed int to long long and there were just time error

[lastchance]

You could probably go as far as unsigned long long.

What does a "time error" mean? (Other than it took a long time!) How many numbers were there in your data file (and can I find them on the web anywhere?)

[biwkina]

https://www.e-olymp.com/en/problems/2426 see this link register and you will show how i am working. you can compile your code and see the result of your program

[lastchance]

I think I'll take your word for it, biwkina! I think there are far better coders than I on that site.

Reading disk files can be a comparatively slow operation. You might also be able to improve the vector operation by reserving some space in advance, rather than just relying on push_back to resize the array.

[48T7M4Gy]

int array[] = {10,20,50,6,7,5,8,56,230,4,27,19};

19  <-- FIRST ... QED

[48T7M4Gy]

int array[] = {1,2,5,6,7,5,8,56,23,4,2,19};

16    <-- FIRST ... QED