Timeline for Hackerrank Queen's Attack II
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2020 at 13:24 | history | edited | CommunityBot |
Commonmark migration
|
|
| Feb 4, 2017 at 16:24 | vote | accept | Jianmin Chen | ||
| Feb 4, 2017 at 9:33 | comment | added | Jianmin Chen | it is easy to write code using HashSet and encapsulate all directions in one or two arrays, avoid to get into the detail of each direction in the code. Even you add/ remove some directions, you do not need to refactor the code, only touch the two arrays for directions. That is something like 'Open for extension, close for change' code. But in theory, as you analyze, your approach is more time efficient, but it takes extra effort to take care each direction. For me, I created bugs and then I learned lessons, took me 3 submissions in the contest. | |
| Feb 4, 2017 at 9:05 | comment | added | JS1 | @JianminChen I see, you had the same idea but your code was more complex. Hopefully, you can learn something from this shorter code and it will help you in your next challenge. | |
| Feb 4, 2017 at 8:56 | comment | added | Jianmin Chen | you are correct on time complexity analysis. It is less time to avoid using hashset, however, I did write the same idea in the contest, the code is gist.github.com/jianminchen/ea01caea42fafa41a5085b36e1b0059a. But I ended up using more than 2.5 hours to write and debug. The way you write as your comment says "Initialize distance to edge of board in each direction" is to find maximum value first, and then compare to find minimum one. The code is shorter than mine in the contest. Your comment is very clear, is very instructional, code is very lean. | |
| Feb 4, 2017 at 8:30 | comment | added | JS1 |
@JianminChen I disagree. Your program does exactly k HashSet insertions followed by up to 4n HashSet finds. My program does exactly k distance comparisons which are less expensive than HashSet insertions. So my program is faster in all cases.
|
|
| Feb 4, 2017 at 8:04 | comment | added | Jianmin Chen | My algorithm is not efficient for special case, for example, when there is no obstacle but still start from queen position increment one by one in each direction, size of n, up to 100000; but your algorithm also is not efficient for special case, such as the minimum obstacle for each direction can be found just by walking one or two steps from queen position, first obstacle to meet is the minimum one, but instead go over all obstacles to compare with minimum value. And in fact all obstacles k can up to 100000. | |
| Feb 3, 2017 at 19:46 | history | answered | JS1 | CC BY-SA 3.0 |