### paramsingh's blog

By paramsingh, history, 2 years ago, ,

Hi there. I've been trying to solve http://www.spoj.com/problems/AKBAR/ for some time, but the only thing I can seem to come up with is starting a BFS from each of the soldiers as the source until the soldier's strength depth. However, that approach gives me a TLE. Any help regarding how to solve this problem would be appreciated. Thanks.

Here's the code for my approach that I tried (TLE): https://gist.github.com/paramsingh/81d728295e6bd01860a0

•
• -1
•

 » 2 years ago, # |   0 say ALLAHU AKBAR and problem will solve itself.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +4 Making FUN with one's Religion is not funny :)
•  » » 4 weeks ago, # ^ |   -19 RVyrodov You are a cheap minded person. You can't have fun with other religions. It is a very bad habit.
 » 2 years ago, # |   +2 using memset in lines 39+40 gave you the TLEyou don't need to do it for every soldier, if any city is previously visited by another soldier, then the flag turns false...remember that "every city is protected by one and only one soldier.According to Akbar , this is the optimum placement."if you need more help, just tell me ^_^
•  » » 2 years ago, # ^ |   +1 Oh man, that was a really stupid mistake! Thanks a lot for the help, I've got it accepted now.:)
•  » » 18 months ago, # ^ |   0 Can you please tell me how to resolve TLE in this code http://ideone.com/ljgRhi ?
•  » » » 18 months ago, # ^ |   0 rghv same mistake:using memset in line 42 gave you the TLEyou don't need to do it for every soldier, if any city is previously visited by another soldier, then you should return false...remember that "every city is protected by one and only one soldier.According to Akbar , this is the optimum placement."
•  » » » » 18 months ago, # ^ |   0 Thank you.
•  » » 4 weeks ago, # ^ |   0 what is wrong in my soluton for AKBAR? https://ideone.com/AonT8k
•  » » » 4 weeks ago, # ^ |   0 I didn't even read a problem's statement, but by just looking to your code, I see some not reliable things... You should write:for (it = adj[s].begin(); it != adj[s].end(); it++) And since you don't need iterator, You better use:for (int value : adj[s])
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 ROIgold it did'nt make any difference.now?
 » 18 months ago, # |   0 Hey, I also used the same approach and getting TLE. Here's my code http://ideone.com/ljgRhi. Any help would be appreciated.