DUSC Winter Warm-up DWW19C

Can someone explain what was the approach to solve this problem Anjali and the tasty treat

It is a cakewalk problem. You can just store the character count for all the alphabets in the strings A and B. And then just check for each character if it’s occurrence is less in A than B, if so, just add the difference to the answer.


Check for the intersections between the two strings while including duplicate elements.

@ankushkhanna , there was swap ingredients … first i thought swapping ingredients between A and B and then got to know swapping ingredients in A to get the same order as B

Actually it is well mentioned in the line just before the operations:

There are three types operations which she can perform any number of times (including 0) and in any order on dish A to make dish B

Don’t miss the "on dish A" part.

oh ok
Didnt read the question properly as i was in hurry in the contest

Oh! It’s just fine. No need to be sorry. We’re all here to learn.

1 Like

But then, there can be a case where we deleted a character (cost 0) and later tried to add the same character at the end of B(cost 1). so, in this case, the frequency of that character is the same in both A and B, but cost is 1.

But it is not optimal to do such an operation. It will only add up cost. The best part is (which is making this problem very very easy) that swapping a pair and deletion operations are free, so we just need to focus on the addition part, and add in a way so as to minimize the total cost (expenditure).

So we should never delete a character which is required, we just need to add the deficit characters, that’s it.

Hope you got it.

1 Like

acha… got it! the same operation can be achieved by a series of swaps and hence that’ll be chosen which doesn’t alter the cost…

yeah… got it… thank you!