Все сводится к переключению на старый календарь, но моя ссылка ведет на описание в новом интерфейсе :) Так как же попасть на описание соревнования через новый интерфейс?

Let A_i be the minimum amount of people who have bought all items from 0 to i.

Then, we have A_0 = s[0] as our base case.

Then, we can find a formula for A_i = max(0, A_(i-1) + s[i] — N). We can derive this since we know at least A_(i-1) people have bought items 0 to i-1, s[i] people have have bought item i and there are N total people. Thus, A_i is minimum size of the intersection between the people who've bought items 0 to i-1 and people who've bought item i.

It's maximum weight independent set on a bipartite graph.

First, make a node for each red or blue segment you can draw. Then, connect two nodes if they can not occur in a configuration together. We can see that this resulting graph will be bipartite. Our answer will be an independent set of this graph, so we want to maximize the weight of it. We can do this with max flow as follows:

• connect the source to each blue node with the score of that blue segment
• connect each red node to the sink with the score of that red segment
• connect a blue and red node with infinite capacity if they conflict

We can see the maximum weight independent set is just the sum of all blue/red scores we can get minus the minimum cut. We know we can solve min cut on a bipartite graph with max flow.

Here's a rough sketch.

Start with the string "11111...111". Then, for each character in order, try greedily setting it to zero. It can only be set to zero if the resulting string is special and is also strictly greater than current. The reason we need to check if the resulting string is still special is if ST is not a special string, where S is some arbitrary string, and T consists of all 1s, then ST' will definitely not be special, where T' is some arbitrary string that is the same length as T. The running time of this is O(N^2)

Alternatively, there is a different solution to this that is also google-able (but it seems no one had this solution). You can see it here: http://en.wikipedia.org/wiki/Lyndon_word#Generation The running time of this method is O(N)