Asia-Pacific Informatics Olympiad 2010 (TODO)

1. Commando:

• First observation:javascript:void(0) We could feel the Dynamic Programming property in this problem. Indeed, the 20% test cases could be solve by using 2 for-loops.
• From the first observation, we define d[i] = maximum adjusted effectiveness achievable by splitting the sequence in some way from beginning up to i. To get the 20% test cases, d[i] = max (d[j] + x' of (x[j+1], ... x[i])) for all 0 <= j
• Second observation, since n <= 10^6. It makes me think of an algorithm that runs time in O(nlogn) or O(n). There are two approaches I can think of here, either:
• We can prove that the sequence d[i] holds a certain ordering property and a binary search will find a suitable solution. (if succeeded, this takes O(nlogn) in running time)
• We maintain a movable pointer j (as described above) to the places we think the sequence should be split up. Also, notice that since a < 0, the larger x, the smaller x'.
• Bingo! Now I think the second approaches looks more promising. We know that f(x) = ax^2 + bx + c is a parabola having a maximum. Unless it is always < 0, we want the f(x') where x' = x[i] + ... + x[i+k] to be positive so that d[i+k] = f(x') + d[i].
• If the Let's x* is the larger solWe need at some point of x0 > 0, f(x0) is maximum so that the