PREFNEC - Editorial

PROBLEM LINK:

Practice

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.

There should be a DP tag added to question.

My DP solution link
https://www.codechef.com/viewsolution/18475246