You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] Need help with hackerrank problem (dynamic programming)

Problem code
My solution

I am trying a simple recursive approach here. From each dimension, I am checking whether or next I can move forward to next dimension. If so I am moving there and return back to the present position to check whether backward movement is possible or not.

Problems I am facing :

1) If I comment out one recursion (either), the answer becomes zero.
2) If both recursions are present then it is infinite loop
3) In first if statement if I remove arr[i]-- or in second if I remove arr[i]++, I am getting wrong answer (but no infinite loop or zero as the answer).

Where have I gone wrong? Please help

p.s. Is there any other approach for this problem?

asked 25 Aug '15, 11:41

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

closed 10 Sep '15, 11:18

The question has been closed for the following reason "The question is answered, right answer was accepted" by dragonemperor 10 Sep '15, 11:18


I guess your "infinite loop" isn't infinite but rather 2^N for a somewhat big N.

The reason is: You're not using DP yet. Enumerating all possibilities is far to slow. Check waht your state during the recursion is and memoize it (just do it for 1d - high dimensions wont run in that way anyway). To get to higher dimensions think about how you can construct higher dimensional paths out of the 1d-version.

link

answered 27 Aug '15, 05:50

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

how can I store the states? I mean maximum dimension is 10 and each dimension can have value upto 100. So I will require a 100^10 element array to store each state. Correct me if I am wrong.

And can you elaborate that 2^n part? n is 10 at max. So 2^10 = 1024 isn't too large I think

(27 Aug '15, 10:37) dragonemperor3★

I'm sorry, I didn't use matching notation. I meant 2^m, m being the length of the path. m is the recursion depth of your algorithm, splitting (except on the edges of the square) 2 times per call yields 2^m for the 1-n-case.

Youre completely right with your concern about storage space for high n, but it doesn't help not to store, your algorithm as is will be too slow by far.

Use your algorithm with memo for n=1, and think about how to compute the value for n>1 out of solving n one dimensional problems.

(27 Aug '15, 20:48) ceilks7★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,172
×310
×40

question asked: 25 Aug '15, 11:41

question was seen: 2,741 times

last updated: 10 Sep '15, 11:18