Why I am getting Time Limit Exceeded? [closed]

by

Why I am getting Time Limit Exceeded?

Consider this triangle (ignore the numbers):

1
2 3

There are 2 possible paths to take here. Let’s add a row:

1
2 3
4 5 6

The 4 can only be reached via a path that ends directly above, the 5 has two paths which can reach it, the 6 can only be reached from the path previously ending left above of it. We now have 4 possible paths. Another row:

1
2 3
4 5 6
7 8 9 0

That’s 8 possible paths. Do you see a pattern? Let’s describe the path straight down to 7, starting from 1:

D = DOWN
R = DOWN AND RIGHT

DDD

The (single) path to 0:

RRR

Since in each step you go down one row, you can only chose between the two possibilities number of rows - 1 times, thus giving you:

2^(number of rows - 1) possible paths

With 100 rows, that’s alot. Your code tries to compute each of these paths separately. Assuming computing 1 path takes 1 nanosecond (which would be blazing fast) computing them all would take more than 2 * 10^16 years. Well, …

Time Limit Exceeded

So you now know that you cannot just compute every possible path and take the maximum. The main issue is the following:

1
2 3
4 5 6

One path to the 5 is 1 + 3 + 5, the path to the 6 is 1 + 3 + 6. Your code computes each path separately, thus 1 + 3 will be computed twice. If you save that result, you’ll get rid of most of the unnecessary computations.

How could you store such results? Well, 1 + 3 is the computation of the path arriving at 3, so store it there. What if a number (say 5) can be reached by multiple paths?

5 could be reached via 1 + 2 + 5 or 1 + 3 + 5.

Any path going through the 5 will give a higher result if it wen’t through the 3 first, so only remember this path (and ignore the path through the 2, it’s useless now).

So, as an algorithm:

For each row, starting at row 1 (not the first, but the second): For each entry: Calculate the maximum of the entries left above (if available) and directly above (if available) and store the result + the entry’s value as new value for the entry. Then, find the maximum of the last row.

More Related Contents:

  1. Why does this tell me that "gender" is an undeclared identifier on line
  2. segmentation fault in an sorted linked list program for Homework [closed]
  3. How to execute a c# exe from a c++ program
  4. Something about C++ binary [closed]
  5. Store derived class objects in base class variables
  6. Why does rand() yield the same sequence of numbers on every run?
  7. Why don’t I get a segmentation fault when I write beyond the end of an array?
  8. cudaMemcpy segmentation fault
  9. Same random numbers every loop iteration
  10. Overloading friend operator
  11. How do I print the elements of a C++ vector in GDB?
  12. Getting the actual length of a UTF-8 encoded std::string?
  13. std::string::c_str() and temporaries
  14. How to use clock() in C++
  15. Namespaces in C
  16. declare template friend function of template class
  17. Deleting specific line from file
  18. “Undefined symbols” linker error with simple template class
  19. Impact of cubic and catmull splines on image
  20. Spirit-Qi: How can I write a nonterminal parser?
  21. What’s the fastest way to pack 32 0/1 values into the bits of a single 32-bit variable?
  22. Which types on a 64-bit computer are naturally atomic in gnu C and gnu C++? — meaning they have atomic reads, and atomic writes
  23. Refreshing the auto complete (IntelliSense) database in Visual Studio
  24. Why can I access private variables in the copy constructor?
  25. What’s the difference between opening a file with ios::binary or ios::out or both?
  26. How to convert a command-line argument to int?
  27. What is different between join() and detach() for multi threading in C++?
  28. Does std::mutex create a fence?
  29. Should you overload swap in the std namespace?
  30. how to get process handle from process id?

Leave a Comment