Problem 081
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.

 Posts: 15
 Joined: Sat Dec 17, 2011 7:15 pm
 Location: Charlottesville, Virginia
Problem 081
Hello,
I'm having trouble with this problem. My algorithm works just fine for the small sample matrix and seems to be working how I think it should. Is it fair to say that once either the row number or the column number equals 0 (with the matrix going from 0 to 79), you add up the numbers going up the side that you have reached? That's the only problem I can think of with my code.
Thanks
I'm having trouble with this problem. My algorithm works just fine for the small sample matrix and seems to be working how I think it should. Is it fair to say that once either the row number or the column number equals 0 (with the matrix going from 0 to 79), you add up the numbers going up the side that you have reached? That's the only problem I can think of with my code.
Thanks
Re: Problem 081
Yes, you must get to the bottom right corner using only right and down directions, so when you hit a side (right or bottom), you must add all of the numbers from there to the corner. For an 80x80 matrix, it will always be 159 numbers total.ParadiceCity9 wrote:I'm having trouble with this problem. My algorithm works just fine for the small sample matrix and seems to be working how I think it should. Is it fair to say that once either the row number or the column number equals 0 (with the matrix going from 0 to 79), you add up the numbers going up the side that you have reached? That's the only problem I can think of with my code.
I think most programmers use (0,0) for the topleft square.

 Posts: 15
 Joined: Sat Dec 17, 2011 7:15 pm
 Location: Charlottesville, Virginia
Re: Problem 081
I'm getting 159 numbers is the thing. Would you mind taking a look at my code? It's in Java so it should be fairly easy to read/understand.
Re: Problem 081
I'll look at the code, if you include an explanation of your solution and I agree that the algorithm you explain will solve the problem.
Problem 81
Does anybody have any suggestions for solving Problem 81?
I have set up a binary tree to traverse every possible path, but bruteforcing it like this looks like it will take a while. Would something like Dijkstra's algorithm be a good fit for this problem?
I've been running my code for a few hours now and it looks like I have a long time to go.
Thanks,
Jon
I have set up a binary tree to traverse every possible path, but bruteforcing it like this looks like it will take a while. Would something like Dijkstra's algorithm be a good fit for this problem?
I've been running my code for a few hours now and it looks like I have a long time to go.
Thanks,
Jon
 RishadanPort
 Posts: 78
 Joined: Mon Jun 10, 2013 7:31 am
Re: Problem 81
Funny.
I just solved this one like 2 minutes ago. Not a very terribly difficult problem to do  a very basic Dynamic Programming problem...
I suggest you to do a bit of research on DPs.  Think about how you can break this problem down into sub problems.
I just solved this one like 2 minutes ago. Not a very terribly difficult problem to do  a very basic Dynamic Programming problem...
I suggest you to do a bit of research on DPs.  Think about how you can break this problem down into sub problems.
Rishada is the gateway to free trade—but the key will cost you.
Re: Problem 081
@jlillest
FYI, problem numbers below 100 are padded with leading 0's to make then 3digit numbers. You may then find that answer already exists to your question(s) in many cases by searching the proper topic.
FYI, problem numbers below 100 are padded with leading 0's to make then 3digit numbers. You may then find that answer already exists to your question(s) in many cases by searching the proper topic.
When you assume something, you risk being wrong half the time.
Re: Problem 081
Just wanted to share my failed attempt at solving this XD (one from top left corner down and one from bottom right corner up) ... cutting and patching the two "minimized" trails together didn't work either XD grrr ... couldn't make it an easy one, could you? XD
366541_5799d51e95657e1a227f2cb86bd181de
 angzhiping
 Posts: 32
 Joined: Sat Aug 09, 2014 3:51 pm
 Location: Jurong East, Singapore
 Contact:
Re: Problem 081
How do you come up with the "minimized" trail?solarmew wrote:Just wanted to share my failed attempt at solving this XD (one from top left corner down and one from bottom right corner up) ... cutting and patching the two "minimized" trails together didn't work either XD grrr ... couldn't make it an easy one, could you? XD
170825_b3d528c2bf87aaeff2a0ff93382fba94
Re: Problem 081
Just a simple check if the number to the right(left) is smaller than the number above(below) the current position in the matrix, depending on which way you're going (staring on top or bottom). I didn't expect this to work because I figured that sometimes you would have to pick a higher number because the following sequence would contain smaller numbers, but just wanted to try the easy way first just in case...
366541_5799d51e95657e1a227f2cb86bd181de

 Posts: 5
 Joined: Fri Jun 19, 2015 2:50 pm
Re: Problem 081
i tried applying djikstra algorithm for this problem
in the 5x5 matrix till the index (3,2) algorithm is working fine .
However, wrong number is getting picked for the neighbor of (3,2)
i.e. (3,2) has two valid neighbor node.
Right (4,2) = 111
Down(3,3) = 121
When we calculate distance till (3,2) = 131 + 201 + 96 + 342 + 746 + 422 = 1938
Now, we need to select either right or down node. since right node has lesser weight(111) , my algorithm is selecting it .
and the answer is printing as 1938 + 111 + 956 + 331
However, the path that should be taken is 1938 + 121 + 37 + 331 and this is the minmal path.
Can someone correct my understanding ?
in the 5x5 matrix till the index (3,2) algorithm is working fine .
However, wrong number is getting picked for the neighbor of (3,2)
i.e. (3,2) has two valid neighbor node.
Right (4,2) = 111
Down(3,3) = 121
When we calculate distance till (3,2) = 131 + 201 + 96 + 342 + 746 + 422 = 1938
Now, we need to select either right or down node. since right node has lesser weight(111) , my algorithm is selecting it .
and the answer is printing as 1938 + 111 + 956 + 331
However, the path that should be taken is 1938 + 121 + 37 + 331 and this is the minmal path.
Can someone correct my understanding ?
Re: Problem 081
I sent a private message with some explanation.srinathmkce wrote:Can someone correct my understanding ?
_{Jaap's Puzzle Page}