How to solve this question?

#1

964×812 78.2 KB

#2

You can use bitmasks to solve this.
Make a dp array of upto 8, where 1 represents A, 10 represents B, 100 represents C.
Take a look at this code for implementation https://ide.codingblocks.com/s/322801

#3

Can you explain the logic in more detail, what you have done after declaring the dp array?

#4

Your Code may not be correct.
Try the testcase
2
AB
BC
1
2

#5

Yeah there was an error, please see if this passes the testcases https://ide.codingblocks.com/s/323290,
If yes then I can explain the logic.

#6

Ok Explain the logic

#7 
for (int i = 0; i < 8; i++) dp[i] = INTMAX;

dp[i] is the min cost to make a string have the all the characters which are set in i.
For example
dp[001] means minimum cost to have a string having atleast 1 A.
dp[110] means minimum cost to have a string having atleast B and C in it.
dp[111] or dp[7] means minimum cost to have a string having A,B and C.

So I initialise it with max cost.

for (int i = 0; i < n; i++) {
              dp[val[i]] = min(dp[val[i]], cost[i]);
              for (int j = 0; j < 8; j++) {
                     dp[(j | val[i])] = min(dp[j | val[i]], dp[j] + cost[i]);
              }
       }

After this it’s just bitmask dp.
I iterate over all i, Now I check all the possible strings that can be formed using this string.
We can form 8 strings in total from 0 to 7.
So using a string j, we can form dp[val[i] bitwise or j], so we check the min cost to form dp[val[i] | j]

Bitwise or works because we aim to form 7 which has all bits set.

Dry run the program, then it should be clear how bits are being manipulated

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.