codechef may12, problem MEDIAN

After 10 submissions, multiple WA and TLE, finally got problem MEDIAN in codechef may12 challenge accepted.

The problem is: given a sequence of 0 and 1, with at least one 1, and n<=30, find minimum number of steps to make them all 1. In each step you can choose a subarray with #1 >= #0 and flip all 0 to 1.

OK, you know n<=30 so you can represent all states with bitmap which fits into int. Then you do BFS search to start from initial configuration and look for (1<<30)-1. The hard part, at least to me, is to implement each transition in O(n) time. A naive approach is to try all possible subarray, there are O(n^2) of them, and add them to the queue. This will TLE for sure as it gets you a lot more useless states. An improvement is by observing that if a feasible interval, meaning #1>=#0, is included in another feasible interval, then there is no point try that subinterval. This gives O(n) next state instead of O(n^2). However, if you insist on finding feasible interval starting from each pos=0..n-1, it still takes O(n) time for each pos and you need O(n^2) time to find them. Maybe there is a way to do it in linear time, but I do not know how.

My idea is based on the observation: start at p1=0, then look for the rightmost p2 such that diff=#1 - #0 is minimized. Once we found p2, we check diff. If diff <0, then we know we are done, add next state into queue and update its dist. If diff ==0, then we can try p2=p2+1 in next iteration to look for a new p2. Otherwise diff > 0, then we move p1 to the right and stop when diff=0. If we end up with diff >0, that means there is no feasible interval within [p1..n-1], and we stop. Otherwise we have diff=0 so we record this interval, and in next iteration we will start with p2=p2+1. Clearly it is O(n) time and we have at most O(n) next state.

Now we prove the case diff>0 implies no feasible interval can appear within [p1..n-1]. Since diff >0, we know that either all [p1..p2] are 0, or p2 must be 1, otherwise we can take p2=p2-1 and we get a smaller diff. But if p2 is 1, then when we move p1 to p2, we have to have a feasible interval because p2 itself is a feasible interval. Therefore all [p1..p2] are 0. However, for a feasible interval to exist within p1..n-1, we have to have some 1 in this interval, then include this pos into [p1..p2] will give a smaller diff, which is a contradiction. Therefore we have a somewhat surprising result, if we fail to find a feasible interval between p1..n-1, then all p1..n-1 must be 0.


Implementation notes:
1. I forgot to clear map between testcases.
2. I was using a[i] instead of the a[i] value from bitmap conf.
3. To run all cases, the standard way is:
int ncase; cin >> ncase;
while(ncase--)
   solve();

User	Mem	Time	Lang
bb_1	1.6M	0.00	C	View Solution
adge1	2.8M	0.01	C++ 4.3.2	View Solution
lantimilan	2.8M	0.02	C++ 4.3.2	View Solution