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.