901001's blog

Can someone help me how to solve this problem
By 901001, 13 years ago, In English
Can someone help me how to solve this problem.I use greedy algorithm,every time I find the point which can destroy most rocks,but it wrong answer. I cannot find what data make the solution WA. Can someone tell me how to solve it?
thanks in advance!
  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Greedy is incorrect. Solution is optimized search. There is O(2^n) search algorithm which fits in time limit.

→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I thought of a 2^25 times 25 algo. Will it pass the limit ?

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
111111
001000
000100
010010

Here are four "greediest" points at first move, I think, but two of them lead your algorithm to wrong way with three bombs instead of two.
→ Reply
13 years ago, # |
  Vote: I like it -6 Vote: I do not like it

You can solve this problem using Hungarian algorithm.
http://en.wikipedia.org/wiki/KM_algorithm

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    No can not solve this problem using Hungarian algorithm.
    → Reply