yaksha's blog

By yaksha, history, 4 years ago, In English

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..

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it