One improvement you can make to the step 2: Store the path you take initially without adding any new obstacles, and only try and add obstacles in those places. If we never hit an obstacle we add on our path - there's no point checking that location.
@@dasDull In real life - this constant factor is very significant. Especially since the starting path will generally be far far smaller than the whole grid. For me, this reduced the search space to 1/20th of what it was before.
Very nice video! A small improvement is that you don't need to try every single position for the additional barrier. You traverse the path without adding a barrier yet and if the next position hasn't been visited, is inside and isn't a barrier, then you add a barrier and simulate that path. After checking wether or not that leads to a cycle you remove the barrier and continue the algorithm.
I saw the same thing using set as a first solution, taking about 1.5 seconds. You saying, just put it in a boolean array, made me smack myself... Doing that, I got down to 0.03 seconds. (g++ 14).
There is a way to solve in O(N*M) total, for second part. If we view it as a functional graph, one new obstruction changes upto 4 edges, and you can check for each of the neighboring nodes which is reached first, upto 4 times ( because we can compute steps or say impossible, required to go from a to b in functional graph )
Nice. Can't wait to see if there is a more optimized way to solve the second part. Also, can you explain the hash a little further? I used a 3D boolean array to check if we visited the same cell from the same direction
More optimized solution: create a map of every possible combination of position + rotation, and then, after adding additional obstacle in X, Y, you need to update every obstacle in this line and row. It should work, but too much hustle for this simple problem
One small optimization: you don't need to place # in places when guard never have been (not X), and if there is no obstacle on adjacent rows and lines.
Loving these videos! Really interested to hear if there's a linear time complexity solution. The fact the added hash can 'reflect' the guard from multiple directions makes it much more challenging.
Optimization is remember the path you went on and look for obstacles directly to the left of where you were going. Let's call those Ob_i. Then you simply need to find locations where adding an obstacle would cause you to change your course and end up running into some Ob_i. Edit: Similarly the rest of the locations could be found by looking directly backwards from anywhere along your path.
Isn't it better to use a counter each time you move to another cell, updating it and adding to the count, instead of maintaining a set or boolean array
Man I really wonder what you did for Day 9. It was easy enough to come up with two-pointer solution with O(n) time and O(1) space for part 1 but p2 tripped me up. Every other solution I've seen is just wildly inefficient.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
One improvement you can make to the step 2: Store the path you take initially without adding any new obstacles, and only try and add obstacles in those places.
If we never hit an obstacle we add on our path - there's no point checking that location.
True, but if the path is a significant part of the grid this does only improve by a small constant factor.
@@dasDull In real life - this constant factor is very significant.
Especially since the starting path will generally be far far smaller than the whole grid.
For me, this reduced the search space to 1/20th of what it was before.
@@dasDull This significantly sped up my solution
Very nice video! A small improvement is that you don't need to try every single position for the additional barrier. You traverse the path without adding a barrier yet and if the next position hasn't been visited, is inside and isn't a barrier, then you add a barrier and simulate that path. After checking wether or not that leads to a cycle you remove the barrier and continue the algorithm.
I saw the same thing using set as a first solution, taking about 1.5 seconds. You saying, just put it in a boolean array, made me smack myself... Doing that, I got down to 0.03 seconds. (g++ 14).
There is a way to solve in O(N*M) total, for second part. If we view it as a functional graph, one new obstruction changes upto 4 edges, and you can check for each of the neighboring nodes which is reached first, upto 4 times ( because we can compute steps or say impossible, required to go from a to b in functional graph )
approach sounds similar to a post on the r/adventofcode subreddit, same idea?
Nice. Can't wait to see if there is a more optimized way to solve the second part. Also, can you explain the hash a little further? I used a 3D boolean array to check if we visited the same cell from the same direction
More optimized solution: create a map of every possible combination of position + rotation, and then, after adding additional obstacle in X, Y, you need to update every obstacle in this line and row. It should work, but too much hustle for this simple problem
One small optimization: you don't need to place # in places when guard never have been (not X), and if there is no obstacle on adjacent rows and lines.
Great work you are doing. Thank you man!
Loving these videos! Really interested to hear if there's a linear time complexity solution. The fact the added hash can 'reflect' the guard from multiple directions makes it much more challenging.
Hey! It would be really cool to see you tackling Everybody Codes event, Quest 19!
Optimization is remember the path you went on and look for obstacles directly to the left of where you were going.
Let's call those Ob_i.
Then you simply need to find locations where adding an obstacle would cause you to change your course and end up running into some Ob_i.
Edit: Similarly the rest of the locations could be found by looking directly backwards from anywhere along your path.
Hi @Errichto,is there IOI camp 2024 playlist
I keep getting "Denial of judgement" on my solution. Can someone please explain what this is and how to deal with it?
Isn't it better to use a counter each time you move to another cell, updating it and adding to the count, instead of maintaining a set or boolean array
In part 1
@@abdulrafay1976 You may overcount previous positions if you do so
You can visit the same cell more than once
This is very similar to what I did, I mark in the graph with a "V" (visited) and only count the times I see a "."
@@suchithsridhar same here marked them with 'X' and next time only shifts the row col
Man I really wonder what you did for Day 9. It was easy enough to come up with two-pointer solution with O(n) time and O(1) space for part 1 but p2 tripped me up. Every other solution I've seen is just wildly inefficient.
lord errichto pls come back. Start from day 14
sir whre is day 7
lord errichto pls come back. Start from day 14
lord errichto pls come back. Start from day 14