Hi!
Today I faced this problem: https://www.hackerearth.com/codex-6-0/algorithm/dummy-4-1/.
Problem statement in short: there are ones and zeroes in two-dimensional array N × N. How many ways do exist between top-left corner and bottom-right corner, if you can travel in horizontal or vertical directions only (not only down/right but in any direction) and you cannot visit any cell twice? N ≤ 100
All accepted solutions are simple bruteforce, that gets TL on array 100x100 with all zeroes in it.
What is the approach to solve this problem?
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?