ashishranjan2828's blog

http://www.spoj.com/problems/RANDG/

By ashishranjan2828, history, 8 years ago, In English

i hv tried this question with naive ....

but i think it can be done with the help of dp...

any help??

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes, it can be done in O(N) with prefix/suffix sums. Let gi be the amount of green squares in the prefix [1, i] and ri be the amount of red squares in the suffix [i, N]. Then the answer is the minimum gi + ri + 1.

→ Reply