Need to shorten run-time in my program -COMPUTER OLYMPIAD-

viv.

THE PROBLEM----> Number Triangles
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30. PROGRAM NAME: numtri
INPUT FORMAT
The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
SAMPLE INPUT (file numtri.in)
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
OUTPUT FORMAT
A single line containing the largest sum using the traversal specified.
SAMPLE OUTPUT (file numtri.out)
30


MY CODE ---->
[code]
VAR fio:text;
nums:ARRAY[1..1000,1..1000] OF 0..100;
moves:ARRAY[1..1000] OF boolean;
curpos,i,j,r:1..1000;
sum,max:0..100000;
flag:boolean;
BEGIN
assign(fio,'numtri.in');
reset(fio);
readln(fio,r);
FOR i:=1 TO r DO
BEGIN
FOR j:=1 TO i DO read(fio,nums[i,j]);
readln(fio);
moves[i]:=false;
END;
close(fio);
max:=0;
REPEAT
FOR i:=r DOWNTO 1 DO
BEGIN
IF NOT moves[i] THEN
BEGIN
moves[i]:=true;
break;
END
ELSE moves[i]:=false;
END;
sum:=0;
curpos:=1;
FOR i:=1 TO r DO
BEGIN
IF moves[i] THEN curpos:=curpos+1;
sum:=sum+nums[i,curpos];
END;
IF sum>max THEN max:=sum;
UNTIL curpos=r;
assign(fio,'numtri.out');
rewrite(fio);
writeln(fio,max);
close(fio);
END.
[/code]

The above code basically has a 'binary' array (moves) and uses it to keep track of the possibility being searched . After every repeat loop, it adds 1 until it reaches (111111111)R.
my program works, but takes to long when presented with a 1000 X 1000 triangle.
Any suggestions?

Unknown

Rather than doing it brute force (checking all possible ways), you could think of a better algorithm which doesn't need that amount of calculations or steps. If I understood correctly, the algorithm you are using has 2^1000 steps on a 1000 lines triangle - this is way too much.

Here's my proposal:

Add the numbers from bottom up and only remember the biggest sum. Also remember from which side you were coming from.

1.

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

2.

7
3 8
8 1 0
7R 12L 10R 10L (L=Left, R=Right, 4+2 = 6 < 5+2 = 7, so take 7 coming from Right ...)
4 5 2 6 5

3.

7
3 8
20R 13L 10RL (R or L, doesn't matter)
7R 12L 10R 10L
4 5 2 6 5

4.

7
23L 21L
20R 13L 10RL
7R 12L 10R 10L
4 5 2 6 5

5.

30L
23L 21L
20R 13L 10RL
7R 12L 10R 10L
4 5 2 6 5

Now it's very easy to get the right path from top to bottom. Simply start at the top element and follow the directions:
LLRL = 7+3+8+7+5 = 30

Hope it's clear enough. This algorithm has linear complexity (O(n)) instead of exponential (O(2^n)), which simply means that it is [b]much[/b] faster with bigger ns than the brute force one.

tron.

: THE PROBLEM----> Number Triangles
: Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
: 7
: 3 8
: 8 1 0
: 2 7 4 4
: 4 5 2 6 5
: In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30. PROGRAM NAME: numtri
: INPUT FORMAT
: The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
: SAMPLE INPUT (file numtri.in)
: 5
: 7
: 3 8
: 8 1 0
: 2 7 4 4
: 4 5 2 6 5
: OUTPUT FORMAT
: A single line containing the largest sum using the traversal specified.
: SAMPLE OUTPUT (file numtri.out)
: 30
:
:
: MY CODE ---->
: [code]
: VAR fio:text;
: nums:ARRAY[1..1000,1..1000] OF 0..100;
: moves:ARRAY[1..1000] OF boolean;
: curpos,i,j,r:1..1000;
: sum,max:0..100000;
: flag:boolean;
: BEGIN
: assign(fio,'numtri.in');
: reset(fio);
: readln(fio,r);
: FOR i:=1 TO r DO
: BEGIN
: FOR j:=1 TO i DO read(fio,nums[i,j]);
: readln(fio);
: moves[i]:=false;
: END;
: close(fio);
: max:=0;
: REPEAT
: FOR i:=r DOWNTO 1 DO
: BEGIN
: IF NOT moves[i] THEN
: BEGIN
: moves[i]:=true;
: break;
: END
: ELSE moves[i]:=false;
: END;
: sum:=0;
: curpos:=1;
: FOR i:=1 TO r DO
: BEGIN
: IF moves[i] THEN curpos:=curpos+1;
: sum:=sum+nums[i,curpos];
: END;
: IF sum>max THEN max:=sum;
: UNTIL curpos=r;
: assign(fio,'numtri.out');
: rewrite(fio);
: writeln(fio,max);
: close(fio);
: END.
: [/code]
:
: The above code basically has a 'binary' array (moves) and uses it to keep track of the possibility being searched . After every repeat loop, it adds 1 until it reaches (111111111)R.
: my program works, but takes to long when presented with a 1000 X 1000 triangle.
: Any suggestions?
:
:

viv.

Thanks, it worked, is that the same as recursion
?

Unknown

Recursion is something else. You could do this with recursion though, but it would be slower. The idea is pretty much the same, but it would take much more steps (this is because this pyramid is not a binary tree - there is more than one way to get from A to .

Here's an example in pseudo code.
In this example each element of the pyramid is called a "node" which
has two or no children. This recursive algorithm returns only the highest possible sum, but not the way. However, it could be easily altered, so that it would return the way too.

[code]
function getHighestSum(n : Node) : Integer;
if (n has no children) then return n.number;
s1 = getHighestSum(n.left);
s2 = getHighestSum(n.right);
return max of (s1,s2);
end;
[/code]

As mentioned above, the idea behind this algo is the same as described before. But it takes many steps more than the non-recursive one. It will also take more execution time because it is recursive (calls, stack frames, etc.) Actually, this algo would be much slower than the other one, because it is calculating the highest sum several times for most nodes (try it on paper). A good way to prevent this would be to save this information within the node, so it wouldn't have had to be re-calculated ... well ... but that sounds familiar somehow ;-) (It's what the first algo does.)

tron.

: Thanks, it worked, is that the same as recursion
: ?
:
: