Codeforces Round #333 — editorial
Difference between en2 and en3, changed 877 character(s)
![ ](http://memeobrazky.com/wp-content/uploads/2012/09/trollface_hi_res.png)Hints:↵
↵
div2A: Try conversions between bases.↵
↵
div2B: Solve a simpler version of the problem where $A_{i+1} \neq A_i$ 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(N^2)$. Read my editorial of TREEPATH from Codechef :D.↵
↵
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.

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)