### PROBLEM LINK:

**Author:** Mayank Pugalia **Tester:** Aswin Ashok **Editorialist:** Mayank Pugalia

### DIFFICULTY:

EASY

### PREREQUISITES:

NONE

### PROBLEM:

Here we had to answer **Q queries**, i.e. Minimum cost of making a Necklace using **exactly X beads** and achieving **exactly Y beauty value.**

We can make a necklace using **any of the 5 beads**, each of them having its own beauty value.

**S-> -2, G-> -1, Q-> 0, R-> 1 & D-> 2** and each of them had a cost.

For every query we have to output the minimum cost of making such a necklace.

### EXPLANATION:

If we used complete Brute Force then it would give a **TLE**, But if we used appropriate **“Breaks”** at correct places along with **memoization** then we could do it in the given time limit.**(Basically being greedy)**

**The constraints of X and Y were set low because a improved brute with memoization was expected to pass.**

### INTENDED SOLUTION:

Using Brute:

**->**We try to calculate all possible necklaces and store the Min cost for each type.

**->**we need 5 nested loops running from 0 to 100, lets say that we used the variables **i,j,k,l,m** for the loops where **i,j,k,l,m** are number of beads.

**->**we calculate the beauty (**Y**) and the cost(**C**) of the making this necklace with (**X=i+j+k+l+m**) beads so we would store the cost of making this necklace using **X beads** and **Y beauty.**

**cost[X][Y] = Min ( cost[X][Y] , C )**

**->**now the beauty could go **negative!** (Max -200) so we would add an **offset 200** to the beauty so that **Y** never goes negative so the dimensions of the “cost” array should be **cost[101][401]**

for example if **beauty is -100** and **beads are 50** we would use location

**cost[ -100+offset(200) ][ 50 ] == cost[100][50]**

**After calculation of all the minimum cost we can answer the query in O(1)
but the pre calculation would take time around O(10^10).**

The thing to notice here is that we **do not require all the iterations** of the five loops because we know the the **sum of the beads never cross 100** but in our brute we will calculate the cost for up to 500 beads so **when ever the total number of beads becomes more that 100 we break from the respective loop**

```
for(i from 0 to 100)
for(j from 0 to 100)
if(i+j greater than 100)
break
for(k from 0 to 100)
if(i+j+k greater than 100)
break
for(...
...
if(i+j+k+l greater than 100)
break
for(..
and so on.. for “m” also
```

### TIME COMPLEXITY

**After doing this optimization the complexity for the precalculation comes around O(10^8)**

which will fit in time limit.

### ALTERNATIVE SOLUTION:

Another solution is also there and many of them have used this methods.

Here we would use **Dynamic Programming**, i.e. we would make use of the previous states.

Let dp[i][j] denote the cost of making a necklace of beauty **j** with **i** beads

**Now we can arrive at a state dp[i][j] from 5 different previous states**

those are

→ **dp[i-1][j-2]** and use a **diamond with beauty +2** so no of **beads = (i-1) +1** and **beauty (j-2)+2**

→ **dp[i-1][j-1]** and use a **ruby with beauty +1** so no of **beads = (i-1) +1** and **beauty (j-1)+1**

→ **dp[i-1][j]** and use a **quarts with beauty 0** so no of **beads = (i-1) +1** and **beauty (j-0)+0**

→ **dp[i-1][j+1]** and use a **glass with beauty -1** so no of **beads = (i-1) +1** and **beauty (j+1)-1**

→ **dp[i-1][j+2]** and use a **stone with beauty -2** so no of **beads = (i-1) +1** and **beauty (j+2)-2**

**All the five states would arrive at dp[i][j] after using a appropriate bead. And we can store the minimum of these costs.**

**The complexity of this solution will be around O(10^6)**

### SOLUTIONS LINKS:

Author’s solution can be found here.

Tester’s solution can be found here.