aadarsh_ram's blog

TLE in Atcoder LCS problem
By aadarsh_ram, 3 years ago, In English

Hi,

I tried to solve the LCS problem in the Atcoder Educational DP Contest. I used the top down approach (recursion + memoization) for solving the problem. I implemented this in Python first, which resulted in a TLE (no surprise, there). Then, I tried implementing the same code in C++, which performed even worse than my Python submission for some reason.

I would like to know where I could improve on further (both in Python and C++), so that the code passes within the time limit. Is it possible for solutions of the top-down approach to pass under the time limit given in the question?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Strings (string s, string t) are copied every time. That leads to additional n-factor. Use references (string &s, string &t) instead.

UPD. Moreover, it is a bad idea to keep the whole answer in every element of dp. Keep [one char + pointer to the previous state] instead.

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

    tch1cherin I tried introducing references to the code. But, it still doesn't come under the time limit. Regarding the [char + pointer] nethod, would you be able to show an implementation for the same? I mostly code in Python and have very liitle experience in C++ at the moment.

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

      For each spot, because of how the dp transitions work, for $$$\textrm{dp}[i][j]$$$ you either add one character when $$$s[i]=t[j]$$$ or skip one of the characters $$$s[i]$$$ or $$$t[j]$$$. Do the following:

      • If you take $$$s[i]=t[j]$$$, store $$$s[i]$$$ in your $$$\textrm{best}[i][j]$$$, and store the pair $$$(i-1,j-1)$$$ in $$$\textrm{prev}[i][j]$$$
      • If you skip $$$s[i]$$$, store some character that you can recognize to mean that you're not including it (like maybe _) in $$$\textrm{best}[i][j]$$$ and store $$$(i-1,j)$$$ in $$$\textrm{prev}[i][j]$$$
      • If you skip $$$t[j]$$$, store that character in $$$\textrm{best}[i][j]$$$ and store $$$(i,j-1)$$$ in $$$\textrm{prev}[i][j]$$$

      When you want to reconstruct your string, start with $$$(i,j) = (n-1,m-1)$$$ and go to $$$(i,j) := \textrm{prev}[i][j]$$$, storing $$$\textrm{best}[i][j]$$$ whenever it's not that special character.

      → Reply