Discussion @ 1167. Bicolored Horses @ Timus Online Judge

XueMao I wonder why somebody passed it only used less than 0.1 sec ! [4] // Problem 1167. Bicolored Horses 9 Apr 2003 17:19

I used DP , 0.8 sec , but some people only used 0.04 sec and uesd
less than 100K memory ! why ? How can they do it ? can anybody tell
me ?

Miguel Angel It can be done in O(n^2) (-) [3] // Problem 1167. Bicolored Horses 11 Apr 2003 00:25

> I used DP , 0.8 sec , but some people only used 0.04 sec and uesd
> less than 100K memory ! why ? How can they do it ? can anybody tell
> me ?

marius dumitran Re: It can be done in O(n^2) (-) [2] // Problem 1167. Bicolored Horses 27 Apr 2004 20:01

how?
i managed a 0.09 O(n^3) but how do u do n^2??
i might have an N^2 ideea but it n^2 memory......

Teragram Re: It can be done in O(n^2) (-) [1] // Problem 1167. Bicolored Horses 21 May 2004 14:11

X[i]: how many black horses are in the first i horses
Y[i]: how many white horses are in the first i horses

We use Dp.
F[i,j] = min { F[i-1,k] + (X[j]-X[k])*(Y[j]-Y[k]) } | K<J

The answer is F[K,N].

Suppose F[i,j] get the minimal value when k=k0.
Let W[i,j]=k0.

You can prove : w[i,j-1]<=w[i,j]<=w[i+1,j]

So you can solve this problem in o(n^2).

El_Groguet Re: It can be done in O(n^2) (-) // Problem 1167. Bicolored Horses 11 May 2013 23:09

Sorry, could you explain please what's k0?

Discussion of Problem 1167. Bicolored Horses