ROCK - Sweet and Sour Rock


A manufacturer of sweets has started production of a new type of sweet called rock. Rock comes in sticks composed of one-centimetre-long segments, some of which are sweet, and the rest are sour. Before sale, the rock is broken up into smaller pieces by splitting it at the connections of some segments.

Today's children are very particular about what they eat, and they will only buy a piece of rock if it contains more sweet segments than sour ones. Try to determine the total length of rock which can be sold after breaking up the rock in the best possible way.

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case, the first line of input contains one integer N - the length of the stick in centimetres (1<=N<=200). The next line is a sequence of N characters '0' or '1', describing the segments of the stick from the left end to the right end ('0' denotes a sour segment, '1' - a sweet one).

Output

For each test case output a line with a single integer: the total length of rock that can be sold after breaking up the rock in the best possible way.

Example

Sample input:
2
15
100110001010001
16
0010111101100000

Sample output:
9
13

hide comments
a161112225: 2018-09-05 20:24:22

why i am getting WA and in which test case ? i am trying with partition DP (iterative )

aman_sachin200: 2018-06-14 00:10:48

Awesome One!!

kalyanavuthu: 2018-04-16 04:50:52

Last edit: 2018-04-16 04:51:33
sinersnvrsleep: 2018-01-18 13:49:54

o(n3) solution is very easy plz give hint of o(n2) solution;

ashishranjan28: 2017-05-25 09:47:06

recursion partitioning + memoisation

nilabja16180: 2017-03-29 10:56:34

AC in one GO!

cake_is_a_lie: 2017-02-23 03:32:49

This problem can be solved in O(N) time, so for example on my computer I can solve instances with N=1000000 in <0.1s.

The constraints here are so loose that they will even pass an O(N^3) solution like MCM, which is sad as it's much more interesting to get the O(N) solution.

For those interested in a hint, there's a fairly obvious DP solution in O(N^2) and with a clever implementation it can be made to run in O(N) amortized time and O(N) memory. The heart of the solution is 5 simple lines of code, so it's not exactly difficult to implement either.

Last edit: 2017-02-23 14:48:40
gautam: 2017-02-22 12:11:33

nailed it :)

iam_ss: 2017-02-11 17:38:51

AC in first attempted. Very basic DP.

flyingduchman_: 2016-12-26 12:24:51

A modified Matrix Chain Multiplication algorithm (MCM) can solve it in O(n^3) using the dynamic programming(dp) approach. The idea is to generate all possible combination of sub-problems and derive a formula that solves the problem in bottom-up manner. Assuming you know the dp solution of MCM, let M[n][n] be a table where M[i,j] stores the solution of elements from i to j in given string. Generate all possible combination of array-index i, j, k i.e. i<=k<j. In the table each range(i to j) can have two properties like:

sweet = number of 1’s in range(i,j)

total = total segments of best choice i.e. sweet>sour.It’s the solution for element(i to j).

dp table can be of type rock like:

struct rock

{

int sweet,total;

};

Now in all possible combination of i, j, k there can be four cases:

1.(i == k) && (k+1 == j)

2. (i == k)

3. (k+1 == j)

4.not any of three above i.e. i, k, k+1, j are distinct.

Main logic: If number of 1’s (sweets) in between element index (i to j) < (total elements in range)/2 , total elements in range is the optimal solution.

otherwise, optimal solution = summation of sub-problems.

Now fitting the logic into the table for all those 4 cases and taking the maximum in each step will yield an optimal solution.


Added by:adrian
Date:2004-08-03
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002