Skip to main content
Code Review

Return to Answer

factual correction
Source Link
abuzittin gillifirca
abuzittin gillifirca
  • 6.4k
  • 15
  • 25

  • Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.

  • Dont do IO in the constructor.

    Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.

  • Use plain arrays when the size is known. as in this case. use new[] operator. std::vector does bounds checking. arrays are faster.

    Dont do IO in the constructor.
- Use plain arrays when the size is known. as in this case. use new[] operator. std::vector does bounds checking. arrays are faster.

  • Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.

  • Dont do IO in the constructor.

  • Use plain arrays when the size is known. as in this case. use new[] operator. std::vector does bounds checking. arrays are faster.

  • Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.
  • Dont do IO in the constructor.
- Use plain arrays when the size is known. as in this case. use new[] operator. std::vector does bounds checking. arrays are faster.
added 174 characters in body
Source Link
abuzittin gillifirca
abuzittin gillifirca
  • 6.4k
  • 15
  • 25
  • Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.

    Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.

  • Dont do IO in the constructor.

  • Use plain arrays when the size is known. as in this case. use new[] operator. std::vector does bounds checking. arrays are faster.

  • Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.

  • Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.

  • Dont do IO in the constructor.

  • Use plain arrays when the size is known. as in this case. use new[] operator. std::vector does bounds checking. arrays are faster.

Source Link
abuzittin gillifirca
abuzittin gillifirca
  • 6.4k
  • 15
  • 25

  • Most importantly algorithm: Since the shortest path from top-left to any point on the grid is dependent on the points above and to the left of that point, dynamic programming can be used to calculate the path. It's O(MN) so it should give an answer in reasonable time for 1000*1000 grid. space complexity is O(MN) too. memory consumption will be about 2MB.