Codeforces Round #333 — editorial

Revision en7, by Xellos, 2015-11-24 22:48:48


div2A: Try conversions between bases.

div2B: Solve a simpler version of the problem where Ai + 1 ≠ Ai 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(N2). 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(N2).

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(N2).

Bonus: Assume that there are M1 roads and M2 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 Tv 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 Hv (because Tv is already used), initially consisting only of one vertex — the root containing the letter sv. 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 Hv; all we need to do is look at each son S of R in DFS, create the son curs of cur corresponding to the character sS (if it didn't exist yet) and run DFS(S, curs). This DFS does nothing but construct Hv that encodes all strings read down from v in Tv. And since each vertex of Hv encodes a distinct string, is the number of vertices of Hv.

This runs in O(|Tv|σ) time, since it can create a trie with |Tv| vertices in the worst case. Overall, it'd be O(N2σ) 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 |Tw|, add sv to Hw and make it Hv; then, DFS through the rest of Tv and complete the trie Hv 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 Hv that consists of one vertex.

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

It remains true that dif(v) is |Hv| — the number of vertices in the trie Hv, 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(N2) 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 Pr[]; take the vertex/vertices with lexicograhically maximum Pr[] (as many strings as possible which occur only once, etc).

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

Tags codeforces, round, 333, editorial, pictures!


  Rev. Lang. By When Δ Comment
en16 English Xellos 2015-11-29 20:49:38 16 Tiny change: 'sing maps in $O(N ' -> 'sing maps + Fenwick trees in $O(N '
en15 English 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 English Xellos 2015-11-25 18:20:31 2 Tiny change: 'ms in $O(k)$, but th' -> 'ms in $O(k^2)$, but th'
en13 English Xellos 2015-11-25 01:42:21 129
en12 English Xellos 2015-11-25 01:12:03 5769 and done
en11 English Xellos 2015-11-24 23:47:45 3357 Tiny change: 'akes $O(m^2n^2)$ time' -
en10 English Xellos 2015-11-24 23:25:07 1864 Tiny change: 'using STL map<>/set<> data stru' -> 'using STL `map<>`/`set<>` data stru'
en9 English 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 English Xellos 2015-11-24 23:01:15 305 Tiny change: '------\n\n\nIt's e' -
en7 English Xellos 2015-11-24 22:48:48 3940
en6 English Xellos 2015-11-24 22:23:59 507
en5 English Xellos 2015-11-24 22:07:30 1272 Tiny change: 'Hints:\n\n' -
en4 English Xellos 2015-11-24 21:37:47 3 Tiny change: 'm Codechef :D.\n\ndiv1E' -
en3 English Xellos 2015-11-24 21:37:12 877
en2 English Xellos 2015-11-24 20:39:12 2 (published)
en1 English Xellos 2015-11-24 16:26:52 109 Initial revision (saved to drafts)