C++

Forum

 
Sum of numbers

Pen72 (74)
Any idea to solve this problem in a more efficient way other than comparing it one after another?
------------------------------------------------------------------------------------------------
You’re given n arrays, each array has m integers. There are m^n ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the m smallest sums among them.

Input Format

The first line contains 2 integers n,m .

the following n lines contains m positive integers in each array.


Sample Input 0

2 6
2 3 6 7 8 9
10 10 11 15 16 16
Sample Output 0

12 12 13 13 13 14

Last edited on
jonnin (11437)
about as fast as it gets is to do a basic find the smallest on each array as it is input and keep a running total of that. By the time all the data is input, you have your answer.
that would net you 2 and 10 for your input, -> 12 is the smallest sum.
do you need all those other sums? If so, you may have to sort each input array, but its the same idea. there, you sort the input and add each (up to m) to a container of results, the [0] is the smallest overall, and so on.
Last edited on
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdlib>
using namespace std;


struct Test
{
   int value;
   vector<int> columns;
   bool operator < ( const Test &other ) const
   { 
      if ( value != other.value ) return value < other.value;
      for ( int i = 0; i < columns.size(); i++ ) if ( columns[i] != other.columns[i] ) return columns[i] < other.columns[i];
      return false;
   }
};


int main()
{
   int n, m;
   cin >> n >> m;
   vector< vector<int> > A( n, vector<int>( m ) );

   // Read data
   for ( int i = 0; i < n; i++ )
   {
      for ( int j = 0; j < m; j++ ) cin >> A[i][j];
//    sort( A[i].begin(), A[i].end() );                    // uncomment if data needs sorting
   }

   // First sum
   int sum = 0;
   for ( int i = 0; i < n; i++ ) sum += A[i][0];
   cout << sum << ' ';
   if ( m == 1 ) exit(0);
   
   // Set up first n tests
   set<Test> S;
   for ( int i = 0; i < n; i++ )
   {
      vector<int> V(n,0);   V[i] = 1;
      S.insert( { sum + A[i][1] - A[i][0], V } );
   }

   // At each stage, remove "best" test and replace in set by its immediate distinct followers
   for ( int j = 1; j < m - 1; j++ )
   {
      Test t = *S.begin();
      cout << t.value << ' ';
      S.erase( S.begin() );
      for ( int i = 0; i < n; i++ )
      {
         vector<int> V = t.columns;   V[i]++;
         S.insert( { t.value + A[i][V[i]] - A[i][V[i]-1], V } );
      }
   }
   cout << S.begin()->value << '\n';
}

Last edited on
Topic archived. No new replies allowed.