Codeforces #266 (Div 2) – Number of Ways

Problem link : http://codeforces.com/contest/466/problem/C

Logic:

Let sum of elements in array = S

If S%3==0 then the array cannot be divided into 3 equal parts . So print zero.

Otherwise,

Have a count array where count[i]=number of subarrays in arr[i…n] whose sum is equal to S/3

Now iterate from the first element and add elements to a variable called “temp”

At iteration i, if temp==S/3 then we have found first part of the “3 equal parts array”.count[i+2] will give you the number of ways the rest of the 2 equal parts of the array could be arranged.

The logic here is “if arr[0…i] sums upto S/3 and if arr[i+j…n] sums upto S/3 then inbetween elements arr[i+1…j-1] will also sum upto S/3 ” here j varies from 2 to n-2.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 10000005
	typedef long long int ll;
	int arr[1000005];
	int count1[1000005];
	int main(){
	int n;
	cin>>n;
	ll s=0;
	REP(i,n){
	cin>>arr[i];
	s+=arr[i];
	}
	if(s%3!=0){
	cout<<"0";
	return 0;
	}
	ll sum=s/3;
	ll temp=0;
	for(int i=n-1;i>=0;i--){
	temp+=arr[i];
	if(temp==sum){
	count1[i]+=1;
	}
	}
	for(int i=n-2;i>=0;i--){
	count1[i]+=count1[i+1];
	}
	temp=0;
	ll ans=0;
	for(int i=0;i+2<n;i++){
	temp+=arr[i];
	if(temp==sum){
	ans+=count1[i+2];
	}
	}
	cout<<ans;
	}

view raw TheNumberOfWays.cpp hosted with ❤ by GitHub