Codeforces Round #333 — editorial

Revision en4, by Xellos, 2015-11-24 21:37:47

Hints:

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.

Tags codeforces, round, 333, editorial, pictures!

History

 
 
 
 
Revisions
 
 
  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)