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$ ~M~.

Time Complexity: $\mathcal O(N^3)$ ~\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$ ~M~.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

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

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

Time Complexity: $\mathcal O(N)$ ~\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$ ~10^9~ will MLE.

Time Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

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

Comments

There are no comments at the moment.