HDU Multi-University Training 2019, Contest 2

Longest Increasing Subsequence Revisited: Problem B
An alternative way to solve LIS: Using a segment or BIT to keep the maximum length ending with number $i$. To choose the lexicographically smallest/largest, we can greedy pick the first/last available number.

Contribution Technique?: Problem F
The key thing to notice is the product of any two unit cube. No matter how we split the cubes, they always stays the same. That means the answer is always the same, which equals to the sum of products of all pairs of unit cube. We can calculate that with the help of FWT.

Tricky Build-up of min-cut graph: Problem H
Consider having two items $A, B$ in a min-cut graph and the source $S$ and the sink $T$. Consider 5 edges between those vertices: $SA, SB, AB, AT, BT$. We can set up the cost of those edges properly so that cutting in some edges corresponds the profit that we are not able to get by seperating them. There are 5 variables and 4 equations, so we can have some solutions. In the setting of the problem, we can always get a non-negative solution. Then we get add the graphs of two vertices up and get the final graph.

Palindrome Tree: Problem I
Using DFS/Binary Lifting on the fail tree, we can know if there is a suffix palindrome of certain length. Then can add them to the answer.

Leave a Reply

Your email address will not be published. Required fields are marked *