Table of Contents

1. Global Positioning System
2. Card Game
3. Median
4. SuperMemo
5. Sequence
6. Last Hit
7. Text Message Formatting
8. Small Polynomial Factorization

Problem A: Global Positioning System

The idea is to solve a equation having trigonometric functions. Suppose that t1=0 and let x2' = x2 - x1, y2' = y2 - y1, x3' = x3 - x1, y3' = y3 - y1, x' = x - x1, y' = y - y1. Then we have two equations :

where

by letting

we obtain

Problem B: Card Game

It is obvious that Jack will add m points to apo. Also it can be proven that if Joe can win p rounds he must have a strategy to achieve it using only the most powerful p cards. So the idea is bisecting p and testing whether it can be achieved. The testing can be solved by a greedy algorithm.

Problem C: Median

Assume X₁, X₂, ... X_n is the non-descending permutation of the numbers. Consider the following table:

X2-X1
X3-X1	X3-X2
X4-X1	X4-X2	X4-X3	...
...	...	...	...
Xn-X1	Xn-X2	Xn-X3	...	Xn-Xn-1

The rows are non-ascending from left to right and the columns are non-descending from top to bottom. Given a value, we can use the table to calculate how many differences are less than it.

Problem D: SuperMemo

The trivial solution in O(mn) will apparently get TLE. We can use a balanced-tree, like Splay Tree, to maintain the sequence effectively. The relative sequence number is the keyword of each nodes in the tree. For example the sequence{29, 25, 30, 41, 56} can be represented as the following balanced-tree : (the number in blanks are their sequence index)

   30(3)
   /   \
 25(2) 56(5)
 /      /
29(1) 41(4)

Every tree node needs to record at least following information:
int data ——the current data of this node
int t ——the total number of tree nodes in this sub-tree
int delta ——the common increasing value on each nodes in this sub-tree
bool reverse ——whether the whole sub-tree needs to be reversed.
Since then, we may maintain the every single operation in O(logn) in average time.
For example, the "RESERVE x y" command, we can operate as follows:
STEP1 : cut the tree into 3 sub-trees: T1(X-1 nodes), T2(Y-X+1 nodes), T3(n-Y nodes)
STEP2 : change T2.reverse to !T2.reverse(reverse the sub-tree T2)
STEP3 : merge the 3 sub-trees in turn.

Problem E: Sequence

Assume R is the reverse of the given sequence, then the first cutting position is where the smallest suffix of R starts which can be evaluated effectively by suffix array. The second cutting position can be obtained in a similar way.

Problem F: Last Hit

If neither hero can hit the creep before it dies, the answer is clearly "God". Apart from this situation, as the creep will counted for hero1 if their bullets hit the creep at the same time, hero1 will definitely win if t₁ is not greater than t₂, whatever their attacks are. If t₁ is greater than t₂, it can be proven that no one will attack (or their attacks will do no effect to the result) before the hp of the creep reaches max{a1+t1*v,a2+t2*v}, so all you need to do is to set the hp of the creep to max{a1+t1*v,a2+t2*v} (If the initial hp of the creep is bigger than max{a1+t1*v,a2+t2*v}) and simply calculate who will get the last hit of the creep.

Problem G: Text Message Formatting

There multiple tricky cases which a solution has to take into consideration to be correct. They include

• empty strings in the input,
• indices in braces exceeding bounds of the argument array (did you realize there could be something like {4294967297}?),
• backslashes invalidating placeholders (for example, \{\1\}) among other minor ones.

Problem H: Samll Polynomial Factorization

If a reducible polynomial f(x) of order δ must have a irreducible factor g(x) of order not exceeding δ/2. We try to find g(x) by enumeration. Suppose we want to find a second-order g(x). We need three (x, g(x)) pairs to uniquely determine g(x). Observe that for any x such that f(x) ≠ 0, g(x) must be a divisor of f(x). This prompts us to find x₁, x₂, x₃ such that f(x₁), f(x₂), f(x₃) ≠ 0, enumerate y₁, y₂, y₃ which are a divisor of f(x₁), f(x₂), f(x₃) respectively, fit a g(x) through the points (x₁, y₁), (x₂, y₂), (x₃, y₃) and check whether it has integral coefficients and is indeed a factor of f(x).