Problem Name :- Fast And Furious Problem Link :- hackerearth/mindsweeper_1/algorithm/fast-and-furious/ Difficulty :- Easy , Adhoc Complexity :- O(1) One solution may be -> 1st turn , 1 to N soldiers of Gandalf army kill 1 to N/2 soldiers of Saurons army . 2nd turn , N/2+1 to N soldiers of Saurons army kill 1 to N/2 soldiers of Gandalf army . 3rd turn , N/2+1 to N soldiers of Gandalfs army kill N/2+1 to N soldiers of Saurons army. Thus only N/2 remains at end . Now you can verify that if in any turn more or less kilings are there then , optimality will not be maintained . For example , if in 1st turn , 1 to N soldiers of Gandalf army kill 1 to N soldiers of Saurons army . N soldiers of Gandalf will remain which is not optimal , similarly check for other cases . pastebin/N3x2xBp9
Posted on: Sun, 19 Jan 2014 19:41:39 +0000
Trending Topics
Recently Viewed Topics
© 2015