Привет!
Сегодня встретилась такая задача: https://www.hackerearth.com/codex-6-0/algorithm/dummy-4-1/.
Вкратце суть: в двумерной таблице расставлены нули и единицы. Сколько существует способов пройти от нижнего правого угла до верхнего левого угла в таблице N × N только по нулям, если ходить можно только по горизонтали и вертикали (не только вверх/влево, а во все стороны), причём нельзя посещать одну клетку дважды? N ≤ 100
Все решения, получившие 100 баллов, -- это просто полный перебор, который валится по TL на таблице 100x100 со всеми нулями.
Как можно решить такую задачу?
Watch this epic video: https://www.youtube.com/watch?v=Q4gTV4r0zRs :D
That was such an emotional roller coaster.
The first couple are solved quickly and so we think all is well but then it all starts to fall apart till that line about 11 by 11 taking more time than the universes age.
BUT THEN.
Latest algorithmic techniques save the day and compute answers in seconds. So here I am thinking there is still hope till that guy goes 16 by 16 takes 20 to 30 minutes.
All in all, not the worst way to pass 8 minutes.
I was hoping that it ends with something like:
And then the kids become computer scientists and they live happily ever after.
Well, it kinda ends like this, doesn't it? "With modern algorithms..."
That was so touching man. I so fucking liked it :P
This paper includes the video link (check out introduction and [4] :D) along with the algorithmic ideas:
https://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_64/tcstr_13_64.pdf
...and what do zeroes and ones mean? You cannot go over the ones?