### Hints:

div2A: Try conversions between bases.

div2B: Solve a simpler version of the problem where *A*_{i + 1} ≠ *A*_{i} for all *i*.

div1A: What are the shortest paths of the vehicles? what's the shorter of those paths?

div1B: Forget about the ceiling function. Draw points (*i*, *A*[*i*]) and lines between them — what's the Lipschitz constant geometrically?

div1C: Some dynamic programming. Definitely not for the exp. score of one person — look at fixed scores instead.

div1D: Compute *dif*(*v*) in *O*(*N*) (without hashing) and then solve the problem in *O*(*N*^{2}). Read my editorial of TREEPATH from Codechef.

div1E: Can you solve the problem without events of type 1 or 2? Also, how about solving it offline — as queries on subsets.

What, you thought I'd post solutions? Nope. Read the hints, maybe they'll help you. The solutions will appear here gradually.

### Div. 2 A: Two Bases

It's easy to compare two numbers if the same base belong to both. And our numbers can be converted to a common base — just use the formulas

A straightforward implementation takes *O*(*N* + *M*) time and memory. Watch out, you need 64-bit integers! And don't use `pow`

— iterating is better.

### Div. 2 C / Div. 1 A: The Two Routes

The condition that the train and bus can't meet at one vertex except the final one is just trolling. If there's a railway , then the train can take it and wait in town *N*. If there's no such railway, then there's a road , the bus can take it and wait in *N* instead. There's nothing forbidding this :D.

The route of one vehicle is clear. How about the other one? Well, it can move as it wants, so the answer is the length of its shortest path from 1 to *N*... or - 1 if no such path exists. It can be found by BFS in time *O*(*N* + *M*) = *O*(*N*^{2}).

In order to avoid casework, we can just compute the answer as the maximum of the train's and the bus's shortest distance from 1 to *N*. That way, we compute ; since the answer is ≥ 1, it works well.

In summary, time and memory complexity: *O*(*N*^{2}).

Bonus: Assume that there are *M*_{1} roads and *M*_{2} railways given on the input, all of them pairwise distinct.

Bonus 2: Additionally, assume that the edges are weighted. The speed of both vehicles is still the same — traversing an edge of length *l* takes *l* hours.

### Div. 1 D: Acyclic Organic Compounds

If you solved problem TREEPATH from the recent Codechef November Challenge, this problem should be easier for you — it uses the same technique, after all.

Let's figure out how to compute for just one fixed *v*. One more or less obvious way is computing hashes of our strings in a DFS and then counting the number of distinct hashes (which is why there are anti-hash tests :D). However, there's another, deterministic and faster way.

#### Compressing the subtree *T*_{v} into a trie.

Recall that a trie is a rooted tree with a letter in each vertex (or possibly nothing in the root), where each vertex encodes a unique string read along the path from the root to it; it has at most σ sons, where σ = 26 is the size of the alphabet, and each son contains a different letter. Adding a son is done trivially in *O*(σ) (each vertex contains an array of 26 links to — possibly non-existent — sons) and moving down to a son with the character *c* is then possible in *O*(1).

Compressing a subtree can be done in a DFS. Let's build a trie *H*_{v} (because *T*_{v} is already used), initially consisting only of one vertex — the root containing the letter *s*_{v}. In the DFS, we'll remember the current vertex *R* of the tree *T* and the current vertex *cur* of the trie. We'll start the DFS at *v* with *cur* being the root of *H*_{v}; all we need to do is look at each son *S* of *R* in DFS, create the son *cur*_{s} of *cur* corresponding to the character *s*_{S} (if it didn't exist yet) and run *DFS*(*S*, *cur*_{s}). This DFS does nothing but construct *H*_{v} that encodes all strings read down from *v* in *T*_{v}. And since each vertex of *H*_{v} encodes a distinct string, is the number of vertices of *H*_{v}.

This runs in *O*(|*T*_{v}|σ) time, since it can create a trie with |*T*_{v}| vertices in the worst case. Overall, it'd be *O*(*N*^{2}σ) if *T* looks sufficiently like a path.

#### The HLD trick

Well, what can we do to improve it? This trick is really the same — **find the son w of v that has the maximum |T_{w}|, add s_{v} to H_{w} and make it H_{v}; then, DFS through the rest of T_{v} and complete the trie H_{v} as in the slow solution.** The trick resembles HLD a lot, since we're basically remembering tries on HLD-paths.

If *v* is a leaf, of course, we can just create *H*_{v} that consists of one vertex.

How do we "add" *v* to a trie *H*_{w} of its son *w*? Well, *v* should be the root of the trie afterwards and the original *H*_{w}'s root should become its son, so we're rerooting *H*_{w}. We'll just create a new vertex in *H*_{w} with *s*_{v} in it, make it the root of *H*_{w} and make the previous root of *H*_{w} its son. And if we number the tries somehow, then we can just set the number of *H*_{v} to be the number of *H*_{w}.

It remains true that *dif*(*v*) is |*H*_{v}| — the number of vertices in the trie *H*_{v}, which allows us to compute those values directly. After computing *dif*(*v*) for each *v*, we can just compute both statistics directly in *O*(*N*).

Since each vertex of *T* corresponds to vertices in at most tries (for each heavy edge that's on the path from it to the root), we aren't creating tries with a total of *O*(*N*^{2}) vertices, but . The time complexity is therefore . However, the same is true for the memory, so you can't waste it too much!

Bonus: you have an additional tiebreaker condition for vertices with identical . Count the number of distinct strings which occurred exactly *k* times for each *k* in an array *P*_{r}[]; take the vertex/vertices with lexicograhically maximum *P*_{r}[] (as many strings as possible which occur only once, etc).

Bonus 2: Can you get rid of the logarithm in the time complexity?