but bugs have only six legs

Look at Gym tab more often, there was announcement 2 days ago.

Look at this problems in different way: You've got Mi man and Wi woman "fighting" for Si shoelaces. Greedy algorithms does the trick. Firstly, give all shoelaces to woman (because you're gentleman) and take back and give shoelaces to man until there are more woman with shoelaces. Don't do it one by one, but count how many you should take back for every color.

Dunno, the straightforward "subtract N - i from non-negative sum, add N - i to negative sum" for all i from 1 to N - 1 worked for me...

I: there's a DAG with at most 2 edges from each vertex; if a vertex is (position, last jump direction), you can make "dummy jumps" whose cost depends on whether the direction of the last and next jump are the same

J: trie, offline (add the dictionary into the trie); in particular, all answers will be either the sum of LCP with all strings or the sum of LCP of s[i] with s[j < i]

can you put the d and f solution,thanks

Can you explain solution to E? I could only understand up to line 43

You can calculate new coordinates of your raplaces, so you handle requests from the end, calculate on each step new coordinates. It's work with O(m) complexity.

In problem D , the rotation and reflection (Mirror) can be done in O(1). In these cases only the starting position for row , starting position for column , direction of row , direction of column changes.Also in case of rotation the board inverts . The row becomes column and columns became rows( Something like that !!!). If you handle this cases and just simulate accordingly for replacing your work is done.

My Code.

G can be converted to this problem. Put + (or -) in proper way to solve this equation: (n-1) +/- (n-2) +/- (n-3) +/- ... +/- 1 = s

What is the max sum possible : (n*(n-1))/2 when you place 0,1,2,...n-1 : now consider some place x(0<=x<=n-2) after which instead of increasing you decrease, then 0,1,..x,x-1,x,x+1,... : this makes the sum decrease by 2*(n-x-1). So, the problem can be viewed as decreasing after some positions to achieve required sum. Of course, if abs(sum)>(n*(n-1))/2, then answer is not possible. Because you decrease some multiple of 2, the parity of sum and (n*(n-1))/2 should be same. Now, a greedy approach starting from x=0, current_sum = (n*(n-1))/2, by decreasing the maximum possible allowed, and storing after which indices you have decreased.

Let me start from the end to give the motivation for the rest. The following formula gives the solution to the problem:

Let and

With this formula it is trivial to get an O(k2^k) algorithm, and fairly simple to get an O(2^k).

Now the derivation:

Note:

To count the number finished states, label them by the last station on each track that is on strike. There are states with each label.