Trouble in understanding A bitmasks DP problem

Revision en1, by yaksha, 2018-06-12 20:18:41

Hi, So I recently attempted this problem, I was not able to solve it , and went to read the editorial.. The editorial however did not give proof for the DP state and transition , and I am having a lot of trouble actually understanding how the DP transition is working...

Problem : 543C - Remembering Strings

Solution : 11035719

My Thoughts:

the DP state is "mask" which denotes the strings that have been already made easy to remember.. The editorial says , we pick up the "lowest bit" which is ON and then find the most optimum result while focusing only on that 'lowest bit' (by checking all the columns)

However , in my opinion , for the current state "mask" we should check the same thing not just for the lowest bit , but infact for all of the bits that are ON . .

Please help, I think I am conceptually very wrong in this problem..

Tags dp, bitmask

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English yaksha 2018-06-12 20:18:41 910 Initial revision (published)