Apr 1, 2015

TopCoder SRM 654 DIV1

Practice Record: TopCoder SRM 654 DIV1

250 SquareScores

Problem Statement

http://community.topcoder.com/stat?c=problem_statement&pm=13694

My Solution

DP: Let's say dpExp[i][j] is the expected value of the postfix run-length of jth character at the end of substring S[0..i]. At (i+1)th character, if (i+1)th character is same as ith character, the score is increased by dpExp[i][j]+1. (Imagine constant substring 'aaa' whose expected postfix run-length of 'a' is three and if 4th character is also 'a', the score is increased by four) So you can calculate dpExp[i][j] one by one.

450 SuccessiveSubtraction2

Problem Statement

http://community.topcoder.com/stat?c=problem_statement&pm=13700

My Solution

Inserting two bracket is actually the same as picking two subarray from the origin array and inverse their sign. (Note that the first element is always plus and the second is always minus. You can not include the first and second one in those subarrays.) So you only need to pick up two sub arrays so their sum is maximized. To calculate it in a reasonable order, I pre-calculate the max values of sums of subarray out of [0..i] (first subarray max) and one out of [i..n] (second subarray max). After calculating it, I just iterate all possible 'pivot' elements which sprit the original array into two groups and sum first max and second max to get the total max.