HDU Multi-University Training 2019, Contest 1

Dynamic Programming: Problem A
Since there can only be four numbers, we can do a four-dimensional DP to record the last occurrences of the numbers. The time complexity is $O(n^4)$. One dimension can be used to record the current number, so we can reduce it to $O(n^3)$ space to fit into the space.

XOR Basis: Problem B
This can be solved by segment tree in $O(n \log n \log A)$, but this is too slow. Instead, we can keep a upper-triangular basis for each right bound. We should put the number with higher index as high as possible and put other numbers down. In this way, when we are querying the maximum for range $[l, r]$, we take the number in the “$r$ basis” when it is in the bound ($l_i \geq l$), and it can be guaranteed that every number we take is valid, i.e. can be expressed as a linear combination of the number in $[l_i, l]$.

Sliding Windows for String Matching on SAM: Problem F
There are several things to notice: The first is that the range for possible transition for copying text is increasing, which means we can use a deque to maintain the minimum. Furthermore, since we can prove the DP value is non-decreasing, we can just choose the smallest position to do the copy. To find that position $j$, we maintain a SAM for $s[1;j-1]$ and keeping adding $s[j]$ into the SAM until we can find $s[j;i]$ in $s[1;j-1]$. We use a pointer $pt$ to record the current matching. To delete a character, we just keep moving $pt$ until $curlen \leq st[pt].len$.

Generating Function/ Convolution: Problem L
Write the operation as generating function, we have $$\sum_i b_i x^i = (\sum_i a_i x^i) (\sum_i x^{ik})$$, which tells us that the order of operations does not matter. We also see that the operation of the same kind can be combined together by using the fact that the coefficient of $x^t$ in $(\sum_i x^{i}) ^ l$ is ${t + l – 1}\choose{l – 1}$. Then we can use three NTTs to get the answer.

Leave a Reply

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