ARRP - Editorial




Div1, Div2

Author: Misha Chorniy
Tester: Lewin Gan
Editorialist: Adarsh Kumar




Sieve of Eratosthenes


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.


Let $S* = \sum_{j=1}^{i} A[j]$. Let's make some observation here now:
  • All the values of $S*$ 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.


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:



Setter's solution
Tester's solution


Can anyone explain this through an example?


Let’s consider the first example: 1 4 2 3 5. The array of prefix sums(S) will look like 1 5 7 10 15. Let’s make fractions from it: 1/15 5/15 7/15 10/15 15/15. Let’s make them irreducible 1/15 1/3 7/15 2/3 1/1. Now consider only denominators which are <= N=5(only they will affect the answer), i.e. (3)1/3 (3)2/3 (1)1/1. Now, for every K=1…N find the number of denominators which are divisors of K. K=1(1), K=2(1), K=3(3), K=4(1), K=5(1). We’re interested only in those values of K for which this number is equal to K, i.e 1 and 3.


Thanks for the explanation.

Can you please give me the editorial link of TRS ?

#5 - all editorials - TRS