# | User | Rating |
---|---|---|

1 | tourist | 3851 |

2 | jiangly | 3634 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | ksun48 | 3493 |

6 | djq_cpp | 3486 |

7 | maroonrk | 3471 |

8 | Radewoosh | 3442 |

9 | Petr | 3426 |

10 | Isonan | 3344 |

# | User | Contrib. |
---|---|---|

1 | -is-this-fft- | 185 |

2 | awoo | 180 |

3 | dario2994 | 171 |

4 | SecondThread | 168 |

4 | maroonrk | 168 |

4 | Um_nik | 168 |

7 | adamant | 167 |

8 | errorgorn | 166 |

8 | YouKn0wWho | 166 |

10 | antontrygubO_o | 162 |

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/28/2022 10:03:20 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

ok nice, it worked https://www.codechef.com/viewsolution/67079207

Thanks