Codeforces Round #333 — editorial

Правка en4, от 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.

Теги codeforces, round, 333, editorial, pictures!

История

 
 
 
 
Правки
 
 
  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)