The above equation can be solved without the convex hull trick in O(n). We just need to use the property of quadrangle inequality. You can look for 1D-1D Dp optimisation. It solves the above recurrence in O(n). For more details, you can refer to my code.

The first part of your solution is correct where you binary search on the cost associated with increasing one partition. So, now the problem reduces to solve the recurrence you mentioned optimally. As the above recurrence satisfies quadrangle inequality, you can solve it in O(n) using 1D-1D Dp optimisation. Hence the complexity would be O(n logA) where A is upper bound of cost.

Thanks :)

How to solve E — Eva and Euro coins ?

I did ternary search on all 3 coordinates. Do a ternary search on x first, now for getting optimal answer for this x, do ternary search on y keeping x fixed, repeat this for z, keeping x and y fixed.

Why does the randomized solution work for K?

Thanks :)

Could you explain, how did you solve the query part in O(|x|* LogN *26) per request? I solved it in O(|x| * LogN * LogN * 26) . I first build the suffix tree of given string. Then to find whether there is an element in range [l,r] in given subtree, I use binary search on each node of segment tree which are visited during query. Hence, there would be O(logN * logN) for each character (from 0 to 26) for each index of x in the worst case.

I had a solution with 2-D sparse BIT (Binary Indexed Tree). Basically first calculate number of permutations such that Bahu at least 2 values greater than the corresponding values for Bala. It can be done simply by using a BIT. Then subtract 2 times the number of permutations where all three values of Bahu are greater than Bala. This can be done using 2-D sparse bit. Any solution easier than this?

You can always add edge at same place.

F(g(N)).

Paths which go from one part to another are counted twice. And we add paths from u to root once when we solve for each vertex u. To make their count twice, we add paths from root to u again. Now we add dp[r]/2 to the ans.

dfs1() calculates the mask for each vertex. dfs2() calculates the answer for each vertex. dp[u] is the the number of paths starting from subtree of u and ending in any other part.

Auto comment: topic has been updated by born2rule (previous revision, new revision, compare).

First root the given tree on its centroid. Now for each node u, mask_u has at jth bit in binary representation of mask_u, considering count of characters from root to u. We can say that a path from u to v is palindromic if has at most 1 set bit.

Now let part_v be defined as subtree of vertex v such that v is children of the centroid. Now we consider all paths that include centroid. For each node u, valid paths are the paths ending in part other than part_u, and starting from any node in subtree of u including itself and satisfying the above property.

Valid masks for a node u are: mask[u] and . Let other_u be the sum of all valid masks from other parts for u. So for u, other_u will be such that v lies in its subtree (including itself) . Hence add it to the answer. For root (centroid), answer will be summation of cnt1[mask[u]]·cnt2[mask_x] for all u, such that cnt1 is count of masks in part of u, and cnt2 is count of masks in other parts and mask_x are valid masks of u.

Now solve recursively for each of the parts.

Auto comment: topic has been updated by born2rule (previous revision, new revision, compare).

mask[u] has cnt[j]%2 at jth bit in binary representation of mask[u], considering characters from root to u. Now when we root the tree at centroid, we consider the paths from root to subtree of u and from subtree of u to vertices in other parts when we calculate answer for u. We do this for each centroid.

How to solve problem I — Installing Apps?