Author: **Roman Rubanenko**

Tester: **Vamsi Kavala**

Editorialist: **Bruno Oliveira**

# PROBLEM LINKS

# DIFFICULTY

Medium

# PRE-REQUISITES

Divide-and-conquer

## Problem:

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.

## Quick Explanation:

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.

## Detailed Explanation:

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.

### SETTERâ€™S SOLUTION

Can be found here.

### TESTERâ€™S SOLUTION

Testerâ€™s solution will be uploaded soon.

**Useful Links**

**Useful Links**