REMADJ-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Author: Utkarsh Gupta
Tester: Tejas Pandey
Editorialist: Daanish Mahajan

DIFFICULTY:

Easy Medium

PREREQUISITES:

Prefix sums, \mathcal{O}(N^{1/2}) factorization

PROBLEM:

You are given an array A of length N.
You can perform the following operation on the array, as long as it has more than one element:

  • Choose any two adjacent elements, remove them from the array and insert their sum at that position.

Print the minimum number of operations to be applied on array A such that all the elements in the resulting array are equal.

EXPLANATION:

Hint 1

Only consecutive elements are getting merged which means elements of the final array can be visualized as the sum of elements of some subarray of the original array A.

Hint 2
  • The length of the final array is some factor of the sum of the array.
  • The value of the final array is some factor of the sum of the array.
Solution

Suppose B is the final array where each element of B = x and size of B = y.

This means the original array A can be partitioned into subarrays [1 \ldots P_1], [P_1 + 1, \ldots P_2], \ldots, [P_{y - 2} + 1, \ldots, P_{y - 1}], [P_{y - 1} + 1, N] (P_i < P_{i + 1}, \forall i \in [1, y - 2] and P_1 \ge 1 and P_{y - 1} \lt N) where each of these subarray sums to x.

Suppose sum of elements of A = S and the prefix sum array of A is C.

Also, the sum of elements of B is equal to the sum of elements of A, implying:
x \cdot y = S.

This means x is a factor of S. So now for all factors of S, we check whether a particular factor is valid, i.e, there exists a sequence of moves such that the final array B has all elements equal to that factor and take minimum over the count of operations required over all valid factors.

Implementation

Initialize answer to N - 1 since one of the valid options is to merge all the elements into a single element.
Now we iterate over the factors (x) of S and check whether there exists indices i_1 \lt i_2, \ldots \lt i_{y - 2} \lt i_{y - 1} in C (where y = \frac{S}{x}) such that C_{i_c} = c \cdot x, \forall c \in [1, y - 1], and if it does, update answer = min(answer, N - y). This takes \mathcal{O}(N) time for each factor.

Corner case

For S = 0, answer = N - (count of indices have value equal to $0$ in $P$).

COMPLEXITY ANALYSIS:

Complexity = \mathcal{O}(count of factors of S \cdot checking whether a factor is valid).
Since maximum value of S = N \cdot maximum value of A_i = \mathcal{O}(N^2) and maximum number of factors of a number X = \mathcal{O}(X^{1/3}) and we are we can validate every factor in \mathcal{O}(N), the above expression turns out to be \mathcal{O}(N^{5/3}).

SOLUTIONS:

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
void solve()
{
    ll n;
    cin>>n;
    ll arr[n+1]={0};
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    if(sum==0)
    {
        ll tmp=0;
        ll ans=n;
        for(int i=1;i<=n;i++)
        {
            tmp+=arr[i];
            if(tmp==0)
                ans--;
        }
        cout<<ans<<'\n';
        return;
    }
    if(sum<0)
    {
        for(int i=1;i<=n;i++)
            arr[i]*=-1;
        sum*=-1;
    }
    ll out=n-1;
    for(int i=1;i*i<=sum;i++)
    {
        if((sum%i)!=0)
            continue;
        {
            int x=i;
            ll tmp=0;
            ll ans=n;
            int flag=1;
            int cnt=0;
            for(int j=1;j<=n;j++)
            {
                tmp+=arr[j];
                if(tmp==x)
                {
                    ans--;
                    cnt++;
                    tmp=0;
                }
            }
            if(cnt*x>=sum)
                out=min(out,n-sum/x);
        }
        {
            int x=sum/i;
            ll tmp=0;
            ll ans=n;
            int flag=1;
            int cnt=0;
            for(int j=1;j<=n;j++)
            {
                tmp+=arr[j];
                if(tmp==x)
                {
                    ans--;
                    cnt++;
                    tmp=0;
                }
            }
            if(cnt*x>=sum)
                out=min(out,n-sum/x);
        }
    }
    cout<<out<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int t;
    cin>>t;
    while(t--)
        solve();
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--) {
		int n;
		cin >> n;
		int a[n];
		for(int i = 0; i < n; i++) cin >> a[i];
		ll sm = 0;
	    ll pa[n];
	    pa[0] = a[0];
	    for(int i = 1; i < n; i++) pa[i] = pa[i - 1] + a[i];
	    sm = pa[n - 1];
	    if(!sm) {
	        int blocks = 0;
	        for(int i = 0; i < n; i++)
	            blocks += (!pa[i]);
	        cout << n - blocks << "\n";
	        continue;
	    }
	    int ans = n - 1;
	    int absm = abs(sm);
	    for(int i = 1; i <= sqrt(absm); i++) {
	        if(absm%i == 0) {
	            ll tf = sm/i;
	            ll now = tf;
	            int ok = 0;
	            for(int j = 0; j < n; j++) {
	                if(pa[j] == now) {
	                    if(now == sm) ok = 1;
	                    now += tf;
	                }
	            }
	            if(ok) ans = min(ans, n - i);
	            if(absm/i != i) {
	                ll tf = sm/(absm/i);
	                ll now = tf;
	                int ok = 0;
	                for(int j = 0; j < n; j++) {
	                    if(pa[j] == now) {
	                        if(now == sm) ok = 1;
	                        now += tf;
	                    }
	                }
	                if(ok) ans = min(ans, (int)(n - absm/i));
	            }
	        }
	    }
	    cout << ans << "\n";
	}
	return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int maxn = 3e4 + 10;
