PROBLEM LINK:
Author: Misha Chorniy
Tester: Lewin Gan
Editorialist: Adarsh Kumar
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Sieve of Eratosthenes
PROBLEM:
You are given an array A with size N. For each K between 1 and N (inclusive), find out if it is possible to partition (split) the array A into K contiguous subarrays such that the sum of elements within each of these subarrays is the same.
EXPLANATION:
Let S[i] = \sum_{j=1}^{i} A[j]. Let’s make some observation here now:
- All the values of S[i] will be distinct because all A[j] > 0.
- S[N] must be divisible by K if we want to partition the array into K contiguous part.
- Sum of each part will be equal to \frac{S[N]}{K} = X (say).
- For every multiple of X i.e. for every X*i ∀ 1 \le i \le K there must exist some j such that S[j]=X.i.
Iterate over all the divisors of S[N] that is \le N. For every such divisor K we will check if all of the multiples of \frac{S[N]}{K} are present in the prefix sum array or not. Let’s make a cnt[] array which stores how many multiples of \frac{S[N]}{K} are present in the prefix sum array in cnt[K]. Any K will be good iff cnt[K]==K.
From the above observations, S[j]=\frac{S[N]}{K}.i which means \frac{S[j]}{S[N]}=\frac{i}{K}.
We are going to iterate over S[j], compute the irreducible fraction \frac{S[j]}{S[N]} =\frac{P}{Q}. Now we need to increase cnt[Q.i] by 1 for all those Q.i that are divisors of S[N] and \le N, because for every Q.i you get a distinct P.i because of the property that all prefix sums are distinct.
Doing the later step for every j can be costly. Hence, we will use sieve for this purpose. When iterating over j, just increment cnt[Q] by 1 if Q \le N. When done iterating over j, you can run a sieve-like algorithm for updating the multiples of every cnt[Q.i] which will cost us O(NlogN).
You can refer to the setter’s solution for implementation details of this approach.
ALTERNATE SOLUTION:
Based on above observations, we will try to devise our solution. Iterate over all the divisors of S[N] that is \le N. For every such divisor K we will check if all of the multiples of \frac{S[N]}{K} are present in the prefix sum array or not. If all of the multiples are present in the prefix sum array then this K is good. When doing naively, for every K it will require O(K.logN) operations to check if every multiple of K is present in prefix sum array. But creating good test data which costs O(K.logN) for every K is nearly impossible. Hence, in practice, this approach will run a lot fast than expected. Tester’s solution uses this idea. You can refer to it for the implementation details.
Time Complexity:
O(NlogN)