Page 1 of 1
10647 - Optimal House Placement
Posted: Mon May 10, 2004 11:56 am
by titid_gede
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-
Posted: Mon May 10, 2004 12:23 pm
by Adrian Kuegel
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.
Posted: Tue May 18, 2004 4:50 am
by kh9
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...
Posted: Sun Aug 08, 2004 3:27 pm
by Revenger
I've got many WA's
Please tell me what can be wrong? are there any tricks ?
Soory, I've found the error