10647 - Optimal House Placement

titid_gede · Post by **titid_gede** » Mon May 10, 2004 11:56 am

can you give me how to solve this problem? at first sight i think it can be solve by binary search, but since there could be possible maximum value, i'm going mad now.

-titid-

Adrian Kuegel · Post by **Adrian Kuegel** » Mon May 10, 2004 12:23 pm

Find a function for the costs, if you place a house between two adjacent houses of friends. Then find minimum of that function, and evaluate it efficiently (hint: use partial sums). Take the best result of all adjacent house pairs.

kh9 · Post by **kh9** » Tue May 18, 2004 4:50 am

I did that, and got correct results for the sample test cases, but still got WA. Is there some subtle thing that I've missed?
----------------
Update: ok, problem fixed. it's an int overflow mistake (what else is new)...
for whatever reason i stored the locations in an int array, while all other arrays are long long...

Revenger · Post by **Revenger** » Sun Aug 08, 2004 3:27 pm

I've got many WA's
Please tell me what can be wrong? are there any tricks ?

Soory, I've found the error