I have to ask
Is there any better algorithm to solve this problem instead of using backtracking ?
After contest I discovered, that office could be placed not only in square, where some people live, but in empty square too (!!). So could anyone tell me, how can I speed up backtracking for this problem (if doesn't exist any other method ) ?
Best regards
DM
Last edited by Dominik Michniewski on Wed Jul 14, 2004 8:46 am, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Is there any better algorithm to solve this problem instead of using backtracking ?
I would rather call it brute force than backtracking.
But I think there is no other algorithm than the naive one, trying all possibilites. But you can see that there are only (25 over 5) = 53130 possibilities, and for each possibility you can check in O(n) (where n is the number of non-empty squares) what the costs are.
Thanks for reply ... I think too, that brute-force (backtracking) is the only possibilities, but I thought , that I was wrong
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Hi,
I also use simple bruteforce. trying to put the offices for all possible combinations .But i m keep getting wrong answer. Some one can help me giving some AC Sample I/O or some hints. Thanx in advance.
Regards
_______________________________________________ faizur
I also have a problem with this one, but it's NOT OK on the example test cases.
currently no idea on what is the problem
anyone please point out the bug!
Hi, I've looked at all of the posts and I've tried all of the input/output posted + more (and checked with uDebug to see if input/output matches), but to no avail.
I'm still getting WA.
If anybody can tell me what is wrong with my code I'd be really grateful