int n;
int a[maxn], ps[maxn];
int cal(int x){
	int mul = 1;
	for(int i = 1; i <= n && mul < ps[n] / x; i++){
		if(ps[i] == mul * x){
			mul++;
		}
	}
	if(mul != ps[n] / x)mul = 1;
	return n - mul;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); 
	int t; cin >> t;
	while(t--){
		cin >> n;
		int cnt0 = 0;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			ps[i] = ps[i - 1] + a[i];
			cnt0 += ps[i] == 0;
		}
		int ans = ps[n] ? n - 1 : n - cnt0;
		for(int i = 1; i * i <= abs(ps[n]); i++){
			if(ps[n] % i)continue;
			ans = min(ans, min(cal(i * (ps[n] / abs(ps[n]))), cal(ps[n] / i)));
		}
		cout << ans << endl;
	}
	return 0;
}
2 Likes

Can you please explain why my solution is showing SIGFPE Run time error only for 1st subtask and giving right answer for all other 12 tasks.
Solution : solution

1 Like

Consider Case-

1
7
1 1 1 3 -2 2 -4

Correct ans- 5

7 Likes

Can you please explain why my solution is showing WA for 1st subtask only?

My code: Solution: 57783955 | CodeChef

2 Likes
3 Likes

My code is giving output 5 is it correct as my code is also showing wrong answer on 1st test case only

1 Like

giving WA in 1st testCase ,please give any TestCase for which i’m getting WA.
https://www.codechef.com/viewsolution/57947972

5 is correct for that case. Link to your code?

1 Like

2 0 8 -4 -2 2 2 2 0
try for this one
your code is working fine for whatever testcases i tried for my code

1 Like

Here’s the link for my code:
https://www.codechef.com/viewsolution/57900183

Your code doesn’t print anything on that input.

1 Like

getting 8 , is it correct?

sir can u explain how 5 is the correct answer for this case…?

I am getting WA only for test case #1. Here is the link for code: Solution: 57951338 | CodeChef. Can someone provide the case for which it is failing.

1 2 3 -2 2 -4
1 5 -2 2 -4
1 3 2 -4
1 5 -4
1 1
2 Likes

Not able to find any testcase where my code is failing
Can anyone please point out the testcase where it is giving unexpected output

https://www.codechef.com/viewsolution/57879755

similar but smaller corner case
1
4
1 1 1 -1
correct ans: 2

2 Likes

On codechef ide it isn’t printing anything I was using Leetcode playground there it printed 5. Thanks for pointing it out. Let me check what’s the error.

Thank you @jagdish_t19 for the testcase
1
4
1 1 1 -1

1 Like