You are not logged in. Please login at www.codechef.com to post your questions!

×

ARRP - Editorial

0
1

PROBLEM LINK:

Div1, Div2
Practice

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)$

AUTHOR'S AND TESTER'S SOLUTIONS

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 02 Apr '18, 15:56

adkroxx's gravatar image

6★adkroxx
306719
accept rate: 7%

edited 05 Apr '18, 17:21

admin's gravatar image

0★admin ♦♦
19.7k350498541


Can anyone explain this through an example?

link

answered 08 Apr '18, 23:43

mukul_vashisht's gravatar image

4★mukul_vashisht
16
accept rate: 10%

2

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.

(08 Apr '18, 23:57) mgch6★

Thanks for the explanation.

Can you please give me the editorial link of TRS ? https://www.codechef.com/LTIME58A/problems/TRS

(09 Apr '18, 00:14) mukul_vashisht4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,492
×1,648
×1,176
×301
×68
×47
×1

question asked: 02 Apr '18, 15:56

question was seen: 665 times

last updated: 09 Apr '18, 00:22