Codeforces Round #333 — editorial
Разница между en7 и en8, 305 символ(ов) изменены
### 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.↵


![ ](https://i.imgur.com/bnWmD60.png)↵

### <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 &mdash; 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` &mdash; iterating $X \rightarrow XB_x+x_i$ is better.↵

![ ](http://i.kinja-img.com/gawker-media/image/upload/rsn3th1odr4otjgubklz.gif)↵

### <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 &mdash; traversing an edge of length $l$ takes $l$ hours.↵

![ ](http://static.fjcdn.com/pictures/Pic_88f4ec_984592.jpg)↵

### <a name="div1D"></a>Div. 1 D: Acyclic Organic Compounds↵
------------------------------------↵

The name is really almost unrelated &mdash; 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 &mdash; 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 &mdash; possibly non-existent &mdash; 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 &mdash; 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 &mdash; <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|$ &mdash; 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?↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en16 Английский Xellos 2015-11-29 20:49:38 16 Tiny change: 'sing maps in $O(N ' -> 'sing maps + Fenwick trees in $O(N '
en15 Английский Xellos 2015-11-27 23:14:50 6 Tiny change: 'that $L_1(i,j) > L_1(j,k)$ in th' -> 'that $L_1(j,k) > L_1(i,k)$ in th'
en14 Английский Xellos 2015-11-25 18:20:31 2 Tiny change: 'ms in $O(k)$, but th' -> 'ms in $O(k^2)$, but th'
en13 Английский Xellos 2015-11-25 01:42:21 129
en12 Английский Xellos 2015-11-25 01:12:03 5769 and done
en11 Английский Xellos 2015-11-24 23:47:45 3357 Tiny change: 'akes $O(m^2n^2)$ time' -
en10 Английский Xellos 2015-11-24 23:25:07 1864 Tiny change: 'using STL map<>/set<> data stru' -> 'using STL `map<>`/`set<>` data stru'
en9 Английский Xellos 2015-11-24 23:08:43 3981 Tiny change: 'ps in $O(N\log{N})$ time.\n' -> 'ps in $O(N \log N)$ time.\n'
en8 Английский Xellos 2015-11-24 23:01:15 305 Tiny change: '------\n\n\nIt's e' -
en7 Английский Xellos 2015-11-24 22:48:48 3940
en6 Английский Xellos 2015-11-24 22:23:59 507
en5 Английский Xellos 2015-11-24 22:07:30 1272 Tiny change: 'Hints:\n\n' -
en4 Английский Xellos 2015-11-24 21:37:47 3 Tiny change: 'm Codechef :D.\n\ndiv1E' -
en3 Английский Xellos 2015-11-24 21:37:12 877
en2 Английский Xellos 2015-11-24 20:39:12 2 (published)
en1 Английский Xellos 2015-11-24 16:26:52 109 Initial revision (saved to drafts)