The object is to output the largest possible sum of values in a top-to-bottom path of a pyramid. There will be up to 10,000 pyramids issued with less than 100 rows each. The inputs are inserted with stdin (cin). Example input:
1 2 3 4 5 6 7 8 9 10
2 // number of pyramids
3 // size of this pyramid
1
2 1
1 2 3
4 // size of this pyramid
1
1 2
4 1 2
2 3 1 1
5
9
I've found a couple of solutions, but I am required process an undisclosed input within 3 seconds which I fail to do.
I have a couple of questions regarding general efficiency:
1. Which is generally faster to access: dynamic or static memory? (stack vs heap) 2. Are there any performance differences found with 2D vs 1D arrays? 3. Does declaring a variable inside a loop detract from performance? 4. Are nested loops generally faster than recursion if both are done well? 5. Is the <cstdio>scanf function any faster than <iostream>'s std::cin? 6. Is there a faster way to access stdin? 7. Is passing by reference in a c++ manner slower than passing an address to a pointer in a C manner?
This is my current solution. Any suggestions are welcome.
1. There's no difference.
2. Usually, depending on how you access it. However, if you try to fit a two-dimensional structure into a 1D array, you just end up doing what the compiler is doing internally anyway.
3. No, unless it has a non-trivial constructor or destructor.
4. Depends on what you mean. Generally, you should prefer an iterative version to a recursive one if it is not a divide-and-conquer problem.
5. Sometimes. Usually it isn't and certainly not for this particular problem.
Edit: 7. No.
True performance improvements generally come from using better algorithms, like in this case.
Your approach has a complexity of 2^n and 2^100 is a lot. The problem can be solved with quadratic time as well.
Great, thanks. I thought that I may have taken the wrong approach but was hoping that one of the smaller things would help lead to significant timing improvements. I haven't figured out how to eliminate any paths and avoiding to brute-force it yet. I'll try and do that.