Editorial for An Animal Contest 6 P3 - OAC - Olympiads Online Judge

Editorial for An Animal Contest 6 P3 - OAC

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: andrewtam, dxke02

Subtask 1

Let's denote the array as $a$ $a$ and the length to be $N$ $N$ .

Observe that if the sum in the range $[L, R]$ $[L, R]$ is divisible by its length, then every element it contains must be equal to every other element.

With this in mind, we can solve this problem using the two-pointers technique.

Subtask 2

Let's try to extend our observation from subtask 1. First note that if the sum of the subarray in the range $[L, R]$ $[L, R]$ is divisible by its length then we can write $\sum_{i=L}^R a[i]$ $\sum_{i = L}^{R} a [i]$ as $D \times (R-L+1)$ $D \times (R - L + 1)$ for some $D$ $D$ .

Next, let's prove that $D \le 100$ $D \leq 100$ always holds regardless of what subarray we choose. This is because we can use the fact that $a_i \le 100$ $a_{i} \leq 100$ to prove that:

$\displaystyle \sum_{i=L}^R a[i] \le 100 \times (R-L+1)$ $\sum_{i = L}^{R} a [i] \leq 100 \times (R - L + 1)$

So:

$\displaystyle \frac{\sum_{i=L}^R a[i]}{R-L+1} \le 100$ $\frac{\sum_{i = L}^{R} a [i]}{R - L + 1} \leq 100$

With this in mind we can brute force all possible values of $D$ $D$ and for each of them check the number of subarrays $[L, R]$ $[L, R]$ whose sum can be written as $D \times (R-L+1)$ $D \times (R - L + 1)$ .

For a given $D$ $D$ this is equivalent for finding the number of pairs $0 \le i < j \le N$ $0 \leq i < j \leq N$ such that:

$\displaystyle \frac{f(j)-f(i)}{j-i} = D$ $\frac{f (j) - f (i)}{j - i} = D$

Which can be rewritten as:

$\displaystyle \begin{align} f(j) - f(i) &= D \times j - D \times i \\ f(j) - D \times j &= f(i) - D \times i \end{align}$ $\begin{aligned} f (j) - f (i) & = D \times j - D \times i \\ f (j) - D \times j & = f (i) - D \times i \end{aligned}$

Where:

$\displaystyle f(x) = \begin{cases} 0 & \text{if }x = 0 \\ f(x-1)+a_x & \text{if }x > 0 \end{cases}$ $f (x) = {\begin{cases} 0 & if x = 0 \\ f (x - 1) + a_{x} & if x > 0 \end{cases}$

With this in mind, we can calculate the number of valid pairs for a given $D$ $D$ with a frequency table and a prefix sum array to quickly compute values of $f(x)$ $f (x)$ .

Time Complexity: $\mathcal{O}(\max(a_i) \times N)$ $O (max (a_{i}) \times N)$

Comments

0

kim_123 commented on Dec. 23, 2022, 9:51 a.m.

I came up with the same solution and implemented it. I am getting TLE again and again.

0

Dingledooper commented on Dec. 24, 2022, 9:17 a.m.

Consider using an array rather an unordered_map.

0

rsj commented on Nov. 28, 2022, 2:53 a.m.

This problem is somewhat similar to 1270F