Editorial for DMOPC '17 Contest 1 P2 - Sharing Crayons


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.

Author: Kirito

For the first subtask, we can loop through all subarrays and find their sum, and count how many are divisible by M.

Time Complexity: \mathcal O(N^3)

For the second subtask, we can iterate through all subarrays and find their sum using a prefix sum array, and count how many are divisible by M.

Time Complexity: \mathcal O(N^2)

Let P_i = \sum_{j=1}^i A_i.

For the third subtask, notice that the sum of a subarray A[l, r] will be divisible by M if P_r \bmod M \equiv P_{l-1} \bmod M. Thus we can store a counter array C of size M such that the ith entry is the number of prefix sums that are congruent to i mod M. Thus we can just loop through A, and add C[A_i] to our answer, and then increment it by one.

Time Complexity: \mathcal O(N)

For the fourth subtask, we can replace the counter array with a map data structure, as an array of size 10^9 will MLE.

Time Complexity: \mathcal O(N)

Extra Challenge: Can you solve this problem without using a map data structure?


Comments

There are no comments at the moment.