diff options
Diffstat (limited to '2025/README.md')
| -rw-r--r-- | 2025/README.md | 25 |
1 files changed, 25 insertions, 0 deletions
diff --git a/2025/README.md b/2025/README.md index c1d3f2c..d75a4d3 100644 --- a/2025/README.md +++ b/2025/README.md | |||
| @@ -148,3 +148,28 @@ and in fact I wasted a lot of time searching a quadratic or O(n^2log n) | |||
| 148 | solution before I focused on formalizing a cubic one. The problem is that | 148 | solution before I focused on formalizing a cubic one. The problem is that |
| 149 | I did not have smaller inputs to try my code against, so I this solution | 149 | I did not have smaller inputs to try my code against, so I this solution |
| 150 | was too slow I did not have any way to check that it was at least correct. | 150 | was too slow I did not have any way to check that it was at least correct. |
| 151 | |||
| 152 | EDIT (about 12h after solving part 2): apparently my algorithm is not | ||
| 153 | entirely correct. In particular, it can fail by selecting a rectangle | ||
| 154 | that is completely external to the figure and none of whose sides overlaps | ||
| 155 | any of the lines. | ||
| 156 | |||
| 157 | For example with this input: | ||
| 158 | |||
| 159 | ``` | ||
| 160 | 101,51 | ||
| 161 | 101,0 | ||
| 162 | 0,0 | ||
| 163 | 0,2 | ||
| 164 | 1,2 | ||
| 165 | 1,1 | ||
| 166 | 100,1 | ||
| 167 | 100,50 | ||
| 168 | 99,50 | ||
| 169 | 99,51 | ||
| 170 | 101,51 | ||
| 171 | ``` | ||
| 172 | |||
| 173 | The first version of my program return 4851 instead of 202. I added a | ||
| 174 | check for this case in `b-fixed.py`, hopefully it works in 100% of the | ||
| 175 | cases now. | ||
