Editorial for DMOPC '17 Contest 1 P2 - Sharing Crayons - Olympiads Online Judge

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)$ $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)$ $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} mod M \equiv P_{l - 1} mod 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)$ $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)$ $O (N)$

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

Comments

There are no comments at the moment.