PKU3420 - Quad Tiling

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3420

Typical DP problem when N is small.

In this problem, N can be as large as 10^9, so matrix multiplication should be used. Unlike the problem I've done before, this time the matrix is as large as 16x16 (because there is 2^4 number of states at each layer). I write code to pre-generate the 16x16 matrix instead of hard-coding the formula, and then do matrix multiplication as usual.

PKU3135 - Polygons on the Grid

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3135

An exhaustion problem.
The solution is well known, but this is a good problem for me to practice my exhaustion skills.

We can pre-compute the all possible placement on the grids for specific length sticks. In the worst case, there is 36 possible placement on the grids, which is small and we can do exhaustion on different placements.

Here is some skills for cut-case:
1. Fix the longest stick to be the first one, and try permutations for other sticks.
2. Check whether the sticks left are not long enough to reach back to the origin. Otherwise, cut this case.
3. After putting n-1 sticks, the length to the origin must be equal to the length of the last stick. Otherwise, cut this case.
4. We can fix the direction to put the first stick to be in the first region (x,y are positive)
5. Because for the first stick, it is symmetric for (y,x) and (x,y) cases arrangement, we can only try one of them.

Another thing is that do not use STL pair when doing these problems.

PKU3471 - Integral Roots

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3471

The problem is given an integral coefficient polynomial, find all integral roots of it.

If there is repeated root, output them repeatedly.

For the integral roots of the polynomial, it must be a factor of the constant term of the polynomial. We then can factorized the constant term and verify the factors to the polynomial one by one.

However, overflow will occur during the verification (the degree of the polynomial may be as large as 100), how should we verify the solution safely?

One method is that you can calculate the polynomial by repeatedly dividing and subtracting each terms. For example, ax^2 + bx + c = 0, it can be rewritten as ax + b = -c/x. As the LHS of the equation is integer, the c/x must be integer. Using this method, we can avoid overflow in our calculation.

This has not solved the problem. We have not identified the repeated roots. One way to find the multiplicity of roots is to check f(x), f'(x), f''(x), and so on, and they should all be zero. But calculating the derivatives of f may again lead to overflow.

The method I finally used is to do polynomial division.

I repeatedly divide the polynomial by (x - c). If that is divisible, then c is a root of it, and use the quotient to continue the process. This can avoid all overflow problems, and find the repeated roots successfully.

Be careful on the cases that zero is the root of the polynomial.

start writing ACM blog

a little bit late, but hopes this can make me write more, and of course, do more problems =)