Author: Roman Rubanenko
Tester: Vamsi Kavala
Editorialist: Bruno Oliveira
Chef is at a restaurant serving dishes. There are N ingredients on the restaurant (which we can assume are numbered from 0 to N-1) , and each ingredient is characterized by its beauty which is a positive integer. To order a specific dish, a costumer chooses a segment of ingredients, starting from ingredient whose index is L and ending on the ingredient whose index is R.
However, Chef decides not to use the least beautiful ingredient that is on this subset. Given an integer K, we want to count how many segments (L,R) are there such that the sum of their beauty values will be divisible by K after excluding the least beautiful ingredient.
For the small data-set, a simple brute-force approach to evaluate all segments will suffice to pass the time limit.
For the larger data-set however, the approach we need to use is Divide-and-Conquer. We will see in detail how can this be done.
As mentioned above in quick explanation, iterating over all sets and doing the appropriate counting should suffice to solve the small data-set, since constraints are so small. (N <= 1000 and K <= 100 on the sub-tasks being worth 21 and 39 points respectively.)
The sub-task with the remaining 40 points allocated to it, is not so simple, since N and K can both be very large. The idea is to use Divide-and-conquer to speed things up.
Let F[L,R] be the answer for the original problem if we are given the array=A[L…R], that is, the array formed only by the given ingredients chosen by a costumer.
Let M be the index of the minimal element on this segment.
Let’s count the number of segments that contain point M.
We can count it using partial sums and any data structure that allows us to find a key and the number of times it appears in that same structure (map, for example).
Then we need to calculate the segments that does not contain M, so we can have either L1<R1<M or M<L1<R1 so we should add F[L,M-1] and F[M+1,R] to F[L,R].
Due to the randomness of the test data, it can be showed that this approach doesn’t take a long time.
Some tricks and tweaks necessary to get higher points can be seen on both Setter’s / Testers solutions.
Refer to setter’s and tester’s solution for implementation details.
Can be found here.
Tester’s solution will be uploaded soon.