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 and the length to be N.

Observe that if the sum in the range [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] is divisible by its length then we can write \sum_{i=L}^R a[i] as D \times (R-L+1) for some D.

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

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

So:

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

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

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

\displaystyle \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}

Where:

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

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

Time Complexity: \mathcal{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