C++

Forum

 
Can't seem to solve this

Kalcor (188)
You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.


Input
The first line contains integer n (1 ≤ n ≤ 5·10^5), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤  10^9) — the elements of array a.

Output
Print a single integer — the number of ways to split the array into three parts with the same sum.

Examples
input
5
1 2 3 0 3
output
2
input
4
0 1 -1 0
output
1
input
2
4 1
output
0


Can't find a way around solving this question, if someone could give a hint or whatever else would be great ^^
Last edited on
lastchance (6980)
Attempted answer by recursion - definitely needs another pair of eyes to check it, as there are a lot of pathological cases with 0's and negative numbers in.

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
 
#include <iostream>
#include <numeric>
using namespace std;

//======================================================================

int split( int *a, int N, int npart, int value ) // number of ways of splitting a[] of size N into npart partitions of sum value
{
   if ( npart <= 0 || N < npart ) return 0;      // invalid cases

   int sum = accumulate( a, a + N, 0 );          // find sum of array
   if ( npart == 1 && sum == value ) return 1;   // precise match (end of recursion)
   if ( sum % npart != 0 ) return 0;             // can't split unless a suitable multiple

   // Find number of places you can place first divider and split the rest (recursion)
   int result = 0;
   int rollingSum = 0;
   for ( int i = 0; i < N - 1; i++ )
   {
      rollingSum += a[i];
      if ( rollingSum == value ) result += split( a + i + 1, N - ( i + 1 ), npart - 1, value );    // RECURSION
   }
   return result;
}

//======================================================================

int trisect( int *a, int N )                     // number of ways of TRISECTING
{
   if ( N < 3 ) return 0;                        // need enough elements

   int sum = accumulate( a, a + N, 0 );          // find sum of array
   if ( sum % 3 != 0 ) return 0;                 // can't trisect unless a multiple of 3

   return split( a, N, 3, sum / 3 );
}

//======================================================================

int main()
{
   int N;
   cout << "How many numbers in your array? ";
   cin >> N;

   int *a = new int[N];
   cout << "Enter " << N << " integers, separated by spaces: ";
   for ( int i = 0; i < N; i++ ) cin >> a[i];

   cout << "Number of tri-partitions = " << trisect( a, N );

   delete [] a;
}


How many numbers in your array? 5
Enter 5 integers, separated by spaces: 1 2 3 0 3
Number of tri-partitions = 2


How many numbers in your array? 4
Enter 4 integers, separated by spaces: 0 1 -1 0
Number of tri-partitions = 1


How many numbers in your array? 2
Enter 2 integers, separated by spaces: 4 1
Number of tri-partitions = 0
Last edited on
Kalcor (188)
@lastchance, amazing solution but only 1 problem...It exceeded the 2 second time limit of the question :/

Test case was
N: 100000
and array elements are:
1 0 0 0 0 0 0 0 0 0 0 0 0............till elements are finished, I mean I hope it's all zeros there is no place I can see the rest of the array but what I saw up to 100 elements were all 0s
Last edited on
lastchance (6980)
OK, try this one. It avoids calculating partial sums multiple times.

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
 
#include <iostream>
using namespace std;

int main()
{
   // Get data (replace with file reads if desired)
   int N;
   cout << "How many numbers in your array? ";
   cin >> N;

   int *a = new int[N];
   int *b = new int[N];
   cout << "Enter " << N << " integers, separated by spaces: ";
   for ( int i = 0; i < N; i++ ) cin >> a[i];

   // Compute partial sums
   b[0] = a[0];
   for ( int i = 1; i < N; i++ ) b[i] = b[i-1] + a[i];

   int sum = b[N-1];
   int third = sum / 3;
   int result = 0;

   // Partition into thirds
   if ( 3 * third == sum )             // only solutions if sum is a multiple of 3
   {
      int twoThirds = third + third;
      for ( int i = 0; i < N - 2; i++ )
      {
         if ( b[i] == third )          // if first partition found then search forward for second
         {
            for ( int j = i + 1; j < N - 1; j++ )
            {
               if ( b[j] == twoThirds ) result++;
            }
         }
      }
   }

   cout << result << endl;

   delete [] a;
   delete [] b;
}

