n00bie's blog

By n00bie, history, 2 years ago, In English

This problem was in recent codechef contest

https://www.codechef.com/COOK98B/problems/OETW

It's actually very simple, but I could not see that at first, and reduced it to the following subproblem (even the reduction might be wrong, but that doesn't matter):

Given a binary array of size n, we need the maximum subarray sum for every size k = 1..n

Can this problem be solved for n<=2e6 ? I can't think of anything better than O(n^2)

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By n00bie, history, 2 years ago, In English

My topcoder arena doesn't seem to open, or respond, at all. Is anyone else having the same issue?

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it