[Community puzzle] Pascal Trapezoid

This topic is about the puzzle Pascal Trapezoid.

Feel free to send your feedback or ask some help here!

Don’t really know how to approach this problem.
All my tries has resulted in memory error with bigger tests.
Is O(n²) algorithm a good way or are there some tricks involving string concatenation?

Knowing you, you might have overthought it. I know I did.

What I remember from solving this three weeks ago was that I analyzed the problem, studied the propagation patterns, refined the memoizing, thought about the proper structure for efficient string concatenation, and maybe one or two other small things. And my attempts timed out, mem’d out, you name it.
That’s when I made one or two key observations on the problem structure and constraints, that allowed me to remove one optimization after another. And in the end my code passed with a semidumb program (in my view).
In the end I removed the last smart parts of my program, just in case, and what do you know it took a lot more time, but still passed.

So my totally non-spoiler hints would be… if you want to know what you’re doing, keep searching… and if you don’t, just simplify things and try to understand why it passes later.

1 Like