Please subscribe to the official Codeforces channel in Telegram via the link ×

_Siegefried's blog

By _Siegefried, history, 2 months ago, In English

LINK to the problem

Its a previous edition "Codeagon" problem and I am trying to understand the editorial. I get the approach but it's my first time encountering a 4-D dp approach. I get the basic intuition behind the problem of subtracting solutions containing characters from only one string from all the solutions, but am unable to understand why we need a 4th state ("status" in editorial) at all as in calculating all possible solutions, how does it matter if I selected/skipped a character from A or from B previously, so why even keep a tab of it. I am probably looking at it wrong, so any help would mean a lot. Also, if a different approach comes to mind, pls do share it as well, thx!

Read more »

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