### Hints:↵
↵
[div2A](#div2A): Try conversions between bases.↵
↵
div2B: Solve a simpler version of the problem where $A_{i+1} \neq A_i$ for all $i$.↵
↵
[div1A](#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](#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.↵
↵
↵
↵
↵
### <a name="div2A"></a>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↵
↵
$$X=\sum_{i=1}^N x_i B_x^{N-i}; \quad Y=\sum_{i=1}^M y_i B_y^{M-i}\,.$$↵
↵
A straightforward implementation takes $O(N+M)$ time and memory. Watch out, you need 64-bit integers! And don't use `pow` — iterating $X \rightarrow XB_x+x_i$ is better.↵
↵
↵
↵
### <a name="div1A"></a>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 $1\texttt{ - }N$, then the train can take it and wait in town $N$. If there's no such railway, then there's a road $1\texttt{ - }N$, 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 $\text{max}(1,\text{answer})$; since the answer is $\ge 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.↵
↵
↵
↵
### <a name="div1D"></a>Div. 1 D: Acyclic Organic Compounds↵
------------------------------------↵
↵
The name is really almost unrelated — it's just what a tree with arbitrary letters typically is in chemistry.↵
↵
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 $\text{dif}(v)$ 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 $\sigma$ sons, where $\sigma=26$ is the size of the alphabet, and each son contains a different letter. Adding a son is done trivially in $O(\sigma)$ (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, $\text{dif}(v)$ is the number of vertices of $H_v$.↵
↵
This runs in $O(|T_v|\sigma)$ time, since it can create a trie with $|T_v|$ vertices in the worst case. Overall, it'd be $O(N^2\sigma)$ if $T$ looks sufficiently like a path.↵
↵
#### The HLD trick↵
↵
Well, what can we do to improve it? This trick is really the same — <b>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.</b> 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 $O(\log{N})$ 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 $O(N \log N )$. The time complexity is therefore $O(N\log{N}\sigma)$. 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 $c_r+\text{dif}(r)$. 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?↵
↵
[div2A](#div2A): Try conversions between bases.↵
↵
div2B: Solve a simpler version of the problem where $A_{i+1} \neq A_i$ for all $i$.↵
↵
[div1A](#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](#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.↵
↵
↵
↵
↵
### <a name="div2A"></a>Div. 2 A: Two Bases↵
------------------------------------↵
↵
↵
$$X=\sum_{i=1}^N x_i B_x^{N-i}; \quad Y=\sum_{i=1}^M y_i B_y^{M-i}\,.$$↵
↵
A straightforward implementation takes $O(N+M)$ time and memory. Watch out, you need 64-bit integers! And don't use `pow` — iterating $X \rightarrow XB_x+x_i$ is better.↵
↵
↵
↵
### <a name="div1A"></a>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 $1\texttt{ - }N$, then the train can take it and wait in town $N$. If there's no such railway, then there's a road $1\texttt{ - }N$, 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 $\text{max}(1,\text{answer})$; since the answer is $\ge 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.↵
↵
↵
↵
### <a name="div1D"></a>Div. 1 D: Acyclic Organic Compounds↵
------------------------------------↵
↵
The name is really almost unrelated — it's just what a tree with arbitrary letters typically is in chemistry.↵
↵
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 $\text{dif}(v)$ 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 $\sigma$ sons, where $\sigma=26$ is the size of the alphabet, and each son contains a different letter. Adding a son is done trivially in $O(\sigma)$ (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, $\text{dif}(v)$ is the number of vertices of $H_v$.↵
↵
This runs in $O(|T_v|\sigma)$ time, since it can create a trie with $|T_v|$ vertices in the worst case. Overall, it'd be $O(N^2\sigma)$ if $T$ looks sufficiently like a path.↵
↵
#### The HLD trick↵
↵
Well, what can we do to improve it? This trick is really the same — <b>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.</b> 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 $O(\log{N})$ 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 $O(N \log N )$. The time complexity is therefore $O(N\log{N}\sigma)$. 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 $c_r+\text{dif}(r)$. 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?↵
