10647 - Optimal House Placement

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10647 - Optimal House Placement

Post 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.

Kalo mau kaya, buat apa sekolah?

Adrian Kuegel
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post 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.

New poster
Posts: 4
Joined: Fri Jun 06, 2003 11:29 pm

Post 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...

Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post 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

Post Reply

Return to “Volume 106 (10600-10699)”