Last edited on
lastchance (6980)
Another attempt - less loops. File reads included this time.

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
 
#include <iostream>
#include <fstream>
using namespace std;

//======================================================================

int main()
{
   int N;

   // Get data (from file)
   ifstream in( "infile.dat" );
   in >> N;
   int *a = new int[N];
   for ( int i = 0; i < N; i++ ) in >> a[i];
   in.close();

   // Compute partial sums
   int *b = new int[N];
   b[0] = a[0];
   for ( int i = 1; i < N; i++ ) b[i] = b[i-1] + a[i];

   int sum = b[N-1];
   int third = sum / 3;
   int result = 0;

   // Partition into thirds
   if ( 3 * third == sum )    
   {
      int numthird = 0;
      int twoThirds = third + third;
      for ( int i = 0; i < N - 1; i++ )
      {
         if ( b[i] == twoThirds ) result += numthird;
         if ( b[i] == third ) numthird++;
      }
   }

   cout << result << endl;

   delete [] a;
   delete [] b;
}

Last edited on
Kalcor (188)
@lastchance, sadly gave a Time limit exceeded error on the same test case :/
ne555 (10692)
¿the last one too? it's O(n), optimum.
lastchance (6980)
@Kalcor

I tried my codes on a file looking like
100000
1 (99997 lots of 0) 1 1
(so that it has some partitions). The first two codes admittedly took some time. The third one looked almost instantaneous - certainly well under 2 seconds.
Kalcor (188)
@lastchance, i cant test that last solution on their systems they dont support input files. q.q :(
lastchance (6980)
@lastchance, i cant test that last solution on their systems they dont support input files. q.q :(


Hmm, and all that thinking I had to do ... OK: revert to console input then.

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
 
#include <iostream>
using namespace std;

int main()
{
   // Get data
   int N;
   cout << "How many numbers in your array? ";
   cin >> N;

   int *a = new int[N];
   cout << "Enter " << N << " integers, separated by spaces: ";
   for ( int i = 0; i < N; i++ ) cin >> a[i];

   // Compute partial sums
   int *b = new int[N];
   b[0] = a[0];
   for ( int i = 1; i < N; i++ ) b[i] = b[i-1] + a[i];

   int sum = b[N-1];
   int third = sum / 3;
   int result = 0;

   // Partition into thirds
   if ( 3 * third == sum )    
   {
      int numthird = 0;
      int twoThirds = third + third;
      for ( int i = 0; i < N - 1; i++ )
      {
         if ( b[i] == twoThirds ) result += numthird;
         if ( b[i] == third ) numthird++;
      }
   }
   delete [] b;

   cout << result << endl;

   delete [] a;
}
ne555 (10692)
> i cant test that last solution on their systems they dont support input files.
data input is independent of the algorithm.
even if you don't know how to do it (¿at this stage?) you've got two other examples to copy from


> Hmm, and all that thinking I had to do ...
¿so why are you doing their homework?
Kalcor (188)
@ne555, srs lol ure literally the only rude person i encountered on this website, just leave the man do what he wants lol he's helped me before and i am glad he doesn't trashtalk me like that, we all learn, you were definitely once a trash programmer before you became something, just let everyone learn their way, and for your info.. its not a homework.. these are contest problems that I solve everyday to practice competitive programming.
Kalcor (188)
@lastchance, yes that one got accepted. I'll trace it correctly to check what was done. thanks buddy, lots of love!

EDIT: if you don't mind, can you comment your code for some demonstration of what is going on like the first one you sent?
Last edited on
lastchance (6980)
@Kalcor, I'll try to explain the code that got accepted, although the technique is probably easier to see on the not-so-fast second code.

General approach - you need 3 equal partitions, so if 'sum' is the total of all elements, then each partition must individually total a 'third' of this, whilst 'sum' itself must be a multiple of 3. I basically try to count the number of ways of placing 'third', 'twoThirds' at appropriate points in the array.

Lines 6-13: enter the integers into an array; fairly standard.

Lines 15-18: calculate the 'partial sums'. These are b0=a0, b1=a0+a1, b2=a0+a1+a2 etc.; i.e. they are the totals up to that point in the array - and I'm going to need to find where they are third, twoThirds.

Lines 20-22: find the sum of the whole array (it will be the last partial sum in b[]) and one third of this. 'result' is going to store my tally of possible combinations.

The equivalent of lines 24-34 was actually easier to see in the earlier code, but that was O(N2) operations, hence slower. I need to do all the work in a single loop, not a nested one.

Line 25 just checks that there are any valid partitions - 'third' was found by integer division, so this is just making sure that the 'sum' is a multiple of 3.

In lines 29 - 33 I'm trying to find places to end the first and second partitions (by comparing with the required partial sum b[i] at these points). Variable 'numthird' tallies the number of first-partition ends up to this point. Thus, if I check first for the end of the second partition (line 31), then all the numthird possibilities for placing the end of the first partition prior to here will give a valid and distinct case that I can add to 'result'. I then check for an end of a first partition on line 32 and increment numthird if necessary. Note that, for the single awkward case where there are negative and positive numbers making sum = 0, I mustn't count a second partition and a first partition at the same point. Thus, the contents of line 31 must precede line 32 and it is definitely an 'if' and not an 'else if' on line 32.

Might be easiest if you sketched out some squares on paper and tried some particular examples. Actually, the ones with lots of 0's in show up the nuances of the problem. Try something like
1 0 0 0 0 1 1


With regards to homework or otherwise, I was fairly sure that this was a "competition" problem and not assessed work: we get a lot on the forum and they are good for lively debate and quite educational: I've had algorithms for them explained to me in the past - by @Keskiverto and @JLBorges I think - so I've learnt as much as the original posters. @ne55's comment in that respect wasn't accurate, but it was only in response to the slightly flippant remark of my own.

Actually @ne55's earlier comment - about the final code being O(N) was highly pertinent: it's what made the algorithm so fast compared with one involving nested loops which would be O(N2) - roughly proportional to the number of times that the inner loop operations will run. I'm only just beginning to move on from an innate sense of what constitutes a fast algorithm and I was secretly quite pleased that he had looked through the code and spotted that. With hindsight - a wonderful thing - my first two codes were pretty lousy, although in terms of partitioning they were a bit easier to explain.

Here endeth the essay!


Kalcor (188)
@lastchance, I'd like to ask you a late question but.. what exactly is a partial sum ?

1
2
3
 
int *b = new int[N];
   b[0] = a[0];
   for ( int i = 1; i < N; i++ ) b[i] = b[i-1] + a[i];


Lines 15-18: calculate the 'partial sums'. These are b0=a0, b1=a0+a1, b2=a0+a1+a2 etc.; i.e. they are the totals up to that point in the array - and I'm going to need to find where they are third, twoThirds.


It was this part in your code aswell
Last edited on
lastchance (6980)
If you have a sequence of values a0, a1, a2, a3, a4, ... etc.
then the partial sums are the sums up to each point in the sequence.

e.g., up to a3 the partial sum is
b3 = a0 + a1 + a2 + a3

You don't have to calculate them from scratch each time: e.g.
b3 = (a0 + a1 + a2) + a3 = b2 + a3
which is what is being done in the line
for ( int i = 1; i < N; i++ ) b[i] = b[i-1] + a[i];
There's actually a standard-library function which will compute the partial sums for you, if you don't want to write this loop.

It is these intermediate/partial sums that have to match the third, twoThirds, points in the partitioning.
Kalcor (188)
Ah.. I get it now.. thanks alot!
Topic archived. No new replies allowed.