bradyawn's blog

Can I optimize this?
By bradyawn, history, 7 years ago, In English

UPD: Thanks for all the help guys! I threw away my recursive solution and solved it with loops. (DP?) :>

Hello all,

While going through the USACO training pages problem "Number Triangles", I used a recursive function to calculate the answer. You can see the problem statement here: http://train.usaco.org/usacoprob2?a=nOEpHRAhtUw&S=numtri

I used recursion to try and solve it, but ran into a timeout on test case 6:

> Run 6: Execution error: Your program (`numtri') used more than the allotted runtime of 1 seconds (it ended or was stopped at 1.715 seconds) when presented with test case 6. It used 4312 KB of memory.

I realized that with the test data at hand, it made sense that my program would timeout.

Data:

199 
    1 
    0 1 
    0 1 0 
    0 1 0 1 
    0 1 0 1 0 
    0 1 0 1 0 1 
    0 1 0 1 0 1 0 
    0 1 0 1 0 1 0 1 
    0 1 0 1 0 1 0 1 0 
    0 1 0 1 0 1 0 1 0 1 
    0 1 0 1 0 1 0 1 0 1 0 
    ... [and more] ...

My question is, is it possible for me to optimize my recursive solution, or should I try to use a loop instead of recursion? All hints and advice would be appreciated. (No full solutions please.)

My code below (C++11):

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Try using loops instead of recursion.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can try memoization.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution works in O(2^n) because of visiting the same states many times (i calced with this). You can use recursion with memoization or use iterative approach. It will decrease complexity to O(n^2). My AC code (solved here).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! I will try memoization as you suggested. Isn't this a greedy solution though?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is dp solution, because f[i][j] is made of previously calculated answers.

      → Reply