ygd161837jn2n313's blog

By ygd161837jn2n313, history, 21 month(s) ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you can repeatedly, greedily choose the pen which can write the most letters.

Now we are left with the problem: "starting from some index i, which pen to choose which can write the most letters?"

To solve, for example, we can binary search the length of the subarray starting at index i. We can get the set of <=20 letters in this subarray, and now we have to answer queries of: "does there exist some pen which can write this set of letters?"

To answer this query, we consider the graph of all 2^20 subsets of letters. Each pen is now some node. Let's DFS from each pen. Inside the DFS, we'll individually remove each set bit of the current mask to get a submask to recurse to. Now, if a node is visited, then there exists some pen "covering" this set of letters