Codeforces Round #359 (Div. 1) - C. Optimal Point

Problem Statement:
http://codeforces.com/contest/685/problem/C

Summary:
Find the minimum point M (x, y, z) in Z^3 such that the maximum Manhattan distance between M and a set of points {(x[i], y[i], z[i]) in Z^3} of size <= 100000 is the minimum. Manhattan distance between two points (x, y, z) and (a, b, c) is defined as |x-a| + |y-b| + |z-c|. Furthermore, x, y and z is in [-10^18, 10^18].

Codeforces Rockethon 2015 Problem E1/E2 - Subarray Cuts

Problem Statement:
513E2 - Subarray Cuts

Solution:
This is another excellent problem, for which its solution demonstrates the power of dynamic programming. Unfortunately the implementation is very error prone due to the handling of edge cases (at least for me). The official editorial to this problem is also unfortunately very hard to read, partly because the TeX are not typed correctly. Anyway, here is my note about this problem.

The problem is difficult because we are presented with modulus operations. When we try to do a naive DP by keeping track of the value of \(s_j\), we will soon realize that we also need to keep track of the value for \(s_{j-1}\), which inflates the space search very badly. As it turns out, there is another way of looking into the problem which I think is very clever.