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;
}