Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### agul's blog

By agul, history, 9 years ago, translation,

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?

• +68

 » 9 years ago, # |   +383 Watch this epic video: https://www.youtube.com/watch?v=Q4gTV4r0zRs :D
•  » » 9 years ago, # ^ |   +18 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.
•  » » 9 years ago, # ^ |   +52 I was hoping that it ends with something like: "And that, kids, is why you should study algorithm" And then the kids become computer scientists and they live happily ever after.
•  » » » 9 years ago, # ^ |   +3 Well, it kinda ends like this, doesn't it? "With modern algorithms..."
•  » » 9 years ago, # ^ |   -8 That was so touching man. I so fucking liked it :P
•  » » 9 years ago, # ^ | ← Rev. 3 →   +3 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
 » 9 years ago, # |   +8 ...and what do zeroes and ones mean? You cannot go over the ones?