agul's blog

Number of ways between two vertices
By agul, history, 9 years ago, translation, In English

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?

  • Vote: I like it
  • +68
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +383 Vote: I do not like it

Watch this epic video: https://www.youtube.com/watch?v=Q4gTV4r0zRs :D

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Well, it kinda ends like this, doesn't it? "With modern algorithms..."

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    That was so touching man. I so fucking liked it :P

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

...and what do zeroes and ones mean? You cannot go over the ones?

→ Reply